AtCoder ABC #325 (キーエンスプログラミングコンテスト2023秋) : G - offence

初手で方針間違ったのが痛い。
https://atcoder.jp/contests/abc325/tasks/abc325_g

問題

N文字の文字列Sと整数Kが与えられる。
S中に"of"が連続した箇所があった場合、そのofとそれに続くK文字以内の文字を削除できる。
最適な削除の仕方をした時、Sを最小何文字にできるか。

解法

dp(L,R) := 部分文字列S[L...(R-1)]を最小何文字にできるか
を考える。求めたいのはdp(0,N)である。
区間長が短い順にdp(L,R)を埋めることを考える。

• 中を消さない場合、dp(L,R) =R-Lである。
• どこかでS[L...(R-1)]を分割した場合、dp(L,R) = min(dp(L,M)+dp(M,R))となるので、まずそのようなMを総当たりする。
• S[L]='o', S[M]='f'かつdp(L+1,M)=0の場合、S[M]以降の文字列をK個消せるので、dp(L,R)をmax(0,dp(M+1,R)-K)とできる。

int N,K;
string S;

int dp[303][303];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	N=S.size();
	
	for(int len=0;len<=N;len++) {
		for(x=0;x+len<=N;x++) {
			dp[x][x+len]=len;
			for(y=x+1;y<x+len;y++) chmin(dp[x][x+len],dp[x][y]+dp[y][x+len]);
			if(S[x]=='o') {
				for(y=x+1;y<x+len;y++) if(dp[x+1][y]==0&&S[y]=='f') chmin(dp[x][x+len],max(0,dp[y+1][x+len]-K));
			}
		}
	}
	cout<<dp[0][N]<<endl;
}

まとめ

結構短く書けたんでないかな。