kmjp's blog

競技プログラミング参加記です

Codeforces Global Round 9 : F. Integer Game

ターン数の上限に惑わされる問題。
https://codeforces.com/contest/1375/problem/F

問題

3つの異なる正整数を初期値とする変数a,b,cがある。
ここで2人でゲームを行う。
毎ターン、先手は任意の正整数を指定し、後手はそれをどこかの変数に足しこむ。
その際、各ターン、直前のターンと同じ変数に足しこんではならない。

後手が2変数を同じ値にしたら先手の勝ち、後手が1000ターン逃げ切ったら後手の勝ちとする。
最適手を取ったとき、先手後手どちらが勝つか答え、実際にその手順を答えよ。

解法

先手が常に3ターン以内で勝つ。
3変数が等差数列を成し、かつ最大値が直前のターンで操作済みという状態に持ち込めば先手の勝ちとなる。
初手で適当な大きな値を与えよう。
その結果3変数がa<b<cとなったとする。この時、次はcを選ぶことはできない。次に(2c-b-a)与えよう。

  • 後手がaに足しこんだとき、3変数の値はb,c,2c-bとなる。これは先手必勝のパターンである。
  • 後手がbに足しこんだとき、3変数の値はa,c,2c-aとなる。これは先手必勝のパターンである。
ll A[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0]>>A[1]>>A[2];
	cout<<"First"<<endl;
	cout<<(1LL<<35)<<endl;
	cin>>x;
	x--;
	A[x]+=1LL<<35;
	ll dif=A[x]*2-A[(x+1)%3]-A[(x+2)%3];
	cout<<dif<<endl;
	cin>>x;
	x--;
	A[x]+=dif;
	sort(A,A+3);
	assert(A[0]+A[2]==2*A[1]);
	cout<<A[2]-A[1]<<endl;
}

まとめ

こういうのサラッと思いつきたいな。