Codeforces #668 Div1 D. Game of Pairs

考察が難しめの問題。
https://codeforces.com/contest/1404/problem/D

問題

2人で行うゲームを考える。
正整数Nが与えられる。
先手は、1～2Nの値を2つずつ組にしてN個の組を作る。
後手は、各組から1つずつ数値を選ぶ。

もし選んだ数値の和が2Nの倍数なら後手の勝ちであり、そうでなければ先手の勝ちである。
Nに対し、先手後手どちらが勝つか。
また勝てるなら、先手ならN個の組、後手ならN個の組に対する数値の選び方を求めよ。

解法

• Nが偶数なら先手必勝。
  • mod Nが等しい2値を組にしておくと、N個の組からどう選んでもその総和を2Nで割った余りがNにある。
• Nが奇数なら後手必勝。
  • mod NがバラけるようにN個の組を選ぼう。そうすると、総和を2Nで割った余りが0かNになる。
  • 全体の総和を2Nで割ると余りがNなので、今回選んだN個の総和を2Nで割った余りがNになってしまった場合、各組反対の値を選べば総和を2Nで割った余りが0になる。

int N;
int col[1010101];
int P[1010101];
vector<int> C[505050];
vector<int> E[1010101];

void dfs(int cur,int c) {
	if(col[cur]!=-1) return;
	col[cur]=c;
	FORR(e,E[cur]) dfs(e,c^1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%2==0) {
		cout<<"First"<<endl;
		FOR(i,N) cout<<(i+1)<<" ";
		FOR(i,N) cout<<(i+1)<<" ";
		cout<<endl;
		return;
	}
	
	cout<<"Second"<<endl;
	for(i=1;i<=2*N;i++) {
		cin>>P[i];
		C[P[i]].push_back(i);
	}
	
	for(i=1;i<=N;i++) {
		E[i].push_back(i+N);
		E[i+N].push_back(i);
		E[C[i][0]].push_back(C[i][1]);
		E[C[i][1]].push_back(C[i][0]);
	}
	
	MINUS(col);
	for(i=1;i<=2*N;i++) if(col[i]==-1) dfs(i,0);
	
	ll sum=0;
	for(i=1;i<=2*N;i++) if(col[i]) sum+=i;
	
	x=1;
	if(sum%(2*N)) x=0;
	for(i=1;i<=2*N;i++) if(col[i]==x) cout<<i<<" ";
	cout<<endl;	
	
	
}

まとめ

Dの割にupsolve多め。