[2020-09-20] Codeforces Round 659 (Div.1)

좀 잘된다 싶더니 바로 거하게 말아먹었다. 오늘 문제는 내가 유독 약한 쪽이기도 했고.. 뭔가 실수라거나 말려서라기보단 그냥 실력 부족인 것 같다. 케이스 분석 능력이 항상 엄청 떨어지는데 이런건 어떻게 해야 키울 수 있는지 잘 모르겠어..

A. String Transformation 1

각각의 알파벳을 그래프 상에서의 노드로 보고, 알파벳 x에서 y로 변환이 필요한 경우 x -> y 엣지를 만들어주자. 이 경우, 항상 x < y 이기 때문에 만들어지는 그래프는 DAG이고, 각각의 weakly connected component에서는 항상 (그 컴포넌트 크기 - 1) 만큼의 변환을 하면 원하는 변환을 모두 할 수 있게 된다. 따라서, 이렇게 그래프를 구성한 후 wcc 기준으로 (크기 -1)을 전부 구해서 더해주면 된다.

B. GameGame

주어진 배열의 모든 값을 전체 XOR한 걸 k라고 하자. 그리고, 두 플레이어가 각각 가져간 점수를 a, b 라고 하자. 일단 a^b = k가 항상 성립함을 알 수 있다. 이 때, k = 0인 경우 a^b = 0이고, a^b^b = 0^b, a = b가 되므로 이 때는 항상 DRAW인 것을 알 수 있다. 그렇지 않다면, a와 b의 최상위 비트 값이 반드시 달라지게 되므로 승패가 결정된다.

 

이 때 승패가 결정나는 비트는 k에서의 최상위 비트이다. 그보다 더 위의 비트는 항상 짝수개가 있는데, 이 경우 양쪽에서 어떻게 원소를 가져가도 그 비트의 개수가 같다. 따라서, 해당 비트는 답에 영향을 미치지 못한다.

 

 홀수개가 있는 비트의 경우 반드시 양쪽이 가져가는 비트의 개수가 다르기 때문에 여기서 승패가 결정나게 된다.

 

 이제 승패를 결정하는 비트 b가 1인 수의 개수를 one, 0인 수의 개수를 zero라고 하자. one은 홀수이므로, one을 4로 나눈 나머지는 항상 1이거나 3이다.

 

 - one % 4 == 1인 경우 : 선공이 먼저 1을 가져갔다고 치자. 이 경우, 남은 1의 개수는 4의 배수가 된다. 선공은 후공이 1을 가져갈 때마다 본인도 1을 가져가면 마지막에 항상 1을 홀수개 가져갈 수 있다. 따라서 이 경우 반드시 선공이 이긴다.

- one % 4 == 3인 경우

   - zero % 2 == 0인 경우: 후공은 그냥 선공의 행동을 무조건 따라하면 된다. 선공이 마지막에 하나를 더 가져가게 되고, 그 외의 나머지는 전부 같은 개수 만큼을 갖게 되는데, 이 경우 선공은 반드시 1을 짝수개 가져가게 된다. 따라서, 후공이 이긴다.

  - zero % 2 == 1인 경우 : 선공이 0을 가져가면, 앞의 케이스(zero % 2 == 0)와 동일해진다. 따라서, 선공이 이긴다.

 

그러니 이 경우 one % 4 == 3 && zero % 2 == 0 일 때 Lose, 나머지는 Win이 된다.

 잘 모르겠으면 DP를 써서 계산한 다음 규칙이라도 찾자. 일단은 게임 문제를 많이 안 풀어봐서, 이런 식으로 개수 / 모듈러로 케이스 분석을 하는 것 자체가 익숙하지 않은게 문제였던 것 같다. 4의 모듈러 기준으로 본다든가 하는 생각을 잘 못했다. 어떻게 보면 당연히 저렇게 분석을 해야하는 건데..

C. String Transformation 2

 A에서 사이클을 허용하는 경우를 해결하는 문제이다. 업솔빙하려고 했는데 풀이 봐도 증명이 잘 이해가 안돼서.. 그냥 따라해서 구현하는게 별 의미 없는 것 같아서 패스. C보다 많이 풀렸던 D랑 E를 보는게 나을 것 같다.