180914 ARC CD밀기 #001

너무 많이 쉬었더니 PS실력이 집을 나가버렸다.

ko_osaga님의 추천으로 ARC를 최근 것부터 밀어보기로 했다. EF는 어려우니까 CD부터. 물론 D마저도 몇 개 못 풀었다... 은퇴를 고려해야 하나.

C는 대부분 간단한 관찰로 밀어버릴 수 있는 문제같다. 코드도 400B 안쪽으로 나오는 것 같으니 웬만큼 좋은 문제가 아니면 포스팅하지 않을 계획.

오늘 푼 문제(6 / Total 6) : 

ARC102C (Triangular Relationship)

ARC102D (All Your Paths are Different Length)

ARC101D (Median of Medians) #오늘 푼 문제는 아닌데 괜찮은 문제라서 포스팅.

ARC100C (Linear Approximation)

ARC098C (Attention)

ARC098D (Xor Sum 2)

고민중인 문제 : 

ARC101D (Equal Cut)

ARC100D (Snuke Number) #이미 Editorial을 봤지만 아직 증명 완성 못함.

문제 본문은 대회 홈페이지에서도 볼 수 있지만, kenkoooo의 AtCoder Checklist에서도 쉽게 접속할 수 있다.

---

This section is intentionally left blank. (스포방지가 없다. 주의!)

---

ARC102D. All Your Paths are Different Length

정수 \(L\)이 주어질 때, 대충 \(N \sim \lg L\)개 정도의 정점과 \(3\lg L\)개 정도의 에지를 사용해서 \(1\)번 정점에서 \(N\)번 정점까지 가는 서로 다른 경로가 정확히 \(L\)개이고, 또 그 경로들의 길이가 각각 \(0\)에서 \(L-1\)까지의 서로 다른 정수가 되는 방향그래프를 모델링해야 한다.

단, 모든 에지는 번호가 작은 정점에서 큰 정점으로 향해야 하며, cost에 0이 허용된다. 또한 multi-edge가 허용된다는 점이 특이하다.

일단 \(N\)개의 정점을 가지고 최소한 \(2^N\)가지의 경로를 만들어내야 하므로 이진법으로 접근해볼 수 있다.

\(2N\)개의 에지를 사용해서 \(i\)번과 \(i+1\)번 정점을 cost \(0\)짜리 간선 하나, \(2^{i-1}\)짜리 간선 하나를 사용해서 이어준다. 이 경우 \(0\)부터 \(2^{N} - 1\)까지의 모든 정수를 길이로 갖는 총 \(2^{N}\)가지의 경로를 만들 수 있다.

\(L \neq 2^k\)인 경우를 생각해보자. \(L = 2^{l_1} + 2^{l_2} + \cdots + 2^{l_k}\)이라고 하자. \((l_i > l_{i+1})\)

이 때 \(N = l_1\)으로 잡고, \(i \ge 2\)에 대해 \(l_i\)번 정점과 \(N\)번 정점을 길이 \(2^{l_1} + \cdots + 2^{l_{i-1}}\)짜리 간선으로 이어주면 된다. 왜 그렇게 생각했는지도 이해하기 어렵지 않다.

---

ARC101D. Median of Medians

길이 \(N \le 2\times 10^{5}\)짜리 수열 \(A\)가 주어졌을 때, \(M_{l,r}\)을 \(A_l, \cdots A_r\)의 중앙값이라 하자. \((l \le r)\) 이 때 모든 \(M_{l,r}\)들을 모아놓은 '중앙값 수열'의 중앙값을 구해야 한다.

중앙값 문제는 대부분 이분탐색과 결부되는 경우가 많다. 이 경우에도 결정 문제를 잘 해결하면 된다.

Median이 \(A_x\)가 될 수 있는지 판단하는 결정 문제를 풀어보자. 그리고 \(A_x\)보다 작은 숫자는 -1, 크거나 같은 숫자는 1로 바꿔준다. 중앙값 수열의 중앙값이 -1이라면 문제의 답은 \(A_x\)보다 작고, 1일 경우 문제의 답은 \(A_x\) 이상이다.

결국 우리는 새롭게 -1/1로 원소를 재정의한 수열 \(A'\)에서 \(M'_{l,r}\)이 1인 수열의 개수가 \(\frac{n(n+1)}{4}\) 이상인지를 판별하면 된다. 이는 결국 \(A'\)의 구간 합이 0 이상인 수열의 개수를 묻는 문제로 바뀌고, Fenwick tree를 이용하면 \(O(N\lg N)\)에 해결할 수 있다. 결정 문제를 \(O(N\lg N)\)만에 해결했으니 원래 문제는 \(O(N \lg^2 N)\)에 해결가능하다.

---

ARC098D. Xor Sum 2

3개 중에 가장 쉬운 문제라고 생각한다. 물론 덤벙대는 바람에 구현이 오래 걸렸다..

길이 \(N \le 2 \times 10^5\)짜리 수열 \(A\)가 주어질 때, \(A_{i} \oplus \cdots \oplus A_{j} = A_{i} + \cdots + A_{j}\)인 \(i \le j\)의 개수를 구해야 한다. 물론 \(\oplus\)는 bitwise-xor.

좌변이 우변을 절대로 넘을 수 없음은 쉽게 알 수 있다. 따라서 양변이 같으려면 모든 bit의 등장 횟수가 최대 1회여야 한다.

수열을 순회하면서 각각의 비트에 대해 그 비트가 마지막으로 등장하는 인덱스 2개를 들고 다니면 쉽게 해결할 수 있다. 시간복잡도는 \(O(N\lg X)\).