SRM526 Div1 Medium(500) PrimeCompositeGame
K=1の場合はシミュレートする。K>=2のとき、2個の素数の間にKより大きな隙間があると、そこに追い込まれて私が負ける。それ以外の場合は2を取られて、Dengklekが負ける。勝つ方はなるべく多く、負ける方はなるべく少なく取れば良い。
#include <string> #include <vector> using namespace std; class PrimeCompositeGame{public: int theOutcome( int N, int K ) { // エラトステネスの篩 vector<bool> P(N+1,true); P[0] = P[1] = false; for ( int i=0; i*i<=N; i++ ) if ( P[i] ) for ( int j=i+i; j<=N; j+=i ) P[j] = false; int ans = 0; if ( K==1 ) { while ( true ) { N--; if ( N<=1 || ans%2==0 && !P[N] || ans%2==1 && P[N] ) break; ans++; } } else { vector<int> G(N+1); for ( int i=2; i<=N; i++ ) G[i] = P[i] ? 0 : G[i-1]+1; bool f = true; // 先手の勝ち for ( int i=2; i<=N; i++ ) if ( G[i]>K ) f = false; if ( N==2 ) f = false; while ( true ) if ( f ) { int k; for ( k=K; ; k-- ) if ( N-k>=2 && P[N-k] ) break; N -= k; ans++; if ( N<=3 ) break; N--; ans++; } else { if ( N==2 || G[N]>K ) break; N--; while ( !P[N] ) N--; ans++; int k; for ( k=1; k<=K; k++ ) if ( G[N-k]>K ) break; if ( k>K ) { k = K; while ( P[N-k] ) k--; } N -= k; ans++; } } return ans%2!=0 ? ans : -ans; }};