SRM574 275

とぷこだ

問題

0を含まない整数AとBがあり、交互に各ターンでそれぞれ以下の2つの操作ができる。
・いまの数字をreverseする(123->321)
・いまの数字/10する(123->12)
2人でそれぞれの数字を操作していくゲームを考える。
このとき、AがBと同じ数字にすることができたらAの勝ち、できなければBの勝ちとなる。
ターン数は1000ターンよりかかってしまう場合はBの勝ちとなる。
互いに最善の操作でゲームを行った時に、どちらが勝つか？

考え方

AとBのとりうる状態は実は多くない。
なので、実際にturnとAとBをメモ化しながら再帰でシミュレーションしてもできる。
最善というのは、今Aならば、どちらかの操作でBが逃げ切れないような手があれば、勝てる。
今Bならば、どちらかの操作でAが必ず勝つ手ががなければ、勝てる。



シンプルな回答は、文字列とみなして、Aの部分文字列にBまたはBのreverseの文字列が含まれるか否かで判定できる。
もし、Bの方がAより長ければ、reverseしつづければBが勝てる。
AとBが同じ長さならば、同じ文字列かreverse文字列でない限り、Aが1文字でもけずれば上記と同じでBが勝てる。
Bの方がAより短い時、部分文字列として含まれる場合、AはBと同じ文字列にするように操作していけば、Bを短くしたとしても同様に繰り返せるので、かならず勝てる。(1000ターンもいらない)

反省

なんか以下のようなひどいコードを書いていたら、挙動が変わってしまっていた。
探索の仕方がよくないようだった。

//ダメ
bool f = false;
if(!solve(1)){
    f = true;
}
if(!solve(2)){
    f = true;
}
if(f){ hoge; }


//通った
if(!solve(1) || !solve(2)){ //solve(2)は!solve(1)がtrueなら呼ばれない
    hoge;
}