必勝法

A multiplication game
http://acm.uva.es/p/v8/847.html

p=1から始めて，スタン，オリーが交互に2から9の好きな数字をかけて，先にnに達した方が勝ちというゲームがある．nが与えられたときに，どちらが勝つかを求める問題．二人とも最善の手を採ることが保障されている．

この手の問題は正直苦手なんだけど，この問題は割と簡単．二人とも，とにかくnに達したいわけだから，大きな数字をどんどんかけていく．一方で，相手がnに達してしまうと負けになるのだから，小さな数字をかけるという戦略もある．つまり，攻めの場合と守りの場合に分けて考えれば良い．2から9まで選べるけれど，実際には2と9しか考えない．

プログラムは次のようになる．

while(true) {
　　// Stan's turn
　　pStan *= 9;
　　pOllie *= 2;

　　if(pStan >= n) {
　　　　cout << "Stan wins." << endl;
　　　　break;
　　}

　　// Ollie's turn
　　pStan *= 2;
　　pOllie *= 9;

　　if(pOllie >= n) {
　　　　cout << "Ollie wins." << endl;
　　　　break;
　　}
}

スタンのターンとオリーのターンそれぞれにおいて，pStanはスタンが攻めている場合のp，pOllieはオリーが攻めている場合のpである．nに達するのが目的なのだから，自分はひたすらnに達するように，相手に対してはひたすらnに達しないようにするしかない．2つの場合を同時にシミュレートすると，結果論だけど先にnに達した方の戦略が良かったってことになる．