AtCoder ARC #116 : F - Deque Game

詰めが甘かった…。
https://atcoder.jp/contests/arc116/tasks/arc116_f

問題

K個の整数列を用いて2人対戦ゲームを行う。
2人は各自の手番で、長さ2以上の数列を1つ選んで、先頭か末尾の要素を1つ取り除く。
全数列、要素数が1になったらゲームを終了する。

残った値の総和について、先手は最大化、後手は最小化するよう最適手を取ると、最終的な総和はどうなるか。

解法

1つの数列について考える。

• 数列が奇数個の時、中心3要素がx,y,zの時、残る値はmin(y,max(x,z))である。
  • まず、後手は先手と反対の手順を取ることで、結果をyにすることができる。ただyが小さくない場合、後手はy以外の値にしようとするが、先手は初手を先頭か末尾か選択することでxかzを強制させることができるので、このようになる。
• 数列が偶数個の時、両端それぞれ取り除いたケースについて、上記値を考え、結果が良い方を取ればよい。

先手と後手が逆の場合、minとmaxが入れ替わるがあとは同じ。
奇数長の数列については、先手が不利なことがわかる。さらに1つ奇数長の数列を処理すると、元の先手は継続して先手となることがわかる。

よって、取る戦略は以下の通り。

• 互いに偶数長の数列がある限り、abs(x-y)の値の大きい順に残るように選択する。
• 最後奇数長の数列が残った場合、毎回同じ側が先手となる前提のもと最適手を取る。

int K;
int N[202020];
deque<int> A[202020];
int L[202020],R[202020];
pair<int,int> C[202020];
int SK;

int F(deque<int>& D) {
	if(D.size()==1) {
		return D[0];
	}
	else {
		int N=D.size();
		int a=D[N/2-1];
		int b=D[N/2];
		int c=D[N/2+1];
		
		if(SK%2==0) {
			return min(b,max(a,c));
		}
		else {
			return max(b,min(a,c));
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	vector<pair<int,int>> cand;
	
	FOR(i,K) {
		cin>>N[i];
		FOR(j,N[i]){
			cin>>x;
			A[i].push_back(x);
		}
		SK+=N[i]-1;
	}
	FOR(i,K) if(N[i]%2==0) {
		x=A[i].back();
		A[i].pop_back();
		C[i].first=F(A[i]);
		A[i].push_back(x);
		x=A[i][0];
		A[i].pop_front();
		C[i].second=F(A[i]);
		
		cand.push_back({abs(C[i].first-C[i].second),i});
	}
	
	int turn=0;
	sort(ALL(cand));
	reverse(ALL(cand));
	ll ret=0;
	FORR2(c,i,cand) {
		if(turn==0) {
			ret+=max(C[i].first,C[i].second);
		}
		else {
			ret+=min(C[i].first,C[i].second);
		}
		turn^=1;
	}
	
	FOR(i,K) if(N[i]%2==1) {
		ret+=F(A[i]);
	}
	
	cout<<ret<<endl;
	
}

まとめ

数列長の偶奇と、中央周辺だけ見ればよい点は正しかったが、偶数長を処理するときだけ交互に手番が入れ替わる点を見逃してしまった…。