Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-08Google Code Jam Japan 2011 決勝

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

| 20:56 | 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だけ解いた。

というか基本的に全探索するだけ。こっちのほうがB-smallより簡単な気がする。


ソースコード

string solve(string a, string b) {
	int n=a.size();
	
	string best=a;
	int bestast=0;
	for(int mask=1; mask<(1<<n)-1; mask++) {
		string aa;
		int aaast=0;
		for(int i=0; i<n; i++) {
			if(mask&(1<<i)) {
				if(i==0 || aa[aa.size()-1]!=' ') {
					aaast++;
					aa.push_back(' ');
				}
			} else aa.push_back(a[i]);
		}
		vector <string> vs;
		istringstream iss(aa);
		copy(istream_iterator <string>(iss), istream_iterator <string>(), back_inserter(vs));
		for(int i=0; i<(int)aa.size(); i++) if(aa[i]==' ') aa[i]='*';

		bool ok=false;
		if(aa[0]!='*') {
			if(vs[0].size()>b.size() || vs[0]!=b.substr(0, vs[0].size())) ok=true;
		}
		if(aa[aa.size()-1]!='*') {
			if(vs[vs.size()-1].size()>b.size() || vs[vs.size()-1]!=b.substr(b.size()-vs[vs.size()-1].size(), vs[vs.size()-1].size())) ok=true;
		}

		int idx=0;
		for(int i=0; i<(int)b.size() && idx<(int)vs.size(); i++) {
			if(vs[idx].size()>b.size()-i) break;
			if(vs[idx]==b.substr(i, vs[idx].size())) {
				i=i+vs[idx].size()-1;
				idx++;
			}
		}
		if(idx<vs.size() || ok) {
			if(best.size()>aa.size() || best.size()==aa.size() && bestast>aaast || best.size()==aa.size() && bestast==aaast && best>aa) {
				best=aa;
				bestast=aaast;
			}
		}
	}

	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;
	}
}

NiiqiitoNiiqiito2013/02/17 11:57I hate my life but at least this makes it braeable.

xkhqsmsgifxkhqsmsgif2013/02/19 15:16E9CxwG <a href="http://cdmchajbiebt.com/">cdmchajbiebt</a>

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111008