Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-10Google Code Jam Japan 2011 決勝(復習)

Google Code Jam Japan 2011 決勝 C ワイルドカード

| 13:41 | Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

smallを解いているときに思いついたDPでLargeを解いてみたら普通に解けた

大まかには以下のような感じ


aのai文字目まで、bのbi文字目までそれぞれマッチする文字列表現をdp[ai][bi]とする

ただし、最後に*があると何文字目までマッチというのが分からないので最後に*がないものを扱う

次に、aのai+1文字目以降で適当に部分文字列を取り出す(nab~nae文字目まで取り出したとする)

その文字列をbのbi+1文字目以降で検索し、最初に見つかったものをnbb~nbe文字目までとする

dp[nae][nbe]をdp[ai][bi]+"*"+a.substr(nab, nae-nab)で更新する

bのbi+1文字目以降でその文字列が見つからなかった場合、(必要に応じて)末尾に"*"を追加して解の候補とする

解の候補の数があまり多くならないので現実的な時間で解ける


最初と末尾の"*"ありなし辺りで多少コーナーケースのケアが難しくなるがそれ以外には特に難しい点はない

こんなんで通るんならもっと解かれてても良さそうなもんだが・・・


ソースコード

void updatebest(string &best, int &bestast, string cand, int candast, string &a, int ab, int ae, int asz, bool last) {
	if(ab>0) {cand.push_back('*'); candast++; }
	cand+=a.substr(ab, ae-ab);
	if(last && ae<asz) {cand.push_back('*'); candast++; }
	if(bestast==-1 || best.size()>cand.size() || best.size()==cand.size() && bestast>candast || best.size()==cand.size() && bestast==candast && best>cand) {
		best=cand;
		bestast=candast;
	}
}

string solve(string a, string b) {
	string best=a;
	int bestast=0;
	int asz=a.size(), bsz=b.size();

	string dp[52][52];
	int dpast[52][52];
	memset(dpast, -1, sizeof(dpast));
	dpast[0][0]=0;
	for(int ai=0; ai<asz; ai++) {
		for(int bi=0; bi<=bsz; bi++) {
			if(dpast[ai][bi]==-1) continue;
			for(int nab=ai; nab<asz; nab++) {
				for(int nae=nab+1; nae<=asz; nae++) {
					int nsz=nae-nab;
					if(bi+nsz>bsz) {updatebest(best, bestast, dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, true); continue; }
					int nbi=bi, nei=bsz;
					if(nab==0) nei=nsz;
					if(nae==asz) nbi=max(0, bsz-nsz);
					int nbb;
					for(nbb=nbi; nbb+nsz<=nei; nbb++) if(a.substr(nab, nsz)==b.substr(nbb, nsz)) break;
					if(nbb+nsz>nei) {updatebest(best, bestast, dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, true); continue; }
					int nbe=nbb+nsz;
					updatebest(dp[nae][nbe], dpast[nae][nbe], dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, false);
				}
			}
		}
	}

	return best;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		string a, b;
		ifs >> a >> b;
		string res=solve(a, b);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111010