No.153 石の山

c++ yukicoder

No.153 石の山 - yukicoder

  • grundy 数を使う問題。
  • 分割によって複数の「山」ができてしまうが、grundy(A and B) = grundy(A) xor grund(B) なので vector などで状態を持たせなくても大丈夫。
  • Nim に帰着できないか...的なことを考えてしまった。(grundy 数を考えて解けるってことは頑張ればできなくもないのかもだけど)
  • 最初に計算量込みで grundy 数を考えるようにするとよいのかも。
class PilesOfStones {
public:
    // grundy 数で解く
    void solve(void) {
            int N;
            cin>>N;
            map<int,int> memo;
            function<int(int)> grundy = [&](int n) {
                if (memo.count(n))
                    return memo[n];
                if (n <= 1)
                    return 0;
                set<int> S;
                if (n%2 == 0)
                    S.insert(grundy(n/2) ^ grundy(n/2));
                if (n%2 == 1)
                    S.insert(grundy(n/2) ^ grundy(n/2+1));
                if (n%3 == 0)
                    S.insert(grundy(n/3) ^ grundy(n/3) ^ grundy(n/3));
                if (n%3 == 1)
                    S.insert(grundy(n/3) ^ grundy(n/3) ^ grundy(n/3+1));
                if (n%3 == 2)
                    S.insert(grundy(n/3) ^ grundy(n/3+1) ^ grundy(n/3+1));
                int res = 0;
                while (S.count(res))
                    ++res;
                return memo[n] = res;
            };
            if (grundy(N))
                cout<<"A"<<endl;
            else
                cout<<"B"<<endl;
    }
};