ターン数の上限に惑わされる問題。
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; }
まとめ
こういうのサラッと思いつきたいな。