CSAcademy Round #81 : D. Gerrymandering

あと1問解きたかったね。
https://csacademy.com/contest/round-81/task/gerrymandering/

問題

N個の街が並んでいる。
それぞれの街は２種類の属性を持つ。

• 1つはAかBかどちらかである。
• もう1つはSかLかどちらかである。

これらの街の列を、いくつかの連続した部分列に分けたい。
その際、各部分列にはLを持つ街がちょうど1つなければならない。
上記条件を満たす部分列の分け方について、Aの属性を持つ街がBの属性を持つ街の数以上である部分列の数を最大化せよ。

解法

貪欲法で解く。
Lの属性を持つ街があるとき、右端をどこまで伸ばすかを考えよう。
もし途中で今見ている街がAが半数以上になるタイミングがあるなら、その街は条件を満たすようにする。
条件を満たす場合、満たさない場合、それぞれ右端をどこにすると次の部分列にAをより多く残せるかを考えていけばよい。

int N;
int A[101010],L[101010];
int S[101010];

int ret;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		A[i]=s=="A";
		S[i+1]=S[i]+(A[i]?1:-1);
		cin>>s;
		L[i]=(s=="L");
	}
	
	int cur=0,nex;
	FOR(cur,N) if(L[cur]) break;
	int dif=S[cur+1];
	while(cur<N) {
		int ok=dif>=0;
		for(nex=cur+1;nex<N;nex++) if(L[nex]) break;
		
		if(nex==N) {
			dif+=S[N]-S[cur+1];
			if(dif>=0) ret++;
			break;
		}
		int best[2]={-100000,-100000};
		best[ok]=S[nex+1]-S[cur+1];
		while(cur<nex) {
			cur++;
			if(cur==nex) break;
			if(A[cur]) dif++;
			else dif--;
			best[dif>=0]=max(best[dif>=0],S[nex+1]-S[cur+1]);
		}
		
		if(best[1]>-100000) {
			ret++;
			dif=best[1];
		}
		else dif=best[0];
	}
	cout<<ret<<endl;
	
}

まとめ

貪欲法でいいと気づくまでちょっと手間取るね。