Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-22Google Code Jam 2011 Round 1A

Google Code Jam 2011 Round 1A B The Killer Word

| 23:13 | Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Seanの戦略が分かりにくい。exampleなかったらかなり理解が大変だったろうな・・

さて方針が思いつかない。

普通にシミュレーションするとLargeでTLEするよなあ

色々考えたが、Seanの戦略はシミュレーションしないとやはり最大失点を求めることが難しいように感じる

よく考えれば、シミュレーションを適当に効率化すればLargeでも間に合いそうな気がする

方針は、、、

  • 同じ長さのwordをグループ化して、各グループ毎にポイントを求める
  • 同じグループの中でも、1文字guessする毎に、開いた文字の位置が全く同じものをグループ化する
  • グループが1つになった時点でそのグループのシミュレーションを終了する

ぐらいのことをやれば良いのでは。

書いた→サンプル合った→提出→WA

なぜだ・・・

分からないので適当に細かいところを直してみるが合計3WA

再度問題文を読みなおす

ポイントが同じ場合はDictionaryで早く現れる順と書いてある

てっきり辞書順かと思っていたが、lexicographically smaller(earlier)とは書いていない

Dictionaryって、引数の名前かよ・・・

直した

通った

年のためsmallの時間を計測

0.08秒くらい。Largeは1000倍くらいのスケールなので大丈夫そう

Largeダウンロード

1分くらいで計算終了

提出

ここまで2時間くらい

最後のWAのデバッグで30分くらい無駄にした。問題文は本当によく読まないと・・・・・・

(問題文があまり良くないような気もするが)


ソースコード

提出時から多少整形しました

//oD:元のD, D:長さで分類したD, Di:長さで分類したDの各要素に対するoDのindex
vector <string> solve(int N, int M, vector <string> oD, vector <string> D[11], vector <int> Di[11], vector <string> L) {
	vector <string> res;

	//Dictionaryの各wordの各文字に対してbitmaskで位置を記憶
	int mask[10010][26];
	memset(mask, 0, sizeof(mask));
	for(int i=0; i<N; i++) {
		for(int j=0; j<(int)oD[i].size(); j++) {
			mask[i][oD[i][j]-'a']|=(1<<j);
		}
	}

	//Lの要素ごとに探索
	for(int li=0; li<M; li++) {
		vector <int> points(N);
		//wordの長さごとにポイントを計上
		for(int i=1; i<=10; i++) {
			if(D[i].empty()) continue;
			if(D[i].size()==1) continue;
			//判別がつかないものを同じgroupの要素(vector)に入れていく
			set <vector <int> > group[2];
			vector <int> vi;
			for(int j=0; j<(int)D[i].size(); j++) vi.push_back(Di[i][j]);
			group[0].insert(vi);
			//Lの1文字毎にgroupを分類する
			for(int j=0; j<(int)L[li].size(); j++) {
				set <vector <int> > &curgroup=group[j%2], &nextgroup=group[(j+1)%2];
				nextgroup.clear();
				if(curgroup.empty()) break;
				//これまでに判別がついてない集合毎に更に現在見ている文字で分類
				for(set <vector <int> >::iterator sti=curgroup.begin(); sti!=curgroup.end(); sti++) {
					vector <int> &curset=*sti;
					if(curset.size()==1) continue;
					map <int, vector <int> > tset;
					bool pointsplus=false;
					//mapとmaskを使って分類をする
					for(int k=0; k<(int)curset.size(); k++) {
						tset[mask[curset[k]][L[li][j]-'a']].push_back(curset[k]);
						if(mask[curset[k]][L[li][j]-'a']==0) points[curset[k]]++;
						else pointsplus=true;
					}
					for(map <int, vector <int> >::iterator mpi=tset.begin(); mpi!=tset.end(); mpi++) {
						if(mpi->second.size()>1) nextgroup.insert(mpi->second);
					}
					//集合の全ての要素が現在見ている文字を含まない場合、ポイントの追加を取り消す
					if(!pointsplus) {
						for(int k=0; k<(int)curset.size(); k++) {
							points[curset[k]]--;
						}
					}
				}
			}
		}
		//最もポイントの大きいものを解とする
		int maxpoints=0, maxi=0;
		for(int i=0; i<N; i++) {
			if(maxpoints<points[i]) {
				maxpoints=points[i];
				maxi=i;
			}
		}
		res.push_back(oD[maxi]);
	}
	
	return res;
}

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

	ifs >> testcase; ifs.ignore();
	for(int i=1; i<=testcase; i++) {
		int N, M;
		ifs >> N >> M;
		ifs.ignore();
		vector <string> oD;
		vector <string> D[11];
		vector <int> Di[11];
		for(int j=0; j<N; j++) {
			string s;
			getline(ifs, s);
			oD.push_back(s);
			D[s.size()].push_back(s);
			Di[s.size()].push_back(j);
		}
		vector <string> L(M);
		for(int j=0; j<M; j++) {
			getline(ifs, L[j]);
		}
		vector <string> w;
		w=solve(N, M, oD, D, Di, L);
		ofs << "Case #" << i << ":";
		for(int j=0; j<M; j++) {
			ofs << " " << w[j];
		}
		ofs << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110522