[2020-09-23] Codeforces Round 666 (Div.1)

오늘도 망했다. C를 대회 끝나고 30초 뒤에 제출해서 맞았고.. B는 풀지를 못했다. 왜 B같은 유형은 도저히 풀리질 않을까.. 잘 풀리다가 다시 연속으로 말아먹으니 멘탈이 너무 깨진다.

A. Multiples of Length

어떤 수에 (x+1)을 더하면 x로 나눈 나머지는 1만큼 증가한다. 따라서, 전체 구간(1 ~ n)을 잡고 (n-1)로 나눈 나머지가 0이 되게 전체 값을 조정해준다. 그 다음 1 ~ n -1 / 2 ~ n 구간을 잡고 전체 값이 0이 되게 만들면 문제를 해결할 수 있다. n = 1일때 예외를 잘못 처리했다가 한 번 틀렸다. 이런 실수 하면 안 되는데..

B. Stoned Game

 이런 식의 케이스 분석 기반의 게임 문제는 도저히 풀지를 못 하겠다. 나올 때마다 못 푸는 듯. 다른 사람들은 잘 푸는데 왜..

 

 우선 할 수 있는 가장 간단한 관찰은, 크기가 n/2 보다 큰 무더기가 하나라도 있으면 무조건 선공이 이긴다는 것이다(선공이든 후공이든 누가 확실히 이기는 조건을 최대한 빨리 찾았어야 했을 것 같은데 이런 관찰을 빠르게 하지 않는게 제일 문제인 것 같다. 다음에는 이런 관찰부터 시도해야지). 이제 그러면 그게 아닌 경우를 생각해보자. 모든 무더기의 크기가 n/2보다 작은 경우는 어떨까? 선공 후공이 한 번씩 번갈아가면서 턴을 가지게 되니 전체 돌의 개수가 짝수인 경우랑 홀수인 경우로 나눠서 생각해보자.

 

- 전체 돌의 개수가 짝수개인 경우: 선공이 임의의 무더기를 골라서 돌을 하나 가져갔다고 가정하자. 이 때, 그렇게 가져간 돌로 인해 남은 돌 중 n/2보다 크기가 큰 무더기가 생기면 맨 처음 얘기한 케이스로 넘어가므로 후공이 이긴다. 그런 무더기가 없다고 가정하자. 이 때 돌을 가져가면 다시 이 케이스로 돌아오게 되고, 돌의 개수가 짝수개이므로 맨 마지막 돌을 후공이 가져가게 된다. 따라서 어느 경우든 후공이 이긴다.

 

- 전체 돌의 개수가 홀수개인 경우: 제일 돌의 개수가 많은 무더기에서 돌을 하나 가져가는 순간 바로 위의 케이스로 환원이 된다. 따라서 선공이 이긴다.

 

C. Monster Invaders

그리디가 섞인 DP다. 역시나 내가 강하진 않은 유형이다.. 그래도 풀 수는 있는 부류의 문제인데, 30초가 부족해서 못 맞았다. 끝나고 30초 뒤에 제출하니 바로 맞아서 너무 슬펐다.

 

 아무튼 풀이로 넘어가자면, 기본적으로 각 스테이지에서 하게 되는건 1. 모든 유닛을 다 처리하거나 2. 보스 체력을 1만 남겨놓고 이동하거나 둘 중 하나다. 또, 보스 체력을 1만 남겨놓은 스테이지가 여러 개 있을 경우, 매번 왔다갔다하면서 처리하는 것보다는 그게 포함된 전체 구간을 한 번 순회하면서 해결하는게 이득이다.

 

이러한 두가지 관찰에 기반해서 아래와 같이 상태를 구분할 수 있다.

 

 1. (idx, 0) = 현재 idx번째 스테이지에 있고, 1..idx-1번째 스테이지는 전부 다 처리한 경우

 2. (idx, 1) = 현재 idx번째 스테이지에 있고, 1..idx-1번째 스테이지 사이에 체력이 1 남은 보스가 하나 이상 있는 경우

 3. (idx, 2) = 현재 idx번째 스테이지에 있고, 1..idx-1번째 스테이지 사이 어딘가에 체력이 1 남은 보스가 하나 있음. 그리고, 그 스테이지에서 마지막으로 보스 잡고 게임을 끝내는 경우

 

이렇게 상태를 분류하면 각 상태에서 할 수 있는 동작에 따른 상태 전이를 정의할 수 있다. 식을 세울 때 쓸 수 있는 또다른 중요한 관찰 중 하나는, (x, 0) 에서 맨 처음 보스 체력 1 남겨놓고 스테이지를 이동할 때 (x -> n -> x) 만큼의 이동거리를 미리 답에 더해놓고, 그 이후 y > x인 (y, 1) 에서 마지막 보스 체력 1 처리할 때 (y -> n -> y) 만큼의 이동거리를 빼주면, x ~ y 사이를 왔다갔다하면서 처리하는 이동거리 (y -> x -> y)를 따로 상태 저장할 필요 없이 답에 포함해서 계산할 수 있다는 것이다.

 

이를 잘 이용해서 식을 세우면 O(N)에 문제를 해결할 수 있다. 자세한 식은 적기 귀찮으니깐 패스