WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM575 Div1 Easy "TheNumberGameDivOne"

解法

n=100ぐらいまでの結果を出力して眺めて法則を探すと・・・
nが2の累乗の場合、指数が奇数の場合は負け。偶数なら勝ち
nが2の累乗でなければ、奇数なら負け。偶数なら勝ち
っぽいなと分かる。

証明してみる

数字が奇数だった場合、それを素因数分解すると、
2^0 * 3^a * 5^b * 7^c * 11^d *...となる。
よって約数は必ず奇数となり、
約数を引いたときに出来る数字は必ず偶数となる。
また、元の数字をC = 2^x + n (nは奇数)とすると、
この2^xはどんなnでも割り切れない。
そのため、Cはnの約数にはならないので、nを引いて2^xにすることは出来ない。
よって、約数を引いた後の偶数は2の累乗でない偶数であることがわかる。
2の累乗でない偶数には必ず奇数の約数があるため、
その約数を引けば、奇数にすることができる。
だから奇数→2の累乗でない偶数→奇数→2の累乗でない偶数...
となり、奇数は負け、2の累乗でない偶数は勝ちとなる。

数字が2の累乗であった場合、
数字から約数を引いたときにできる数字は
指数を1つ減らした2の累乗か、2の累乗でない偶数となる。
上記の通り、2の累乗でない偶数を渡すと負けてしまうので、
ゲームの流れは2^8→2^7→2^6→2^5→2^4→2^3→2^2→2^1となる。
2^1になれば負けなので、指数が奇数だったら負け、偶数だったら勝ちとなる。

事後

Div1の難しさが予想の斜め上をいってた


ソースコード

class TheNumberGameDivOne {
public:
    string find(long long n){
        bool firstWin;
        if( n % 2 ){
            firstWin = false;
        }else{
            long long m = 2;
            for( int i = 1; ; m *= 2, i++ ){
                if( n == m ){
                    firstWin = i % 2 == 0;
                    break;
                }else if( n < m ){
                    firstWin = true;
                    break;
                }
            }
        }
        return firstWin ? "John" : "Brus";    
    }
};