개요
저번 주 모임을 못 해서, 이번주까진 그냥 내가 뽑았다.
A번: 한 줄로 서기
문제 요약
키가 1~N인 사람들이 있고, 각자 자기보다 왼쪽에 몇 명이 있었는지만 기억할 때 줄 세우기
설명
뭔가 와닿지 않아 생각보다 헷갈렸다.
풀이 자체는 간단한 편이다.
- 키 기준 정렬
- 돌면서, 왼쪽에 자신보다 큰 사람이 다 채워졌다면 선택
제한이 넉넉해 $N^2$로 그냥 구현하면 된다.
B번: 가장 가까운 세 사람의 심리적 거리
문제 요약
사람들의 MBTI들이 주어질 때, 해밍 거리의 총합이 가장 작은 세 명을 구하면 된다.
설명
사람의 수 N은 100000까지이므로 $N^3$은 못한다.
그래서 $16^3$으로 거리를 계산해두고, [(거리, 조합)] 꼴로 만들어 거리순 정렬해둔다.
사람마다의 mbti는 count 배열을 만들어 관리한다.
그럼 정렬된 조합마다 가능한지 여부를 확인할 수 있다.
C번: 트리와 쿼리
문제 요약
루티드 트리에서, 어떤 정점 U의 서브트리 내의 정점 수를 묻는 질의를 처리한다.
설명
업데이트 같은 게 없으므로 그냥 dfs로 그래프->루티드트리 진행할 때 같이 세 주면 된다.
D번, E번: 용액 / 두 용액
문제 요약
두 문제는 같은 문제라서 솔브드 점수 복사하라고 넣어뒀다.
수열에서 합이 가장 작은 쌍 찾기
설명
N개의 아이템마다 돌며 이분 탐색으로 찾으면서 최소값 갱신하기.
즉 $N \log{N}$이다.
F번: 뉴스 전하기
문제 요약
트리에서 소식을 전파한다. 전파는 자식 하나마다 1초가 걸린다.
가장 빠르게 전파할 때 걸리는 시간를 구하기
설명하기 애매하므로 문제를 읽어보자.
설명
자식 중 가장 오래 걸리는 자식에게 먼저 전파해야 한다는 것만 캐치하면, C번 문제와 별로 다를 게 없다.
DFS 한 번으로 풀 수 있다.
G번: 약 팔기
문제 요약
1~1000000 중 어떤 값이든 구간합으로 만들 수 있도록 하는 배열을 구성하는 문제
설명
꽤 오래 걸렸고, 답을 알게 되고 어이가 없었다.
처음엔, 구간합 배열로 치환하여서
임의의 정렬된 배열 A에서, 모든 x에 대해 $A[j] - A[i] = x$, $(i<j)$ 인 경우가 존재하게 만드는 것으로 생각했다.
하지만 거기서 딱히 발전이 되지 않았다.
그 다음엔 진법으로 생각해봤는데, 연속된 구간이라는 점에서 막혔다.
1 1 2 2 4 4 같은 식으로 중복을 시키는 경우도 생각해봤지만 마찬가지였다.
그러다가 한 가지 아이디어를 캐치했는데, 연속된 부분이라면 $A \cdot P + B \cdot Q$ 같은 형태로 나타낼 수 있다는 것이다. A,B가 값이고, P,Q가 개수와 같은 형태이다.
K=2000, N=1000000이라는 값이 작위적이므로, 위 아이디어를 적용해 조금 생각해봤더니 바로 풀렸다.
A, B를 1, 1000으로 하면 된다…
후기
G번 문제만 한참 걸렸는데, 답을 알고 나니 너무 허무했다.