소수 징글벨

• 스코어링 게임이고, 전형적인 minimax DP 풀이를 생각할 수 있다. n의 범위가 최대 2000 이라서 테스트 케이스가 10개라도 O(n^2) DP풀이를 돌리는 데에는 지장이 없다.
• 점수의 총합이 일정하므로, 선공의 최대 점수만 구해주는 방식을 DP를 짜면 된다. 미리 O(nloglogn) 에 소수목록을 구해놓고 나면, 각 테스트별로 O(n^2)이 걸린다. 제출결과 1136ms 정도가 걸렸다.
• 하지만 좀더 생각하면 그리디하게 최적 전략을 구할수 있다. 일단 현재 상태에서 최대한 많이 점수를 얻는 액션을 선택하는 것이 최선이 된다. 이말은 현재 숫자로부터 A개 안에 소수가 x개 있다면, 그 소수들을 다 포함할수 있는 숫자를 불러야 한다. 그리고, 포함하는 소수들의 갯수가 동일한 경우에는 그중에서 가장 작은 숫자를 불러야 한다. 그래야 상대방이 다음턴에 같은 전략을 썼을때 얻을수 있는 점수를 최소화시킬수 있다. 이것을 정리하면 현재 숫자가 n이라면, n+A 이하에서 가장 큰 소수를 찾아서 그 수를 부르면 된다. [n+1,n+A]범위 안에 소수가 없으면, 그냥 n+1을 부른다.
  • 사실 느낌적으로는 이 전략이 최적이긴 한데, 엄밀한 증명은 하지 못했다.
• 이렇게 그리디하게 전략을 따라간다면, 이제 단순히 이 전략대로 시뮬레이션하면서 점수를 계산해주면 된다. 모든 i에 대해서 i이하의 가장 큰 소수와, i이하의 소수의 갯수를 모두 O(n)에 전처리한다면, 시뮬레이션도 O(n)에 돌릴수 있다. 이렇게 제출했을때 48ms가 걸렸다.

"""Solution code for "BOJ 23633. 소수 징글벨".

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

Tags: [game theory]
"""

from teflib import numtheory


def main():
    T = int(input())
    A_and_B = [[int(x) for x in input().split()] for _ in range(T)]

    max_b = max(b for _, b in A_and_B)
    primes = set(numtheory.prime_list(max_b))

    for a, b in A_and_B:
        max_score = [None] * (b + 1)
        max_score[b] = 0
        remaining_score = 1 if b in primes else 0
        for i in reversed(range(b)):
            if i in primes:
                remaining_score += 1
            max_score[i] = remaining_score - min(
                max_score[j] for j in range(i + 1, min(i + a, b) + 1)
            )

        first_score = max_score[0]
        second_score = remaining_score - first_score
        if first_score > second_score:
            print('kuro')
        elif first_score < second_score:
            print('siro')
        else:
            print('draw')


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 23633. 소수 징글벨".

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

Tags: [game theory]
"""

from teflib import numtheory

FIRST = 0
SECOND = 1


def main():
    T = int(input())
    A_and_B = [[int(x) for x in input().split()] for _ in range(T)]

    max_b = max(b for _, b in A_and_B)
    primes = set(numtheory.prime_list(max_b))

    last_prime = [0] * (max_b + 1)
    prime_count = [0] * (max_b + 1)
    lp, count = -1, 0
    for i in range(max_b + 1):
        if i in primes:
            lp = last_prime[i] = i
            count = prime_count[i] = count + 1
        else:
            last_prime[i], prime_count[i] = lp, count

    for a, b in A_and_B:
        pos = 0
        score = [0, 0]
        turn = FIRST
        while pos < b:
            lp = last_prime[min(pos + a, b)]
            if lp <= pos:
                pos += 1
            else:
                score[turn] += prime_count[lp] - prime_count[pos]
                pos = lp
            turn = 1 - turn

        if score[FIRST] > score[SECOND]:
            print('kuro')
        elif score[FIRST] < score[SECOND]:
            print('siro')
        else:
            print('draw')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list