yukicoder No.153 石の山

問題

問題概要

省略

解法

grundy数をメモか再起で求めることにした。 この問題は山が分裂していくが、山が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。
grundy数の求め方だが、
grundy数は
-負けの状態で0
-遷移先のGrundy数に含まれない最小の整数
なので、状態遷移先を列挙していき、最小のgrundy数を求めに行けばいい。 負け状態は一つの山についてみれば、石が一つで回ってきた時だから、x=1の時、grundy数=0とすればいい。

ミス

問題文通りに実装した感じ。なんかプロたちのコードを見てたけど、いろいろ省略されていて、ぽげーて感じ。どうして、すぐに省略できることにきずけるのか。

コード

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int dp[110];

int grundy(int x){
    if(dp[x] != -1)return dp[x];
    if(x == 1)return dp[x] = 0;//負け状態

    set<int> s;
    //状態遷移先
    if(x % 2 == 0 && x >= 2) s.insert(grundy(x / 2) ^ grundy(x / 2));
    if(x % 2 == 1 && x >= 3) s.insert(grundy(x / 2) ^ grundy(x / 2 + 1));
    if(x % 3 == 0 && x >= 3) s.insert(grundy(x / 3) ^ grundy(x / 3) ^ grundy(x / 3));
    if(x % 3 == 1 && x >= 4) s.insert(grundy(x / 3) ^ grundy(x / 3) ^ grundy(x / 3 + 1));
    if(x % 3 == 2 && x >= 5) s.insert(grundy(x / 3) ^ grundy(x / 3 + 1) ^ grundy(x / 3 + 1));

    int res = 0;
    while(s.count(res)) res++;
    return dp[x] = res;
}

int main(void){
    rep(i, 110) dp[i] = -1;
    int n; cin >> n;

    if(grundy(n) == 0){
        printf("B\n");
    }else{
        printf("A\n");
    }
    return 0;
}