SRM575 Div2 Medium "TheNumberGameDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12497
訳
ジョンとブロスが数字を使ったゲームを行う。
このゲームは正の整数nからスタートする。
ジョンのターンから始まり、2人交互にターンが回ってくる。
各ターンは次のようにする。
ターンが回ってきたときの数字がCだとする。
そのターンのプレイヤーはCの正の約数を1,C以外から選ぶ。
そしてその約数をCから引く。
その結果が次のターンで対戦相手が扱う数字となる。
もし、この動作を行う事が出来なければ、そのプレイヤーの負けとなる。
n=15としてゲームの一連の流れの例を示す。
15でジョンのターン。3を選ぶ。15-3=12 12でブロスのターン。4を選ぶ。12-4=8 8 でジョンのターン。2を選ぶ。8-2 =6 6 でブロスのターン。3を選ぶ。6-3 =3 3 でジョンのターン。約数が1,3しかないのでジョンの負け!
nが与えられる。また、両プレイヤーが最善を尽くすと仮定する。
どちらのプレイヤーが勝つかを返せ。
制約
1 <= n <= 1000
考えた事
自分のターンで素数が回ってきたら負けだな。
まずdpを素数=負けで初期化しとく。
あとはゲームの問題にありがちなdp更新をする。
相手が負けになるような動き方があれば勝ち。
どう動いても相手が勝ちになれば負け。
ソースコード
class TheNumberGameDivTwo { public: string find(int n){ bool win[1001]; memset( win, false, sizeof(win) ); // 素数だけ負け for( int i = 2; i <= 1000; i++ ){ if( win[i] ) continue; for( int j = i + i; j <= 1000; j += i ){ win[j] = true; } } for( int i = 2; i <= 1000; i++ ){ if( !win[i] ) continue; // どの素因数を引いても勝ちの場合は負け bool ok = false; for( int j = 2; j < i; j++ ){ if( i % j ) continue; if( !win[i-j] ) ok = true; } if( !ok ) win[i] = false; } return win[n] ? "John" : "Brus"; } };