약수 지우기 게임 2

• DP를 이용해서 각각의 포지션에 대한 승패여부를 모두 구해줘야 한다
• 하지만 남아있는 자연수의 집합이 포지션에 대응되므로, 포지션의 갯수가 모두 2^n 개가 된다. 한 포지션에서 취할수 있는 행동은 n가지이므로 시간복잡도는 O(n*2^n)이 되는데 n이 최대 30이라서 이 방법을 그대로 사용하기에는 무리가 있다.
• 관찰하면 2^n의 포지션중에서 상당수는 실제로 도달 불가능한 포지션이라는 것을 알수 있다. [2,4,8] 에서 시작했을경우, 2를 안지운채로 4나 8만 지운다거나 하는것을 불가능하다. 여기에서 도달할수 있는 포지션은 [4,8], [8], [] 뿐이다. 그래서 bottom-up dp 대신에 top-down dp를 사용하면 시간복잡도는 O(n*2^n)일지라도 실제로 훨씬 빨리 동작하게 된다.
• 비트마스크를 이용해서 포지션을 표현하면 빠르게 동작하게 할수 있다. set을 이용해도 통과하긴 했지만, set은 약 7초, 비트마스킹은 약 2초가 걸렸다.
• 약수배수 관계가 없는 숫자들을 다른 그룹으로 묶은 다음, 각 그룹에 대해서 계산해준다면 훨씬 빠르게 동작시킬수도 있다. [2,3,4,5,6,7]이 주어졌을때 [2,3,4,6], [5], [7]의 그룹들로 묶어서 각각 그런디수를 구하고 xor해서 전체의 그런디수를 구하는 방식이다. 지수 시간복잡도이므로, 그룹 사이즈를 조금만 줄여도 시간이 훨씬 줄어들게 된다. 귀찮아서 이 방법을 직접 구현하지는 않았지만, 제출된 코드중 이 방식을 사용한 코드가 내 코드보다 10배 이상 빠른것을 확인했다.

"""Solution code for "BOJ 12108. 약수 지우기 게임 2".

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

Tags: [game theory]
"""

import functools


def iter_bitset(bitset):
    while bitset:
        lsb = bitset & -bitset
        yield lsb.bit_length() - 1
        bitset -= lsb


def main():
    @functools.cache
    def is_win_pos(pos):
        for num in iter_bitset(pos):
            if not is_win_pos(pos & ~divisors[num]):
                return True
        return False

    N = int(input())  # pylint: disable=unused-variable
    X = [int(x) for x in input().split()]

    divisors = {}
    for x_i in X:
        divisors[x_i] = sum(1 << n for n in X if x_i % n == 0)
    a_pos = sum(1 << n for n in X)

    for a_take in X:
        answer = []
        b_pos = a_pos - divisors[a_take]
        for b_take in iter_bitset(b_pos):
            if not is_win_pos(b_pos & ~divisors[b_take]):
                answer.append(b_take)

        print(f'({a_take}) ', end='')
        print(*answer if answer else 'A')


if __name__ == '__main__':
    main()