SRM472 Div1 Easy(250), Div2 Medium(500) PotatoGame

PotatoGame

bool PotatoGame::win( int n )
{
    for ( int i=1; i<=n; i*=4 )
        if ( ! win( n - i ) )
            return true;
    return false;
}

こんな感じで探索すると、ジャガイモの個数をnとしてn%5が1, 3, 4なら手番を持っている側が勝ち、0, 2なら相手が勝つことがわかる。
規則性さえ見つかれば証明は数学的帰納法でできる。4^t%5は1か4。n%5が1, 3, 4ならばn mod 5が0か2になるようにして相手に手番を渡すことができる。一方、n%5が0, 2だと、どうしてもn mod 5が1, 3, 4になってしまう。

#include <string>

using namespace std;

class PotatoGame
{
public:
    string theWinner( int n );
};

string PotatoGame::theWinner( int n )
{
    return n%5==1 || n%5==3 || n%5==4 ? "Taro" : "Hanako";
}