사용자 도구

사이트 도구


ps:problems:boj:16879

궁전 게임

ps
링크https://www.acmicpc.net/problem/16879
출처BOJ
문제 번호16879
문제명궁전 게임
레벨플래티넘 1
분류

스프라그-그런디

시간복잡도O(n)
인풋사이즈n<=300,000
사용한 언어Python
제출기록30840KB / 400ms
최고기록400ms
해결날짜2022/06/07

풀이

  • 궁전들이 겹쳐도 상관 없기때문에, 궁전이 한개만 올라가있는 체스판 N개가 독립적으로 있는 상황으로 생각해도 된다. 그러면 스프라그-그런디 정리를 이용해서 궁전 위치에 따른 그런디 수를 구한 다음에 모두 xor해주면 끝.
  • 좌표에 따른 그런디 수를 구하는 것은, 쉽게 패턴이 떠오르지는 않는다. 한참 일일히 계산해서 그려보다보면 아래와 같은 패턴이 보인다
    • . . . . . .  .  .  .  .
      . . . . . .  .  .  . .
      5 3 4 2 0 1 11  9 10 ...
      4 5 3 1 2 0 10 11  9 ...
      3 4 5 0 1 2  9 10 11 ...
      2 0 1 5 3 4  8  6  7 ...
      1 2 0 4 5 3  7  8  6 ...
      0 1 2 3 4 5  6  7  8 ...
  • 3*3칸 단위로 끊어보면 이런 패턴이고..
    • x+2   x   x
      x+1 x+2   x
      x   x+1 x+2
  • 3*3칸 단위로 묶어서 x/3 값만 적어보면 아래처럼 2^k *2^k 단위로 다시 패턴이 반복된다
    • . . . . . . . .
      3 2 1 0 7 6 5 4 ...
      2 3 0 1 6 7 4 5 ...
      1 0 3 2 5 4 7 6 ...
      0 1 2 3 4 5 6 7 ...
  • 이제 이 패턴을 이용해서 grundy 수를 구하면 된다. 대충 O(log(n)) 정도의 시간복잡도로 구현했는데.. 구현이 좀 복잡하긴 했다.
    • 제출후 다른사람의 코드를 보고 나니, 아래 패턴은 그냥 x^y 로 계산되는 값이라는 것을 알게 되었다..; 구현하느라 엄청 삽질했는데.. 아무튼 이렇게 하면 O(1)에 특정 좌표의 그런디 수를 계산 가능하다. N개의 말에 대해 각각 그런디수를 계산해서 xor하는것은 총 O(N)이 걸린다.

코드

"""Solution code for "BOJ 16879. 궁전 게임".

- Problem link: https://www.acmicpc.net/problem/16879
- Solution link: http://www.teferi.net/ps/problems/boj/16879

Tags: [Sprague-Grundy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    grundy_num = 0
    for _ in range(N):
        x, y = [int(x) for x in sys.stdin.readline().split()]
        grundy_num ^= ((x // 3) ^ (y // 3)) * 3 + (x + y) % 3
    print('koosaga' if grundy_num else 'cubelover')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
A G U Q K
 
ps/problems/boj/16879.txt · 마지막으로 수정됨: 2022/06/07 16:01 저자 teferi