AtCoder ABC #278 : G - Generalized Subtraction Game

遅れて参加した割に、Gまでは割とサクサク解けた。
https://atcoder.jp/contests/abc278/tasks/abc278_g

問題

2人対戦型のインタラクティブ問題である。
初期状態でで1～Nの数字が書かれたカードが1枚ずつある。
ここで、2人交互に以下の処理を行う。

• 連続した値を持つカードをL枚以上R枚以下選んで取り除く。もしカードを選べない場合、負けとなる。

N,L,Rが与えられたとき、先手または後手を選び、実際に相手の行動に対し勝利せよ。

解法

F(x) := 連続する番号のカードがx枚ある場合のGrundy数
とすると、それぞれ連続するカード群に対しGrundy数のxorが0となるようふるまえばよい。

F(x)の計算は、適当にやるとO(N^3)かかる。
x-1枚の状態でy-1枚取り除くことと、x枚の状態でy枚取り除く場合は同じ状態になることを用いると、O(N^2*logN)程度に抑えることができるが、O(N^3)でも何とか間に合うのでそこまでしなくても良い。

int N,L,R;
int dp[2020];
pair<int,int> P[2020][5020];
int mask[5050];
int S[2020];

void go(int L,int R) {
	if(L==0&&R==0) {
		exit(0);
	}
	if(L==-1&&R==-1) {
		assert(0);
	}
	int i;
	for(i=L;i<=L+R-1;i++) S[i]=0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(P);
	cin>>N>>L>>R;
	
	for(i=1;i<=N;i++) {
		ZERO(mask);
		FOR(x,i) {
			for(y=L;y<=R&&x+y<=i;y++) {
				j=dp[x]^dp[i-(x+y)];
				P[i][j]={x,y};
				mask[j]=1;
			}
		}
		while(mask[dp[i]]) dp[i]++;
	}
	
	for(i=1;i<=N;i++) S[i]=1;
	if(dp[N]==0) {
		cout<<"Second"<<endl;
		cin>>x>>y;
		go(x,y);
	}
	else {
		cout<<"First"<<endl;
	}
	
	while(1) {
		int nim=0;
		int cur=0;
		int L=-1;
		int R=-1;
		FOR(i,N+2) {
			if(S[i]==0) {
				nim^=dp[cur];
				cur=0;
			}
			else {
				cur++;
			}
		}
		FOR(i,N+2) {
			if(S[i]==0) {
				if((nim^dp[cur])<dp[cur]) {
					auto p=P[cur][nim^dp[cur]];
					L=i-cur+p.first;
					R=p.second;
				}
				cur=0;
			}
			else {
				cur++;
			}
		}
		
		go(L,R);
		cout<<L<<" "<<R<<endl;
		cin>>x>>y;
		go(x,y);
		
		
	}
	
}

まとめ

真似っこ戦術で良かったのか…。