AtCoder Regular Contest 038 C: 茶碗と豆（grundy数・セグメント木・二分探索）

問題

arc038.contest.atcoder.jp

解法

kmjp.hatenablog.jp

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int N = sc.nextInt();
	int[] C = new int[N];
	boolean[] A = new boolean[N];
	for (int i = 1; i < N; i++) {
	    C[i] = sc.nextInt();
	    A[i] = sc.nextInt() % 2 == 1;
	}
	sc.close();
	SegTree segTree = new SegTree(N);
	segTree.update(0, 0);

	int ans = 0;
	for (int i = 1; i < N; i++) {
	    int grundy = segTree.searchGrundy(i, C[i]);
	    segTree.update(grundy, i);
	    if (A[i]) {
		ans ^= grundy;
	    }
	}
	if (ans == 0) {
	    System.out.println("Second");
	} else {
	    System.out.println("First");
	}

    }

}

class SegTree {
    int N;
    int[] seg;

    public SegTree(int N) {
	this.N = Integer.highestOneBit(N) * 2;
	seg = new int[this.N * 2];
	Arrays.fill(seg, -1);
    }

    public void update(int grundy, int i) {
	grundy += N - 1;
	seg[grundy] = i;
	while (grundy > 0) {
	    grundy = (grundy - 1) / 2;
	    seg[grundy] = Math.min(seg[grundy * 2 + 1], seg[grundy * 2 + 2]);
	}
    }

    public int searchGrundy(int i, int C) {
	int grundy = 0;
	while (N - grundy > 1) {
	    grundy = grundy * 2 + 1;
	    if (seg[grundy] >= i - C) {
		grundy++;
	    }
	}
	return grundy - (N - 1);
    }

}