AtCoder Regular Contest 038 C - 茶碗と豆

問題

　 $N$ 個の茶碗が横一列に並んでいる。各茶碗 $i$ には整数 $C_i$ が書かれており、中には $A_i$ 個の豆が入っている。これらを用いて次のゲームを行う。

プレイヤーは自分のターンに茶碗 $0$ 以外の茶碗に入っている豆を1つ選んで取り出す。
茶碗 $i$ から豆を取り出したとき、茶碗 $i - C_i$ ,茶碗 $i - C_i + 1$ , $\dots$ , 茶碗 $i - 1$ のいずれかの茶碗に豆を入れなければならない。
交互にターンを繰り返し、自分のターンに選べる豆がなくなったプレイヤーの負けとなる。

　両プレイヤーが最適な戦略をとったとき、先手と後手のどちらが勝つか判定せよ。

解法

　Grundy数を考える。 $i$ 個目の茶碗に入っている豆を遷移させられるのは $i - C_i$ から $i - 1$ までなので、この区間のGrundy数に含まれない最小の整数が $i$ 番目についてのGrundy数となる。

　これを単純に数えると $O(N^2)$ 以上かかるが、セグメント木を利用して高速化することで $O(N(\log{N})^2)$ で求めることができる。

　具体的な方法としては、まず $i$ 番目のGrundy数を求める状況を考えることとする。セグメント木には各Grundy数に対して、そのGrundy数が $i - 1$ 番目までで最後にどこで出てきたかを記録しておく。

　このセグメント木を利用して、「 $i$ 番目のGrundy数として $x$ が可能かどうか」という二分探索をしていく。セグメント木に $[0, x]$ の範囲でクエリを投げ、 $x$ 以下のGrundy数として最小の出現位置を得る。これが $i - C_i$ より大きかったらつまり $x$ 以下が $i - C_i$ から $i - 1$ の範囲に全て詰まっているということなので $x$ は $i$ 番目のGrundy数にはなれない。逆に小さかったら $x$ 以下のどれかが $i$ 番目のGrundy数として選べる。この判定をもとに二分探索を行うことでこの問題が解ける。

反省

　2時間41分(2WA)でAC。眠気と格闘しながら1時間20分ほど考えたが、そもそもGrundy数という発想がなく全然ダメな考察をしていた。

　そこから解説スライドを見てまず100点分の部分点解法を得る。Grundy数、言われるとなるほどなんだがこれを思いつける気はしない。

　さらに満点を得るためにはセグメント木を実装しなければならず、また他人の提出をいろいろ見てみたところ二分探索部分がセグメント木の中に埋め込まれている？ような感じでよくわからなかった。多少効率は悪いのかもしれないが、セグメント木を用いた値の取得で $O(\log{N})$ 、それを使った二分探索でさらに $O(\log{N})$ かかる実装とした。これでも十分間に合う(222msec)。

　セグメント木として確保する範囲が大きすぎて一度REを出してしまった。理解が浅いのでこういうミスが出るという面もあるのだと思う。

　Grundy数とこのセグメント木による高速化は相性が良さそうに思えるが、典型と言えるんだろうか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = v;
        for (ll i = (x + n_ - 2) / 2; i > 0; i = (i - 1) / 2) {
            nodes_[i] = min(nodes_[2 * i + 1], nodes_[2 * i + 2]);
        }
    }

    ll getMin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return INT_MAX;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll left  = getMin(a, b, 2 * k + 1, l, (l + r) / 2);
        ll right = getMin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(left, right);
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> C(N), A(N);
    C[0] = A[0] = 0;
    ll sum = 0;
    for (ll i = 1; i < N; i++) {
        cin >> C[i] >> A[i];
        sum += A[i];
    }

    constexpr ll MAX = 1e5 + 1;
    SegmentTree st(MAX, -1);

    vector<ll> grundy(N);
    grundy[0] = 0;
    st.update(0, 0);
    for (ll i = 1; i < N; i++) {
        //取り得るgrundy数について2分探索をする
        ll ng = -1, ok = MAX;
        while (ng + 1 != ok) {
            ll mid = (ng + ok) / 2;

            //0からmidまでのgrundy数について,今まで出てきた位置の最小値を求める
            ll min_index = st.getMin(0, mid + 1);
            (min_index >= i - C[i] ? ng = mid : ok = mid);
        }
        grundy[i] = ok;
        st.update(grundy[i], i);
    }

    ll xor_value = 0;
    for (ll i = 1; i < N; i++) {
        if (A[i] % 2) {
            xor_value ^= grundy[i];
        }
    }

    cout << (xor_value == 0 ? "Second" : "First") << endl;
}