[백준] 소수게임 19595 python 풀이

https://www.acmicpc.net/problem/19595

문제설명

문제자체가 이해하기 매우 난해한 문제이다.
예시를 기반으로 설명하도록 하겠다.
먼저 Alice가 A, K 두 숫자를 고른다. (입력으로 주어지는 두 숫자이다.)
다음으로 Bob이 2 ≤ x ≤ A + 1 - k를 만족하는 정수 x를 고른다.
이때, 예를들어 A=12, K=2 라고 생각해보자
그러면 Bob은 2 ≤ x ≤ 12 + 1 - 2 = 11 범위 사이의 숫자를 고를 수 있다.
예를들어 Bob이 8의 숫자를 골랐다고 가정해보자
그러면 8서부터 9까지의 (9=8+k-1) K(=2)번의 미니게임을 진행한다.

미니게임 다음과 같다.
Alice가 먼저 주어진숫자보다 같거나 작은 소수를 정해 주어진숫자에서 뺀다
그다음 Bob이 남은 숫자보다 같거나 작은 소수를 정해 뺀다.
이렇게 빼나갈때 자기차례에서 0또는 1이 남는 사람이 지는 게임이다.
다시말해, 자기차례에서 소수나 소수+1이 나오면 반드시 이기는 게임이다.

숫자 8일때 미니게임을 해보자
Alice가 먼저 7을 뺀다.
Bob차례에서 1이 남았으므로 Bob 패배

숫자 9일때 미니게임을 해보자
Alice가 2,3,5,7 어느 숫자를 빼던간에 Bob이 이기는 것을 알 수 있다.
Bob의 승

그러면 우리가 구해야 할 것은 무엇인가?
Alice가 고른 A, K 두 숫자에 대해 Bob이 2 ≤ x ≤ A + 1 - k 숫자를 고를 수 있는데
Bob의 승률이 가장 커지는, 다시말해 Bob이 가장 많이 이기는 숫자 x중 최솟값을 고르고 그때 Bob이 최대 몇번이기는지 출력하면 된다.

핵심

문제를 풀기위해서는 문제출제자의 여러 의도를 파악할 수 있어야 한다.
항상 주어진 숫자에 대해 Alice가 먼저 시작한다.
다시말해 어떤 게임이든 특정 숫자에 Alice가 이기는지 Bob이 이기는지는 정해져 있다.
⇒ 한번 계산하면 테스트케이스에서 반복 사용 가능

정리중…..

"""
https://www.acmicpc.net/problem/19595
"""
import sys
input = sys.stdin.readline

MAX = 100000

def eratos(n):
    sieve = [True] * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i + i, n, i):
                sieve[j] = False

    return [i for i, flag in enumerate(sieve) if flag == True and i > 1]

prime_num_list = eratos(MAX)

B_win_list = [True for _ in range(MAX + 10)]
B_win_list[0] = False
B_win_list[1] = False

for p in prime_num_list:
    B_win_list[p] = False
    B_win_list[p + 1] = False

for i in range(2, MAX):
    if B_win_list[i]:
        for p in prime_num_list:
            if i + p > MAX: break
            B_win_list[i + p] = False
prefix_sum_list = [0 for _ in range(MAX + 10)]
s = 0
for i in range(2, MAX + 1):
    if B_win_list[i]:
        s += 1
    prefix_sum_list[i] = s

def solve(a, k):
    max_x = a + 1 - k
    max_win_cnt = -1
    idx = 0
    for i in range(2, max_x+1):
        tmp_win_cnt = prefix_sum_list[i+k-1] - prefix_sum_list[i-1]
        if tmp_win_cnt > max_win_cnt:
            max_win_cnt = tmp_win_cnt
            idx = i

    print(max_win_cnt, idx)

for _ in range(int(input())):
    a, k = map(int, input().split())
    solve(a, k)