SRM526 Div1 Medium(500) PrimeCompositeGame

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;
}};