kmjp's blog

競技プログラミング参加記です

yukicoder : No.291 黒い文字列

ブログ書いてお風呂入る時間ができるの珍しい。
http://yukicoder.me/problems/622

問題

アルファベット大文字または'?'で構成されたL文字の文字列Sがある。
'?'は任意のアルファベット1文字に置き換えることができる。

Sから"KUROI"という部分文字列を最大何個抽出できるか。
なお、部分文字列は元の文字列で連続でなくてもよいが並び順は変えてはいけない。
また同じ位置の文字は複数回利用できない。

解法

K,U,R,O,Iの何文字目までマッチしたものが何個あるかをカウントして先頭からDPしていこう。
dp[何文字目][Oまでマッチした部分文字列数][Rまで(略)][Uまで(略)][Kまで(略)] := (Iまでマッチした部分文字列数の最大値)

KUROI全部マッチするのは最大でもL/5なので、各文字のマッチ数は高々20までチェックすればよい。
そのため一見O(L^5)だが割と解ける。

int L;
string S;
int dp[2][21][21][21][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int a,b,c,d,e;
	cin>>S;
	L=S.size();
	
	ZERO(dp);
	MINUS(dp);
	int ma=0;
	dp[0][0][0][0][0]=0;
	
	FOR(i,L) {
		int cur=i%2,tar=cur^1;
		memmove(dp[tar],dp[cur],sizeof(dp[tar]));
		FOR(a,21) FOR(b,21) FOR(c,21) FOR(d,21) if(dp[cur][d][c][b][a]>=0) {
			int v=dp[cur][d][c][b][a];
			if(S[i]=='K' || S[i]=='?') if(a<20)      dp[tar][d][c][b][a+1] = max(dp[tar][d][c][b][a+1],v);
			if(S[i]=='U' || S[i]=='?') if(b<20 && a) dp[tar][d][c][b+1][a-1] = max(dp[tar][d][c][b+1][a-1],v);
			if(S[i]=='R' || S[i]=='?') if(c<20 && b) dp[tar][d][c+1][b-1][a] = max(dp[tar][d][c+1][b-1][a],v);
			if(S[i]=='O' || S[i]=='?') if(d<20 && c) dp[tar][d+1][c-1][b][a] = max(dp[tar][d+1][c-1][b][a],v);
			if(S[i]=='I' || S[i]=='?') if(d) ma=max(ma,v+1), dp[tar][d-1][c][b][a] = max(dp[tar][d-1][c][b][a],v+1);
		}
		
	}
	cout<<ma<<endl;
}

まとめ

KKUURROOIIが1か2か、サンプルケースがあると良かったかも?