ps:problems:boj:16705
목차
Game of Stones
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 16705 |
문제명 | Game of Stones |
레벨 | 다이아몬드 5 |
분류 |
게임 이론 |
시간복잡도 | O(n) |
인풋사이즈 | n<=10^5 |
사용한 언어 | Python 3.11 |
제출기록 | 34532KB / 92ms |
최고기록 | 64ms |
해결날짜 | 2023/07/04 |
풀이
- 경우를 나눠서 생각해봐야 한다. 우선 가장 돌이 많은 파일의 돌 갯수를 m이라고 하자.
- A와 B가 모두 m이상이라면, 누구든 하나의 파일에서 원하는 만큼 돌을 제거할수 있다. 이것은 그냥 제약 없는 님게임과 똑같아지므로, 모든 파일들의 돌 갯수를 xor한 것이 그런디 수가 된다.
- A와 B가 같다면, 일반적인 배스킨라빈스 게임을 여러개의 파일로 확장한 것과 동일하다. 배스킨라빈스 게임의 그런디 수는 n % (A+1) 이므로, 모든 파일에서 이 값을 계산해서 xor하면 그런디수가 된다.
- A>B 인 경우는 조금 생각이 필요하다. 선공이 후공보다 더 많은 선택지를 갖지만, 만약 선공이 자기도 똑같이 1~B 까지만 제거하겠다고 하고서 게임을 한다고 치자. 그러면 배스킨라빈스 게임이 되고, n%(B+1) 값들을 xor했을때 0보다 크다면, 선공은 1~B만 쓰고도 이길수 있다. 그런데 만약 그런디수가 0이었을 경우에는, 선공은 1~B만 쓰고서는 이길수가 없다. 대신 첫턴에만 B+1만큼을 제거해보자 (맨 처음에 m이 B이하인 경우는 제외했으니, 지금은 B+1개를 제거할수 있는 파일이 1개 이상 존재한다). 그런디수는 B+1로 나눈 나머지이므로, B+1개를 제거해도 그 파일의 그런디수에는 변화가 없다. 그리고 전체의 그런디수도 0을 유지하게 된다. 이 상태로 상대방에게 턴을 넘겨주게 되면, 이후에는 1~B만 사용해서 이길수 있다. 결국, m>B 이고 A>B인 경우에는 선공이 항상 승리할수 있다.
- A<B인 경우는 이제 반대가 된다. 선공이 얼마만큼을 제거하더라도, 후공이 위에서 설명한 전략을 사용하면 항상 이길수 있을것 같아 보인다. 하지만 선공이 이길수 있는 방법이 있는데, 선공의 첫 액션을 통해서, n%(A+1) 값들을 xor한 그런디수가 0이면서, 가장 돌이 많은 파일의 갯수가 A+1보다 작은 상태를 만들어서 넘겨줄수 있다면, 이때는 제약 없는 님게임에서 그런디수가 0이 되는 상황이기 때문에 후공이 승리할수 없다. 이 전략이 가능하려면, A보다 돌이 많은 파일이 1개뿐이어야 하고 (그 파일의 돌의 갯수가 m이 된다), 그 파일에서 A이하를 제거해서 총 그런디수를 0으로 만들수 있어야 한다. m을 제외하고 나머지 X를 모두 xor 한 값을 구하면, m이 그값과 같아지면 전체 그런디 수가 0이 된다. m을 제외하고 xor한 값을 k라고 하면 k<A+1 이고 m-K⇐A 를 만족할 경우에만 선공이 승리 가능하다. 나머지는 후공이 승리한다.
- Unfair Game 도 똑같은 문제이다.
코드
(다이아몬드 이상은 코드 비공개)
ps/problems/boj/16705.txt · 마지막으로 수정됨: 2023/07/04 14:36 저자 teferi
토론