【yukicoder】No.7 プライムナンバーゲーム

yukicoderさんの問題

No.7 プライムナンバーゲーム - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方***

・実装***

・面白さ***

ヒント(カーソル合わせると見れます)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//整数nに対して引く可能性のある素数を全て試して最終的に勝てるパターンが1つでもあるならWin
//深さ優先全探索+メモ化再帰でこれを行う
//dfs(n, 先攻) はdfs(n-素数, 後攻)のどれかがLoseならWinになる

//素数保存用vector
vector<int> vp;

//n以下の素数作成用関数
//エラトステネスの篩
void MakePrimeNumber(int n){
    vp.clear();
    int tmp[n+1];
    FOR(i, 0, n+1) tmp[i] = 1;
    FOR(i, 2, n+1){
        if(tmp[i]==0) continue;
        vp.push_back(i);
        int j = i;
        while(j <= n){
            tmp[j] = 0;
            j += i;
        }
    }
}

//メモ化再帰
int dp[10001][2];
int dfs(int n, int me){
    //計算済みならdpを返す
    if(dp[n][me]!=-1) return dp[n][me];

    //前の人が1,0にした場合
    //前の人が負けになる
    //me=1(自分)なら自分は勝ちそうでないなら負けパターンだったということ
    if(n==1 || n==0) return me == 1 ? 1 : 0;

    //引ける素数全探索
    int j = 0;
    int ret = 0;
    while(1){
        //前の人が勝ちなら今の人が負け
        //前の人が負けなら今の人は勝ちなので"!"dfs
        if(n-vp[j]>=2) ret = ret || !dfs(n-vp[j], (me+1)%2);
        else break;
        j++;
        //素数の上限に達したらbreak
        if(j==vp.size()) break;
    }
    return dp[n][me] = ret;
}

int main(){
  int N;
  cin >> N;
  //素数生成
  MakePrimeNumber(N);
  //配列初期化
  FOR(i, 0, 10001) FOR(j, 0, 2) dp[i][j] = -1;
  cout << (dfs(N, 1)==1 ? "Win" : "Lose") << endl;
}

コメント

ゲームでお互い最善を尽くす系の問題.
深さ優先全探索を使う問題.
最善を尽くすをどう表現すれば良いか悩んだ何回かWAを出してしまった.
お互いベストを尽くすので勝てるパターンが一つでもあれば勝ち(ゲーム木を書くとわかりやすい).
また、メモ化再帰を使わないとLTEになる??.
素数を求めるのはエラトステネスの篩が早いです.