Problem solving (2022/01/04)

오랜동안 손대지 않았던 PS를 다시 단련하기 시작했다. 내가 생각하는 PS의 가장 중요한, "생각하는 재미" 가 있는 문제들을 찾아 AtCoder Regular Contest (ARC) 기출 문제를 몇가지 풀었다. 그 중 재밌었던 몇가지 문제의 풀이를 소개한다.

Camels and Bridge (ARC105C)

우선 다리가 붕괴되는 케이스를 예외처리하는데, 다리에서 capacity 가 가장 적은 부분을 무게가 가장 무거운 낙타가 혼자 통과하지 못하는 경우가 유일한 경우이다. 이 경우를 제외한다면, 낙타가 일렬로 다리를 통과하는 것이 가능하고 생각할 수 있다. 이 것을 보이는 것은 쉬운데, 낙타 한마리가 다리를 다 건너기 전까지 다른 낙타를 출발시키지 않는다고 생각하면 된다.

다리를 지나는 낙타의 순서를 순열로 나타내면, 순열의 길이는 $2 \leq N \leq 8$ 이고 이는 충분히 작기 때문에 해당 길이의 모든 순열 ($N!$ 개)을 완전탐색 하고, 각 순서에 대한 "첫번째 낙타와 마지막 낙타의 거리의 최소값" 중 최소값이 답이 된다.

그렇다면 낙타가 다리를 지나는 순서가 고정되었다고 가정하고 문제를 풀어보자. $1 \leq i < j \leq n$ 일 때, $i$ 번째 낙타와 $j$ 번째 낙타가 가져야하는 "최소" 간격을 $dp_{i, j}$ 에 저장한다. 사실 "최소"라는 표현은 애매모호함을 넘어 매우 잘못된 표현인데. 정확히는 다음을 의미한다: $i$ 번째 낙타와 $j$ 번째 낙타가 연이어 다리에 들어갈 때, 낙타들이 동시에 올라가지 못하도록 병목이 발생하는 다리 구간들 중 길이가 최대인 한 구간의 길이. 이해가 어렵다면 다음 문단을 읽어보자.

$dp_{i,j}$ 를 빠르게 계산하기 위해 다음과 같은 전처리를 수행한다: 다리 ($i$ 번째 다리의 부분은 $w_i$ 의 무게를 가지고 $l_i$의 길이를 가짐)를 무게순으로 정렬한 후 길이는 누적 최대 길이로 변경한다 (정렬 후, $w_i = \max_ {1 \leq j \leq i} w_j$). 이를 사용하면 $dp_{i, j}$ 는 $O(log M)$ 에 계산할 수 있다. 결국 $dp_{1, n}$ 가 이 문제의 부분해가 되고, 이를 구하기 위해서는 Floyd-Warshall 비스무리한 DP를 해야한다:

마지막 DP는 $O(N^2)$ 의 수행시간을 가지며, 따라서 최종 시간복잡도는 $O(N!*N^2 log M)$ 이다.

Let's Play Nim (ARC105D)

기본 nim game의 필승 전략을 알고 있다면 Sprague-Grundy 정리 따위는 잊어버리고 그리디한 필승전략을 생각해보자. 우선 문제에서 소개되어 있는 1번 행동을 두명이서 번갈아 가면서 $N$ 번 수행하면 그 다음부터는 2번 행동, 즉, 우리가 잘 알고 있는 nim game을 하게 된다. 따라서 $N$ 의 홀짝성에 따라 두 사람의 전략이 바뀐다는 것을 떠올릴 수 있어야 한다. 우선 다음과 같은 케이스로 분류된다:

1. $N$ 이 짝수일 때: 게임을 먼저 시작한 플레이어가 nim game 도 먼저 시작하게 된다. 따라서 선공은 XOR 합이 0이 아니도록, 후공은 XOR 합이 0이 되도록 동전을 접시에 놓아야 한다. 같은 개수의 동전이 든 가방이 모두 짝수개라면, 후공이 반드시 승리한다. 선공이 하는 행동을 그대로 따라하기만 하면 반드시 XOR 합을 0으로 만들 수 있다. 그러나 그 반대의 경우는 선공이 무조건 승리하는데, 선공이 동전이 많이든 가방 순으로 같은 접시에만 동전을 둔다면 과반수 이상의 동전이 한 접시에만 담기게 되고 XOR 합은 0이 될 수 없다.
2. $N$ 이 홀수일 때: 게임을 나중에 시작한 플레이어가 nim game 을 먼저 시작하게 된다. 이 경우는 반드시 후공의 승리가 보장되어 있다. 후공은 XOR 합이 0이 아니게 두면 되는데, $N$이 짝수인 케이스와 비슷하게 후공은 같은 접시에 최대한 많은 동전을 모으면 반드시 승리한다. 그리고 이 케이스에서는 선공이 후공의 행동에 대칭적으로 플레이할 수도 없다.

Nim game 에 대해 알고 싶다면 다음을 참고 하면 좋다: 필승 전략 게임

총평

각 문제당 최소 3시간을 투자했는데, 결국 단 한문제도 스스로의 힘으로 해결하지 못했다. 난이도가 1800~2000 인 문제들인데, 아직 내가 스스로 해결할 만한 수준이 아닌 것 같아 아직 갈길이 한참 멀었음을 다시 한번 깨닫게 되었다... :/