kmjp's blog

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

Typical DP Contest : I - イウィ

本番2時間デバッグしてバグが取れなかった問題。
http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

問題

iとwで構成される文字列Sが与えられる。
S中に文字列'iwi'があればそれを取り除くことができる。
Sから最大'iwi'を何回取り除けるかを答えよ。

解法

各文字から初めて、最大何文字取り除けるかをDPで求める。
以下の条件の時、最大で3K文字を取り除くことができる。
Kを大きくしながらDPしていけばよい。

  • 3K文字分の部分文字列の先頭および末尾はi
  • 部分文字列の途中にwがあり、先頭のiとwの間およびwと末尾のiの間はすべて取り除ける

後者の条件は、iiwiiwiwiにおける真ん中のiwiiwiの様に、取り除けるパターンが複数ある場合に注意。
自分はこれを忘れてずっとデバッグしてた。

各文字を先頭に最大で取り除ける文字数がわかったら、あとは先頭からgreedyに取り除いていけばよい。

int L;
string S;

int reducable[322][322];
int mama[322];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>S;
	L=S.size();
	
	for(l=2;l<L;l+=3) {
		FOR(x,L) if(S[x]=='i') {
			z=x+l;
			if(z>=L || S[z]!='i') continue;
			for(y=x+1;y<z;y++) if(S[y]=='w') {
				if((reducable[x+1][y]||(x+1==y)) && (reducable[y+1][z]||(y+1==z))) 
					reducable[x][z+1] = (l+2)/3;
			}
			for(y=x+1;y<z;y++) if(reducable[x][y] && reducable[y][z+1])
				reducable[x][z+1] = (l+2)/3;
		}
	}
	for(x=L-1;x>=0;x--) {
		mama[x]=mama[x+1];
		for(y=x;y<=L;y++) mama[x]=max(mama[x], reducable[x][y]+mama[y]);
	}
	
	return _P("%d\n",mama[0]);
}