[C++] 백준 19595번 소수 게임

문제

Alice와 Bob은 "소수 게임"을 즐겨한다.

소수 게임에서는 두 사람이 먼저 일정한 양의 정수 구간 (interval)을 먼저 고르고, 해당 구간에 속한 모든 정수 각각에 대해 미니 게임을 한 번씩 플레이 한다.

정확한 규칙은 아래와 같다.

먼저, Alice가 두 개의 정수 A, k를 고른다 (이 때 2 ≤ k ≤ A-1 을 만족해야 한다).
k는 미니 게임을 몇 번 할지를 결정하고, A는 정수 구간의 상한값을 결정한다.
다음으로 Bob이 2 ≤ x ≤ A + 1 - k를 만족하는 정수 x를 고른다.
x는 정수 구간의 하한값을 결정한다. 즉, x ≤ 정수구간 ≤ A가 된다.
두 사람은 이제 미니 게임을 k번 플레이 하는데, x이상 x+k-1 이하의 정수 각각에 대하여 아래 미니 게임을 플레이한다 (각각의 미니 게임에서 고른 정수를 N이라 하자).
먼저, N을 종이에 적는다 (x ≤ N ≤ x+k-1). 그리고 Alice와 Bob이 번갈아 플레이 한다.
Alice가 먼저 시작하여 종이에 적힌 숫자보다 크지 않은 수 중 소수 (prime) P를 고른다.
종이에 적힌 수가 X라면, 이를 지우고 X-P를 종이에 새로 적는다.
Bob의 차례가 되어 이를 반복한다.
만약 자신의 차례가 되었을 때 종이에 적힌 수가 0이나 1이라면 진다. (다시 말해, X-P를 종이에 적을 때 이 값이 0이나 1이면 이긴다.)
예를 들어 N = 8 이라면, Alice가 자신의 처음 차례에 7을 고르면 이긴다.

N = 10이라면 Alice가 자신의 차례에 고를 수 있는 소수는 2, 3, 5, 7 중 하나이다.

2를 고른 경우, Bob이 자신의 차례에 받는 수는 8이고 이 때 7을 고르면 Bob이 이긴다.
3을 고른 경우, Bob이 자신의 차례에 받는 수는 7이고, 이 때 7을 고르면 Bob이 이긴다.
5를 고른 경우, Bob이 자신의 차례에 받는 수는 5이고, 이 때 5를 고르면 Bob이 이긴다.
7을 고른 경우, Bob이 자신의 차례에 받는 수는 3이고, 이 때 3을 고르면 Bob이 이긴다.
따라서 N = 10인 경우, Bob이 최선을 다한다면 Alice가 이길 방법은 없다. (두 사람은 언제나 최선을 다해서 플레이 한다고 가정하자.)

Bob은 A, k가 주어졌을 때 x를 잘 골라서 자신의 승률을 최대화 하기로 했다. 만약 승률을 최대화 하는 x값이 여럿이라면 그 중 가장 작은 x를 찾기로 했다. Bob을 도와주자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 줄에 A와 k가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 두 개의 정수를 공백으로 구분하여 출력한다.

첫 수는 k번의 게임 중 Bob이 최대 몇 번을 이길 수 있는지 나타내고, 두 번째 수는 이를 위해 Bob이 선택해야하는 x값 중 최소 값을 나타낸다.

풀이

문제를 이해하는데에만 상당히 시간이 소요된 문제이다.
항상 소수를 이용하기때문에 에라토스테네스의 체를 이용해 100000까지의 소수를 미리 prime벡터에 저장해두었다.
dp[x]는 이번턴에 숫자가 x인 사람이 이기는 경우에는 1, 지는 경우에는 0을 저장했다. setDp함수를 통해 prime에서 x보다 작은 소수를 차례로 찾아 0또는 1을 만드는 경우가 하나라도 있다면 1을 저장한다.

이후 2 ≤ x ≤ A + 1 - k중 최소가 되는 x값을 찾으면 되는데 이를 무턱대고 반복문을 돌려 찾으면 시간초과가 난다. 미리 누적합을 계산해 psum에 저장해놓아야 한다.
psum[i] = dp[2]~dp[i]까지의 합

psum을 계산할때 dp의 값을 뒤집었는데 우리가 구하고 싶은 것은 후공인 Bob의 최대 승률이기때문이다. 따라서 뒤집은 dp[x]는 이번턴에 숫자가 x인 사람이 지는 경우에는 1, 지는 경우에는 0을 저장한다.

dp[i]부터 dp[i+k-1]까지의 합을 구하고 싶다면 psum[i+k-1]-psum[i-1]을 통해 구하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int a,k,test;
// 이번턴에 x인 사람이 이기면 1
int dp[100001];
int notprime[100001];
int psum[100001];
vector<int> prime;

void eratos(){
  for (int i=2; i<=sqrt(100000); i++){
    if (notprime[i]) continue;
    for (int j=i*i; j<=100000; j+=i){
      notprime[j] = 1;
    }
  }
  
  for (int i=2; i<=100000; i++)
    if (!notprime[i]) 
      prime.push_back(i);
}

int setDp(int x){

  int &ret = dp[x];
  if (ret != -1) return ret;
  
  ret = 0;

  int idx = lower_bound(prime.begin(), prime.end(),x)-prime.begin();
  if (prime[idx] > x) idx--;

  for (int i=idx; i>=0; i--){
    if (setDp(x-prime[i]) == 0) return ret = 1;
  }
  return ret;
}

void setPsum(){
  for (int i=2; i<=100000; i++)
    dp[i] = !dp[i];

  psum[2] = dp[2];
  for (int i=3; i<=100000; i++){
    psum[i] = psum[i-1]+dp[i];
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  eratos();
  memset(dp,-1,sizeof(dp));
  dp[0] = 0;
  dp[1] = 0;
  for (int i=2; i<=100000; i++){
    setDp(i);
  }
    
  setPsum();

  cin >> test;

  while (test--){

    cin >> a >> k;

    int ans = 0, minx = 100000;
    for (int i=2; i<=a+1-k; i++){
      int ret = psum[i+k-1]-psum[i-1];
      if (ans < ret){
        ans = ret;
        minx = i;
      }
    }

    cout << ans << " " << minx << endl;
  }
}