JOI 2017/18

JOI 2017/18의 온라인 미러에 참가해 보았다. 올해 JOI는 츠쿠바 시(올해 IOI와 같은 곳!)에서 오전 10시에서 오후 2시까지 진행되었다. 나는 늦잠을 자서 정오에 문제를 풀기 시작했다. 대회 시간 안에는 1, 2만을 풀 수 있었고, 시간을 두고 생각해본 결과 3, 4까지는 풀 수 있었다. 5는 더 생각을 해야 할 듯하다.

1. Stove

$k=n$일 때의 답은 $n$이다. 아닐 때에는, 연속된 두 시점 사이를 스토브를 끄지 않고 유지할 필요가 있다. 구간들은 서로 독립이므로, 구간들의 크기($a_i - a_{i-1} - 1$)들을 크기 순으로 정렬하고 작은 것 $n-k$개를 가져다 쓰면 된다.

시간 복잡도: $O(n \log n)$

2. Art Exhibition

크기 순으로 미술품을 정렬했다고 하자. 이 때의 미술품의 크기를 $s_1, \cdots, s_n$, 가치를 $v_1, \cdots, v_n$이라 하자. 어떤 연속된 구간 $i\cdots j$의 미술품을 쓰는 것이 무조건 최적임을 알 수 있고, 이 때의 값은 $\sum_{k=i}^j v_k - s_j + s_i$. $V_i = sum_k=1^i v_i$로 부분합을 정의하면 $V_j - V_{i-1} - s_j + s_i$가 된다. Two pointers로 왼쪽 포인터는 $V_{i-1} - s_i$의 최솟값을, 오른쪽 포인터는 $V_j - s_j$를 가리키게 하면서 차례대로 살피면 된다.

시간 복잡도: $O(n)$

3. Dango Maker

비슷한 문제들이 2-SAT나 플로우로 변형되는 것을 많이 보고, 이 문제도 그렇게 되리라 생각할 수 있다... 하지만 그렇게 하면 시간 안에 나오지가 않을 것이다. 전체 격자판 $(x, y)$를 $x+y$를 $3$으로 나눈 나머지로 세 가지 색을 칠하자. 모든 RGW 묶음은 서로 다른 세 가지 색으로 이루어져 있을 것이고, 셋 중 하나의 색이 정해진다면, 나머지 둘의 색도 정해질 것이다. 만약 어떤 RGW의 묶음을 골랐을 때, 이것이 최적이 아니려면 셋 중 하나가 겹치는 다른 묶음이 존재해, 이것을 고르는 게 최적이어야 할 것이다. 그 말은, $x+y=k$꼴의 대각선 위에 한 점(가장 쉽게는 G)를 고정시켜두면, 이 대각선 위에서 무엇을 고르던 상관없이 다른 대각선에서 고르는 것에는 영향을 끼치지 않는다는 것이다! 이를 활용해 대각선 단위로 독립적으로 DP를 구성해, 합치면 된다.

각 열의 DP는, 이를테면 다음과 같이 구성한다.

$dp(i, 0) :=$ 대각선의 i번째 칸에서 묶지 않았을 때 최대 묶음의 수

$dp(i, 1) :=$ 대각선의 i번째 칸에서 세로로 묶었을 때(가능하다면) 최대 묶음의 수

$dp(i, 2) :=$ 대각선의 i번째 칸에서 가로로 묶었을 때(가능하다면) 최대 묶음의 수

이 때에 생각해주어야 할 것은, 한 칸에서 세로로 묶었다면, 그 다음 칸에서는 가로로 묶을 수 없다는 것이다. 이를 고려하여 차례대로 반복해주면 답이 나온다.

시간 복잡도: $O(NM)$

4. Commuter Pass

흥미로운 그래프 문제이다. 그래프에서 최단 경로가 여러 개 있을 수 있다는 사실은 사실 꽤 섬뜩한 사실이다. 그러니 그냥 하나의 최단 경로에 대해서만 생각해보자. $S$에서 $T$까지의 하나의 최단 경로를 잡아, 이 경로 위의 모든 간선의 비용을 0으로 만들었다. 이 때, $U$에서 $V$까지의 최단 경로는 무조건 비용을 0으로 만든 간선(Commuter Pass)들을 '연속적으로 몇 개' 지난다. 하나도 안 지날 수도 있고. 만일 연속으로 지나지 않고 드문드문 지나게 된다면, 지났던 commuter pass 위의 첫 점과 마지막 점을 단순히 이어주면 더 짧은 경로가 나오기에 모순이 된다.

따라서, 풀이는 commuter pass 위에 포함될 수 있는 각 점에 대해, $U$와 $V$로 가는 최단 경로의 길이를 적어두는 것으로 시작된다. 답은 commuter pass 위의 어떤 점 $i$에 대해, commuter pass에서 $i$ 이전에 위치할 수 있는 정점과 $U$의 거리의 최솟값 $+$ $i$와 $V$의 거리 또는 이전 정점과 $V$의 거리 $+$ $i$와 $U$의 거리 중 최솟값이 된다. $S$와 $T$의 최단 경로 위에 있는 정점이라는 것은, $S$에서 출발해, 간선의 양 끝 점과 $T$와의 거리가 간선의 길이와 같은 간선들만 이용해서 갈 수 있는 정점이라는 것과 동치임을 이용한다면, 위상 정렬을 이용한 그래프 DP와 같은 방식으로 해결할 수 있을 것이다.

시간 복잡도: $O(N \log N)$

5. Snake Escaping

문제를 보고, 먼저는 '이게 $O(3^n)$보다 더 빠르게 가능하다고?'라는 생각이 들었다. 이게 어떻게든 시간 안에 꾸역꾸역 줄여지는 모양이다.

zscoder는 $l=20$인 경우, 첫 13자리와 뒷 7자리를 나누어 뒷 7자리가 가질 수 있는 128가지 다른 수들로 수를 128개의 서로소인 집합으로 나누는 아이디어를 제시했다. 그러면 각 집합 안에서 첫 13자리에 대해 가질 수 있는 $3^{13}$개의 질문에 대한 답을 전처리해, 시간 복잡도 $O(2^7 \times (3^{13} + Q))$와 공간 복잡도 $O(3^{13} + Q)$로 풀 수 있다고 밝혔다. 이 방법은 풀 수 있는 방법이긴 하지만 깔끔하지 못해, 다른 방법을 찾고 있다.

다른 아이디어(koosaga, zigui)는 간략히 '0', '1', '?' 세 가지 문자로 이루어진 쿼리를 {'0', '?'}, {'1', '?'} 두 가지 문자로 이루어진 쿼리 여러 개로 나눌 수 있을 것이라는 것이다. 이를 'OR', 'AND'(왜냐하면 AND(x)에는 $x \operatorname{and} i = x$인 $i$들에 대한 값의 합을 넣을 것이기 때문, OR도 마찬가지)를 이용해 $O(2^{20})$의 시간에 전처리할 것이다. 굉장히 멋진 아이디어이다. 이 방법에 대해 생각해보고 있으며, 생각나는 대로 정리해서 올릴 것이다.