AtCoder AGC #026 : F - Manju Game

これは自力は厳しそう。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_f

問題

１列にN個並んだ数字を取りあうゲームを行う。
先手は任意の数字を選びとる。
以降、直前に選ばれた数字のいずれか隣接要素が残っていれば、任意の要素を取る、を繰り返す。
ただし選ぶ隣接要素が残っていない場合、また残された要素のうち任意の要素を取ることができる。

両者自分の取る要素の値の総和を最大化しようとするとき、その値を求めよ。

解法

最初の２手が決まるとあとの手は（隣接要素が残る限り）一意に決まる。
またその際要素を交互に取り合うので、位置の偶奇が重要となる。

Nが偶数の場合、左右両端のいずれかを取れば偶奇いずれかの位置を取り切ることができるので、先手は左右両端のうち自分の総和が大きくなる方を取ればよいので終了。

以下Nが奇数のときを考える。残された要素がa1,b1,a2,b2,...と並んでいるとする。
aの総和を取るのが最適な場合、先手はa1を選べばよく、その時点でゲームは終了する。

そうでない場合、先手はbのいずれかを取る。その場合後手がその両隣のaのいずれかを取る。
その結果、両端の要素は後手がとることになるので、次に任意の位置を選択できるのは常に先手であり、その際残された要素数は常に奇数となる。

先手は、いくつかbを取ったのち、あとは残されたaを取りつくすのが最適と判断した時点でa1を取ればゲームを終了できる。
その際の先手の総和は、sum(残ったa)-sum(残ったb)+sum(元のb)となる。
よって先手はsum(残ったa)-sum(残ったb)を最大化する戦略を考えよう。

これは実際にはX=sum(残ったa)-sum(残ったb)の最大値を二分探索で求める。
数列の先頭２要素a1, b1を見る。

• a1≧Xかつb1≧a1の場合、a1,b1は必ず終了前に取られる。なぜなら先手は大きなb1を取りたいし、後手はa1だけ残すと先手がX以上を得てしまうので、先手がb1を取る際はa1を後手が取らざるを得ないためである。
  • よって、この２要素は無視して残った数列を考えればよい。（EditorialにはXからb1-a1を引くと書いてあるが、おそらく誤り。a1,b1は残さないのでXに寄与しない)
• それ以外の場合、a1,b1は両方とるか両方取られないかのいずれかである。よってa1,b1を消し、代わりにa2がその分a1-b1大きくなったと考えて以後同様の処理を行えばよい。

いずれも数列長を２ずつ減らせるので、最終的に１要素になった際、その値がX以上か判定すればよい。
この二分探索の１ステップはO(N)で行える。

int N;
int A[303030];
ll B[303030];
ll S[2];
int ok(ll v) {
	int i;
	FOR(i,N) B[i]=A[i];
	for(int cur=N-1;cur>0;cur-=2) if(B[cur]<v || B[cur-1]<B[cur]) B[cur-2]+=B[cur]-B[cur-1];
	return B[0]>=v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i%2]+=A[i];
	}
	if(N%2==0) {
		cout<<max(S[0],S[1])<<" "<<min(S[0],S[1])<<endl;
		return;
	}
	
	ll Z=-1LL<<40;
	for(i=40;i>=0;i--) if(ok(Z+(1LL<<i))) Z+=1LL<<i;
	
	cout<<(S[1]+Z)<<" "<<(S[0]-Z)<<endl;
	
	
}

まとめ

考察はグダグダ書いたけどコードは短い。
上の記述はEditorialと変わらなくなってしまった。