yukicoder : No.2145 Segment +-

これは気付けないなぁ…。
https://yukicoder.me/problems/no/2145

問題

N要素の整数列Aが与えられる。
各要素は1か-1であり、一部の要素は値が固定されていて、その他の要素は1か-1か任意に選択できるものとする。

f(A)を以下のように定義したとき、f(A)の最小値を求めよ。

• 任意の区間[L,R]を選んで、A[L...R]の符号を反転する処理を繰り返し、Aのprefix sumが常に0以上となるようにしたい。f(A)は処理の最小回数

解法

詳細はEditorialに任せるとして、Aを問わずf(A)はO(logN)で抑えられる。
よって、以下のようにする。
dp(n,r) := n要素目まで見たとき、現在r回符号反転を行った状態であるとき、A[0...n]のprefix sumの最大値
あとは符号反転回数の追加の有無と、Aの値を決めながらDPしていく。

int N;
string S;

int dp[202020][50];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N+2) FOR(j,50) dp[i][j]=-1<<20;
	dp[0][0]=0;
	FOR(i,N) {
		int add[2]={1,1};
		if(S[i]=='+') add[1]=-1;
		if(S[i]=='-') add[0]=-1;
		FOR(j,49) {
			//same
			int d=dp[i][j]+add[j%2];
			if(d>=0) chmax(dp[i+1][j],d);
			//other
			d=dp[i][j]+add[(j+1)%2];
			if(d>=0) chmax(dp[i+1][j+1],d);
		}
	}
	FOR(i,49) if(dp[N][i]>=0) {
		cout<<(i+1)/2<<endl;
		return;
	}
	
}

まとめ

O(logN)回で抑えられると気付くの、結構敷居高くない…？