ARC 069

용인에서 원준이와 호캉스를 즐기면서 ARC 069를 돌기로 했다. ARC로 놓고 봤을 때에는 문제들이 좀 쉬운 대신 구현하기 싫은 편인 것 같지만, 만족스러운 셋이었다.

 

 

C. Scc Puzzle

 

세상에 이런 문제는 없었다! 이것은 앳코더인가 코드포스 div.2인가? 쉬운 구데기 문제로 직선의 교점을 잘 구해서 $O(1)$로 풀거나 삼분탐색으로 $O(\log n)$으로 풀면 된다. 나는 삼분탐색을 썼다. 비트베리가 떠오른다...

 

 

D. Menagerie

 

입력으로 주어지는 문자열의 각 원소 $s[i]$는 "$i-1$, $i$, $i+1$번째 동물 중에서 양의 수가 홀수인가?"에 대한 답과 동치이다. $1$, $2$번째 동물이 무슨 종인지만 정해주면 나머지가 모두 정해지게 되므로, 4가지 경우 모두 해 보고 입력 조건에 맞는 것을 출력하면 된다.

 

 

E. Frequency

 

지금 가장 높고 왼쪽에 있는 막대(실제론 돌뭉치지만 막대가 편하다)를 $k$번 막대라 하자. 쭉 $k$만 나오게 수열을 만드는 건 쉽다. 그러니깐 수열에 $k+1$ 이상의 수가 등장하게 되면 망한다. 하지만 이걸로 충분치 않다. 우리는 더 좋은 수열을 만들고 더 나은 세상을 만들고 싶다.

 

$k$보다 더 작은 수를 수열에 등장시키고 싶은데 누굴 등장시킬 수 있을까? $k$번 막대 왼쪽에 있는 가장 높은 막대를 찾아 $l$번 막대라 하고 얘를 등장시키자. $l$번 막대보다 높은 막대를 모두 $l$번 막대와 같게 깎으면 가능하다. $l$번이 최소의 연산 후 등장시킬 수 있는 $k$번보다 작은 수임은 당연할 것이다. 이 작업을 반복해 보면, 대충 이렇게 생각할 수 있는데:

 

- 막대기를 왼쪽에서 바라봤을 때 보이는 막대기(자신의 왼쪽에 자신보다 높거나 같은 막대가 없는 막대)를 차례대로 등장시키면 정답이다. 이를 $i_1 < i_2 < \cdots < i_k$번 막대라 하자.

 

- $i_k$부터 $i_1$까지 거꾸로 보면서 얘보다 높은 애들이 없을 때까지 나머지를 다 깎아주는 것을 반복하는 것이 전략이다.

 

- $i_x$가 수열에서 등장하는 횟수는 모든 막대의 $i_x$보다 크고 $i_{x+1}$보다 낮은 부분의 높이의 합이 될 것이다.

 

 

F. Flags

 

$O(n^2 \log X)$ 풀이는 쉽게 생각할 수 있다: 파라매트릭으로 모든 깃발 쌍이 거리 $d$ 이상을 유지할 수 있는가를 검사하면 된다. 검사는 2-SAT이 만족 가능한지 검사를 수행하면 된다. 간선 $O(n^2)$개의 완전 그래프의 SCC를 구해야 하는 게 문제지.

 

$O(n^2 \log X)$ 풀이를 최적화해야 하나, 생각하던 와중 원준이가 오지고 지리는 풀이를 하나 냈다. 먼저 깃발들을 위치 순서대로 정렬해두고 생각을 시작해 보자. "이 깃발"을 고르면 "위치가 이 구간 안에 있는 다른 깃발"을 고르면 안 되니까, "고르면 안 되는 깃발"이 한 구간에 있다.

 

세그먼트 트리를 그리자. 정점 $x$가 "$s_x$번째부터 $e_x$번째까지의 깃발을 고르지 않는 사건"을 의미하게 하고 구간의 왼쪽 절반과, 오른쪽 절반 구간을 고르지 않는 사건을 의미하는 두 개의 정점을 가리키게 하자. 그러면 어떤 정점이 다른 구간의 정점을 한꺼번에 잇는 연산은 $O( \log n)$개의 트리 내의 정점을 잇는 것으로 대체되므로, 정점과 간선이 모두 $O(n \log n)$개 있는 그래프의 SCC를 구하는 문제로 바뀐다. 이 중 리프를 나타내는 마지막 $n$개의 정점은 깃발 하나만을 관리하므로, "이 깃발을 고르지 않는 사건", 즉 "이 깃발과 대응되는(반대되는) 깃발을 고르는 사건"과 대응된다. 마지막에 각 $i$에 대해 $x_i$ 깃발을 나타내는 정점과 $y_i$ 깃발을 나타내는 정점이 다른 SCC에 속해 있는지만 검사해주면 문제가 해결된다.