Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

  • A-small/A-Large/B-small(3WA)/B-Large:Passed, score:50, penalty(time):2:20:56, rank:139
  • A, B, Cがそれぞれポイントに合った難易度でいいセットだったと思う

Google Code Jam 2011 Round 1A A FreeCell Statistics

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

Problem Statement

解答方針

サンプルが親切。

PGが0か100のときに、PD!=PGだと矛盾するのでBroken

それ以外の場合は、PGはGの上限がないので任意の値で実現可能

(典型的にはGを100の倍数とすると、G*(PG/100)が必ず整数になるので、G*(PG/100)がN以上となるようにGを適当な100の倍数とすれば必ず実現できることが分かる)

ということで後はN以下のDでD*(PD/100)が整数となるものがあればPossibleということになる

式を変形するとD*(PD/100)=x⇔PD/100=x/D

すなわちPD/100を約分すると最小のDはその分母となる

ユークリッドの互除法を使用して最小のDを求め、N以下となるかどうかを確認すればOK

small通った

Largeダウンロード、一瞬で回答出た

中身を確認すると全てBrokenになっている・・・

問題文の上限を見直すと、10^15と書いてある。オーバーフローしている。不注意だった。

intをlong longに直す。

再度run。今度はPossibleがたくさん出てきたので良さそう

提出

ここまで15分くらい


ソースコード

main関数は省略

solve関数がfalseのときBrokenを出力、trueのときPossibleを出力します

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

bool solve(ll N, ll Pd, ll Pg) {
	if(Pd<100 && Pg==100) return false;
	if(Pd>0 && Pg==0) return false;
	if(Pd==0 || Pd==100) return true;
	ll m=100;
	ll g=gcd(m, Pd);
	if(m/g>N) return false;
	else return true;
}

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

Google Code Jam 2011 Round 1A C Pseudominion

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

Problem Statement

解答方針

残り30分弱では解けませんでした

以下は終了後の検討内容


まず、turnボーナスは手に入ったと同時に全部使ってしまったほうが良いのは明らか

turnボーナスが0のものはどう考えれば良いかという問題になるが、ここではcardボーナスの最大値が小さいのが重要なポイント

smallはcardボーナスが最大1なので、smallから考える


cardボーナスが1のものをc1、0のものをc0というグループに分ける

ここでc1及びc0を使用枚数を固定すると、各グループの中ではどんな順番で使ってもscore以外の状態が変わらない

従って、各グループの中ではscoreボーナスが大きい順に使ったほうが良いのだろうということになる

また、c1とc0についてはc1を先に使ったほうが選択肢が広がるため、まずc1をスコアが大きい順に使用し、次にc0をスコアが大きい順に使うという順序になる

あとはc1の使用枚数を全探索すれば、答えが出る。


ということで、Largeも同様にできそうであるが、実はこの考え方だとc2が登場するだけで劇的に難しくなる

ストレートフォワードに考えれば、選択肢を広げるため、c2をスコアが大きい順に使用し、c1を使用し、c0を使用し・・・という順番で良さそうに見えるが、これではWAとなる

以下のようなのが反例

(ここでは前からN枚が手札、後ろのM枚がデッキとする)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,0,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card1使用, card:2,3, score:6, turn:1
  3. card3使用, card:2,4,5, score:11, turn:0

c1のcard1より先にc2のcard2を使用すると、スコアは7にしかならない。

これは、c1でゲットしたカード内に手札のc2よりスコアの高いc2が入っていたからである。

なので無条件にc2から進めてもダメである。

ということで、c1とc2の使用タイミングを探索しようとすると、計算量が爆発する

そこで、以下のような条件を利用してDPする

  • c1とc2の使用した枚数が同じであれば、結果的にゲットしたカード(使用したものを含む)は常に同じになる
  • c1とc2の使用した枚数が同じであれば、よりスコアボーナスの大きいものを使用したほうが望ましい

ということでc1とc2の使用枚数を状態とすると、そのときのスコアが高いものだけを使用するDPが利用できる

ただし、例外があるので注意が必要である。

以下のような反例を考える。(これは上記の例のcard4のturnボーナスのみを変更したものである)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,2,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card2使用, card:1,3,4, score:1, turn:1
  3. card4使用, card:1,3, score:1, turn:2
  4. card1使用, card:3,5, score:7, turn:1
  5. card3使用, card:5, score:12, turn:0

card0,2,4,1の順で使っても、card0,1,3の順で使っても、c1とc2の使用枚数は同じであるが、0,1,3の順で使用すると残りのturn数が0となってしまい0,2,4,1の順より損である

これは、turnボーナスのカードがturn0のときに使えないという制約のためである。

従って、turnが0となる場合は、そうでない場合と区別して扱う必要がある。

これを踏まえてコーディングすると一応通る。

計算量はn=N+Mとすると、O(n^3log n)くらい?

なお公式の解説にはもっとコーナーケースを考えなくてよさそうなO(n^5)のDPが載ってました


ソースコード

Small専用。比較的簡単。

class GCJ {
public:
	int N, M;
	vector <int> c, s, t;

	//turnボーナスを全て使用する
	int get_turn_bonus(int begin, int end, int &score, int &turn) {
		if(turn<=0) return end;
		int nend=end;
		while(begin<end) {
			for(int card=begin; card<end; card++) {
				if(t[card]>0) {
					turn+=t[card]-1;
					score+=s[card];
					nend+=c[card];
				}
			}
			if(nend>N+M) nend=N+M;
			begin=end;
			end=nend;
		}
		return end;
	}

	//指定した範囲のカードをcardボーナスの値に応じてpriority_queueに振り分ける
	void classify_card(int begin, int end, priority_queue <int> &c0, priority_queue <int> &c1) {
		for(int card=begin; card<end; card++) {
			if(t[card]==0) {
				if(c[card]==0) c0.push(s[card]);
				else if(c[card]==1) c1.push(s[card]);
				else exit(1);
			}
		}
	}

	//残りの手札内でcardボーナス0のものを全て使用した場合のscoreを計算する
	int calc_score(priority_queue <int> c0, int turn) {
		int res=0;
		while(turn>0 && !c0.empty()) {
			res+=c0.top(); c0.pop();
			turn--;
		}
		return res;
	}

	//本体
	int solve(int N, int M, vector <int> c, vector <int> s, vector <int> t) {
		int res=0;
		
		this->N=N; this->M=M;
		this->c=c; this->s=s; this->t=t;
		priority_queue <int> c0, c1;
		int scard=N, sscore=0, sturn=1;
		scard=get_turn_bonus(0, scard, sscore, sturn);
		classify_card(0, scard, c0, c1);

		res=sscore+calc_score(c0, sturn);
		while(!c1.empty() && sturn>0) {
			int score=c1.top(); c1.pop();
			sscore+=score;
			sturn--;
			int nscard=min(scard+1, N+M);
			nscard=get_turn_bonus(scard, nscard, sscore, sturn);
			classify_card(scard, nscard, c0, c1);
			scard=nscard;
			res=max(res, sscore+calc_score(c0, sturn));
		}

		return res;
	}
};

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

	ifs >> testcase; ifs.ignore();
	for(int test=1; test<=testcase; test++) {
		int N;
		ifs >> N;
		vector <int> c(N), s(N), t(N);
		for(int i=0; i<N; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		int M;
		ifs >> M;
		c.resize(N+M); s.resize(N+M); t.resize(N+M);
		for(int i=N; i<N+M; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		ofs << "Case #" << test << ": " << gcj.solve(N, M, c, s, t) << endl;
	}
}

Large用。もちろんSmallも通る。

DP部分は幅優先探索で書いている。

main関数はsmallと一緒なので省略

class GCJ {
public:
	int N, M;
	vector <int> c, s, t;

	//turnボーナスを全て使用する
	int get_turn_bonus(int begin, int end, int &score, int &turn) {
		if(turn<=0) return end;
		int nend=end;
		while(begin<end) {
			for(int card=begin; card<end; card++) {
				if(t[card]>0) {
					turn+=t[card]-1;
					score+=s[card];
					nend+=c[card];
				}
			}
			if(nend>N+M) nend=N+M;
			begin=end;
			end=nend;
		}
		return end;
	}

	//指定した範囲のカードをcardボーナスの値に応じてpriority_queueに振り分ける
	void classify_card(int begin, int end, priority_queue <int> &c0, priority_queue <int> &c1, priority_queue <int> &c2) {
		for(int card=begin; card<end; card++) {
			if(t[card]==0) {
				if(c[card]==0) c0.push(s[card]);
				else if(c[card]==1) c1.push(s[card]);
				else if(c[card]==2) c2.push(s[card]);
				else exit(1);
			}
		}
	}

	//残りの手札内でcardボーナス0のものを全て使用した場合のscoreを計算する
	int calc_score(priority_queue <int> c0, int turn) {
		int res=0;
		while(turn>0 && !c0.empty()) {
			res+=c0.top(); c0.pop();
			turn--;
		}
		return res;
	}

	int solve(int N, int M, vector <int> c, vector <int> s, vector <int> t) {
		int res=0;
		
		this->N=N; this->M=M;
		this->c=c; this->s=s; this->t=t;
		priority_queue <int> c0, c1, c2;
		int scard=N, sscore=0, sturn=1;
		scard=get_turn_bonus(0, scard, sscore, sturn);
		classify_card(0, scard, c0, c1, c2);
		res=sscore+calc_score(c0, sturn);

		//幅優先探索(DP)
		queue <pair <int, int> > cbonus_cands;
		pair <int, int> cur_cbonus=make_pair(0, 0);
		cbonus_cands.push(cur_cbonus);
		int cards[82][82];
		memset(cards, -1, sizeof(cards));
		cards[0][0]=scard;
		int scores[82][82];
		memset(scores, -1, sizeof(scores));
		scores[0][0]=sscore;
		int turns[82][82];
		memset(turns, -1, sizeof(turns));
		turns[0][0]=sturn;
		priority_queue <int> rem_sbonus[82][82][3];
		rem_sbonus[0][0][0]=c0; rem_sbonus[0][0][1]=c1; rem_sbonus[0][0][2]=c2;
		while(!cbonus_cands.empty()) {
			cur_cbonus=cbonus_cands.front(); cbonus_cands.pop();
			int c1used=cur_cbonus.first, c2used=cur_cbonus.second;
			priority_queue <int> *rem=rem_sbonus[c1used][c2used];
			if(rem[1].size()>0) {
				int ncard=cards[c1used][c2used];
				int nscore=scores[c1used][c2used]+rem[1].top();
				int nturn=turns[c1used][c2used]-1;
				priority_queue <int> nrem[3];
				nrem[0]=rem[0]; nrem[1]=rem[1]; nrem[2]=rem[2];
				nrem[1].pop();
				int nncard=min(N+M, ncard+1);
				nncard=get_turn_bonus(ncard, nncard, nscore, nturn);
				classify_card(ncard, nncard, nrem[0], nrem[1], nrem[2]);
				res=max(res, nscore+calc_score(nrem[0], nturn));
				//nturn==0のものはqueueにpushしないようにする
				if(scores[c1used+1][c2used]==-1 && nturn>0) {
					cur_cbonus=make_pair(c1used+1, c2used);
					cbonus_cands.push(cur_cbonus);
				}
				if(nscore>scores[c1used+1][c2used] && nturn>0) {
					cards[c1used+1][c2used]=nncard;
					scores[c1used+1][c2used]=nscore;
					turns[c1used+1][c2used]=nturn;
					rem_sbonus[c1used+1][c2used][0]=nrem[0];
					rem_sbonus[c1used+1][c2used][1]=nrem[1];
					rem_sbonus[c1used+1][c2used][2]=nrem[2];
				}
			}
			if(rem[2].size()>0) {
				int ncard=cards[c1used][c2used];
				int nscore=scores[c1used][c2used]+rem[2].top();
				int nturn=turns[c1used][c2used]-1;
				priority_queue <int> nrem[3];
				nrem[0]=rem[0]; nrem[1]=rem[1]; nrem[2]=rem[2];
				nrem[2].pop();
				int nncard=min(N+M, ncard+2);
				nncard=get_turn_bonus(ncard, nncard, nscore, nturn);
				classify_card(ncard, nncard, nrem[0], nrem[1], nrem[2]);
				res=max(res, nscore+calc_score(nrem[0], nturn));
				//nturn==0のものはqueueにpushしないようにする
				if(scores[c1used][c2used+1]==-1 && nturn>0) {
					cur_cbonus=make_pair(c1used, c2used+1);
					cbonus_cands.push(cur_cbonus);
				}
				if(nscore>scores[c1used][c2used+1] && nturn>0) {
					cards[c1used][c2used+1]=nncard;
					scores[c1used][c2used+1]=nscore;
					turns[c1used][c2used+1]=nturn;
					rem_sbonus[c1used][c2used+1][0]=nrem[0];
					rem_sbonus[c1used][c2used+1][1]=nrem[1];
					rem_sbonus[c1used][c2used+1][2]=nrem[2];
				}
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110522