AtCoder ABC #206 : F - Interval Game 2

Eの方がはるかに難しかった。
https://atcoder.jp/contests/abc206/tasks/abc206_f

問題

N個の1次元区間が与えられ、2人でゲームを行う。
2人交互に1つ区間を選ぶが、すでに選ばれた区間と重複部分がある区間は選べない。
自分の手番で、選べる区間がなくなると負けである。
最適手を取ったとき、勝者は先手後手どちらか。

解法

開いている区間に対し、Grundy数を求めよう。
状態となる区間の両端の組み合わせがO(N^2)、選ぶ区間がO(N)なので、全体でO(N^3)で処理できる。

int T;
int N;
int L[101],R[101];
int gr[101][101];

int hoge(int AL,int AR) {
	if(gr[AL][AR]>=0) return gr[AL][AR];
	gr[AL][AR]=0;
	
	int i;
	set<int> S;
	FOR(i,N) if(AL<=L[i]&&R[i]<=AR) {
		int x=hoge(AL,L[i]);
		int y=hoge(R[i],AR);
		S.insert(x^y);
	}
	
	while(S.count(gr[AL][AR])) gr[AL][AR]++;
	return gr[AL][AR];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>L[i]>>R[i];
			L[i]--,R[i]--;
		}
		MINUS(gr);
		if(hoge(0,100)==0) cout<<"Bob"<<endl;
		else cout<<"Alice"<<endl;
	}
}

まとめ

Eに14分かかって、Fに5分弱…。