yukicoder : No.3147 Parentheses Modification and Rotation (RM Ver.)

こっちはすんなりだった。
https://yukicoder.me/problems/no/3147

問題

N文字の括弧列Sが与えられる。また、整数R,Cが与えられる。
Sに以下の処理を行える時、Sを対応が取れた括弧列にするのに必要な最小コストを求めよ。

• コストRを掛け、Sを右に1文字回転する
• コストCを掛け、S中で指定した1文字を置き換える

解法

Nは偶数であるものとする。
回転回数を総当たりしながら、後者の処理回数を求めよう。
f(i) := Sの各文字を"("なら1、")"なら-1と置き換えた数列における、先頭i要素の総和
g(i) := f(i)のprefix minimum

とすると、閉じ括弧をg(N)だけ開き括弧にしなければならない。
その結果、開き括弧の個数がN/2を超える場合、超過分を閉じ括弧にする必要がある。
よって両者の和から、後者の処理回数の最小値がわかる。

Sをrotateさせていくが、f(i)は事前に累積和を取っておけばよいし、g(N)はf(i)の値をSegTreeに載せれば容易に求められる。

int N;
string S;
ll R,M;

int A[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>R>>M;
	if(N%2) {
		cout<<-1<<endl;
		return;
	}
	S+=S;
	st.update(0,0);
	FOR(i,2*N) {
		A[i+1]=A[i]+((S[i]=='(')?1:-1);
		st.update(i+1,A[i+1]);
	}
	ll ret=1LL<<60;
	FOR(i,N) {
		int cur=A[i];
		int mi=st.getval(i,i+N);
		int las=A[i+N];
		int add=0;
		if(mi<cur) {
			add=(cur-mi+1)/2;
			las+=add*2;
		}
		add+=(las-cur)/2;
		ret=min(ret,1LL*((N-i)%N)*R+1LL*add*M);
	}
	cout<<ret<<endl;
}

まとめ

3416の方がだいぶ難しかったな。