mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 038 C - 茶碗と豆

AtCoder Regular Contest 038に参加。B問題までしか解けませんでした…辛い…

解法

基本的なアイデア(grundy数とか)はこちらを参考にしました。
http://www.slideshare.net/chokudai
104点解法がよくわからなかったのでそっちをメインに説明したいと思います。
104点解法では各i(i=1〜N)についてg[i-C[i]]〜g[i-1]に0からどこまでの値があるのかを高速に求めなければなりません。そのために,次のような配列を考えます。

index[g] := (グランディー数がgであるような数の中で,最も大きい数)

このindexはグランディー数がiになる値を発見するごとにindex[i]を更新していけばわかります。これがわかると,各iについてグランディー数grd[i] = k であるとすると,

index[0]〜index[k]の値がすべてi-C[i]からi-1にすべて収まっている
= index[0]〜index[k]の最小値がi-C[i]以上である

ということになります。これはセグメント木を使うと高速に求めることができます。具体的には以下のような感じです。

まず[0, n)の範囲を考える。
・もし[0, n/2)の最小値(これはセグメント木のdat[0*2+1]でわかる)がi-C[i]より大きければiのグランディー数はn/2以上であるとわかるので,次は[n/2, n)の範囲を調べる。
・そうでなかったら,0〜n/2の少なくとも1つはi-C[i]の座標の範囲の中にグランディー数として入っていないので,g[i]はn/2未満である。そこで,[0, n/2)の範囲を調べる。

…というような感じです。ソースコードでは「以上」ではなくて「より大きい」範囲を調べることによってcalc()でg[i]を一発で求めています。

以下ソースコード
O(n log n)解法

// 0-indexed Segment Tree
template<typename T>
class seg_tree {
public:
    void init(vector<T>& v) {
        init(&v[0], (int)v.size());
    }

    void init(T* d, int size) {
        n = 1;
        while (n < size) n <<= 1;
        dat.resize(2*n-1);
        fill(dat.begin(), dat.end(), -1);
        for (int i = 0; i < size; i++) dat[n-1+i] = d[i];
        for (int i = n-2; i >= 0; i--) propagate(i);
    }

    void propagate(int i) {
        dat[i] = min(dat[i*2+1], dat[i*2+2]);
    }

    void update(int k, int val) {
        k += n-1;
        dat[k] = val;
        while (k > 0) {
            k = (k-1) / 2;
            propagate(k);
        }
    }

    int query(int a, int b) {
        return query(a, b, 0, 0, n);
    }

    // [a, b)
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) return dat[k];

        int md = (l+r)/2;
        return min(query(a, b, 2*k+1, l, md), query(a, b, 2*k+2, md, r));
    }

    int calc(int val, int k, int l, int r) {
        if (k >= n-1) {
            if (dat[k] < val) return l;
            else return r;
        }
        int mid = (l+r)/2;
        if (dat[k*2+1] < val) return calc(val, k*2+1, l, mid);
        else return calc(val, k*2+2, mid, r);
    }

    int size() const {
        return n;
    }

private:
    vector<int> dat;
    int n;
};

const int MAXN = 1e5+5;
int g[MAXN];
int c[MAXN], a[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> c[i] >> a[i];
    }
    vector<int> v(N, -1);
    seg_tree<int> seg;
    seg.init(v);
    seg.update(0, 0);
    for (int i = 1; i < N; i++) {
        g[i] = seg.calc(i-c[i], 0, 0, seg.size());
        seg.update(g[i], i);
    }
    int x = 0;
    for (int i = 1; i < N; i++) if (a[i]%2) x ^= g[i];
    if (x == 0) cout << "Second" << endl;
    else cout << "First" << endl;
    return 0;
}

O(n^2)解法

int N;
const int MAXN = 111111;
int C[MAXN], A[MAXN];

int g[MAXN];

int grundy(int cur) {
    if (g[cur] >= 0) return g[cur];
    set<int> S;
    for (int i = 1; i <= C[cur]; i++) {
        S.insert(grundy(cur-i));
    }
    int& ret = g[cur];
    ret = 0;
    for (int el : S) {
        if (ret < el) break;
        ret++;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    if (N > 1000) return 0;
    for (int i = 1; i < N; i++) {
        cin >> C[i] >> A[i];
        A[i] %= 2;
    }
    memset(g, -1, sizeof(g));
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (A[i]) ans ^= grundy(i);
    }
    if (ans != 0) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}