yukicoder : No.2076 Concon Substrings (ConVersion)

どうやったらこういう問題思いつくんだろ。
https://yukicoder.me/problems/no/2076

問題

文字列Sが与えられる。
Sに対し以下の処理を行う。

• 奇数回目は、S中で"con"がA個連続する箇所を1つ選び、"coon"に置換する。
• 偶数回目は、S中で"con"がB個連続する箇所を1つ選び、"coon"に置換する。

最大何回処理できるか。

解法

dp(n) := 奇数回目の処理をn回行う場合、偶数回目の処理を行える最大回数
とする。解は、dp(n)≧n-1であるnにおけるn+min(n,dp(n))の最大値となる。

あとはdp(n)を考えよう。
"con"が連続している箇所ごとに考える。
仮にL回"con"が連続している場合、A個の連続をi回、B個の連続を(L-A*i)/B回取り除ける、と考えて上記dp(n)のテーブルを更新しよう。
一見計算量が多いか、O(|S|^2)程度で計算でき間に合う。

int N,A,B;
string S;

int dp[130000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(dp);
	cin>>N>>A>>B>>S;
	string T;
	FORR(c,S) {
		T+=c;
		if(T.size()>=3&&T.substr(T.size()-3)=="con") {
			T.pop_back();
			T.pop_back();
			T.pop_back();
			T+="X";
		}
	}
	vector<int> L;
	int cur=0;
	FORR(c,T) {
		if(c=='X') cur++;
		else if(cur) {
			L.push_back(cur);
			cur=0;
		}
	}
	if(cur) L.push_back(cur);
	dp[0]=0;
	FORR(n,L) {
		for(i=12505;i>=0;i--) if(dp[i]>=0) {
			for(x=n/A;x>=0;x--) {
				y=(n-x*A)/B;
				dp[i+x]=max(dp[i+x],dp[i]+y);
			}
		}
	}
	int ma=0;
	FOR(i,12505) if(dp[i]>=i-1) ma=max(ma,i+min(dp[i],i));
	cout<<ma<<endl;
}

まとめ

なんで"concon"を"coon"にしようとかいう問題を考えつくんだろう…。