AtCoder ARC #138 (大和証券プログラミングコンテスト2022 Spring) : C - Rotate and Play Game

完全にDにしてやられた…。
https://atcoder.jp/contests/arc138/tasks/arc138_c

問題

N要素の数列Aに対し、以下の2人ターン制ゲームを行う。

• 先手はAから1つ任意の要素を選び、それを取り除く。
• 後手はAの先頭要素を選び、それを取り除く。

先手は選んだ要素の総和を最大化したい。
事前にAをRotateできる場合、Rotateする要素数と、先手の選んだ要素の総和を求めよ。

解法

先手がAのうち上位(N/2)個を取ることができれば、これは明らかに最大である。
後手が取るものを"("、先手が取る要素を")"で置き換えた文字列Sを考える。
Sをrotateし、Regular Bracket Expressionにすることができれば、先手は対応するように上位(N/2)要素を取ることができる。

SをrotateしてRegular Bracket Expressionにするのは容易で、Sのprefixを見て(開き括弧)-(閉じ括弧)が最小の位置が先頭に来るようにRotateすればよい。

int N;
ll A[404040];
vector<pair<int,int>> V;
ll S;
int B[404040];
int D[404040];
void solve() {
	int i,j,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		V.push_back({-A[i],i});
		B[i]=1;
	}
	sort(ALL(V));
	FOR(i,N/2) {
		x=V[i].second;
		S+=A[x];
		B[x]=-1;
	}
	
	int mi=0,k=0;
	FOR(i,N) {
		D[i+1]=D[i]+B[i];
		if(D[i+1]<mi) {
			mi=D[i+1];
			k=i;
		}
	}
	cout<<k<<" "<<S<<endl;
	
}

まとめ

Dで時間食ったのがまずかった。