[codingame] FIND THE WINNING STRATEGY

https://www.codingame.com/training/medium/find-the-winning-strategy

접근법

• nim game
• 게임이론
• Impartial game
• 스프라그 그런디 이론

참고

• https://ohgym.tistory.com/21
• https://librewiki.net/wiki/%ED%95%84%EC%8A%B9_%EC%A0%84%EB%9E%B5_%EA%B2%8C%EC%9E%84

정리

• 매번 이해하는 이론임
• 승리 상태를 유지하는게 목적인데, 이 경우에는 내 턴에 모든 가져갈 수 있는 것들의 xor이 0이 되게 유지하면 됨
• 주머니에서 마음대로 돌을 가져가는 게임이 이 문제와 동일한 내용임
  • 요약 : 주머니에서 마음대로 돌을 가져가는데, 못가져 가는 사람이 짐
  • https://www.acmicpc.net/problem/11868
• 0이 아닌 경우에 0을 항상 만들 수 있는데, 이 부분 이해가 매번 어려웠음
  • $x_1........x_n$ 들을 xor해서 어떤 값이 나왔다고 치고(0이 아님)
  • 이 중에 하나의 $x_k$를 바꿔서 $y_k$가 될 것임
  • 일단 바뀐 후의 값은 기존 xor에서 $x_k$를 제거하고 $y_k$가 되기때문에
  • $(x_1.....x_n) \oplus x_k \oplus y_k$가 될 것임 ($x_k$를 xor 하면서 $x_k$가 제거되는 효과)
  • 이때 ($x_1.....x_n$)으로 만들어진 값에서 가장 상위 비트를 갖고 있는 것을 $x_k$로 지정한다면
  • $(x_1.....x_n) \oplus x_k$ 하는 순간
    • 왼쪽 상위 비트들은 다 0이니까 그대로 0이고
    • 가장 상위 1인 비트는 사라질테고
    • 그 이후 오른쪽 비트들은 뭔가 값이 나올텐데
    • 결과적으로 $x_k$보다 작은 값이 됨
  • 그렇다면 이 값을 $y_k$로 둔다면, xor한 것들을 0으로 만들 수 있음
  • $x_k -> y_k$가 되었기때문에 감소한 값은 $x_k - y_k$가 됨