2011-05-21

Google Code Jam 2011 Round1B -> 20pt(通過できず)

04:19 |

結果 |00|--|--| 20pt, rank 1649 でした。Round1C まで居残りのはめに。。

A. RPI

04:19 |

チームリーグの勝敗結果（よくあるマトリックス）がある。
RPI なる指標を計算する。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int N;
		cin>>N;
		string sc[N];
		double WP[N];
		double OWP[N];
		double OOWP[N];
		CLR(WP);
		CLR(OWP);
		CLR(OOWP);
		REP(i, N){ cin>>sc[i]; }
		REP(i, N)
		{
			{
				int win=0, all=0;
				REP(j, N)
				{
					if(sc[i][j]!='.')
					{
						win += sc[i][j]=='1';
						all++;
					}
				}
				WP[i] = (double)win/all;
			}
			{
				int _all=0;
				REP(j, N)
				{
					if(sc[i][j]!='.')
					{
						_all++;
						// calc wp of j except i
						int win=0, all=0;
						REP(k, N)
						{
							if(k==i) continue;
							if(sc[j][k]!='.')
							{
								win += sc[j][k]=='1';
								all++;
							}
						}
						OWP[i] += (double)win/all;
					}
				}
				OWP[i] /= (double)_all;
			}
		}
		cout<<"Case #"<<t+1<<":"<<endl;
		REP(i, N)
		{
			int all=0;
			REP(j, N)
			{
				if(sc[i][j]!='.')
				{
					OOWP[i] += OWP[j];
					all++;
				}
			}
			OOWP[i] /= all;
			double RPI = 0.25 * WP[i] + 0.50 * OWP[i] + 0.25 * OOWP[i];
			cout<<RPI<<endl;
		}
		cout<<endl;
	}
	return 0;
}

B. Revenge of the Hot Dogs

04:19 |

数直線上に点がいくつか与えられている。
すべての点は毎秒1m動くことができる。
任意の２点が D[m] 以上離れた状態にするには何秒かかる？

(1) 同じ位置にある点クラスタ内で D 以上に広げる (2) クラスタ間で D 以上に広げるの２ステップで考えてサンプルも通りそうなので実装してみたものの、よく見るとそもそもサンプルが説明できないことに気づく orz
C を見て、戻ってきてやっぱりだめ。

解説を見ると、時間を決め打ちして２分探索できるとのこと。思いつかなかった.....
時間が決まればとりあえず左端からできるだけ遠くに行って詰めていけばいいので OK/NG がわかる。
言われれば納得....

昔、円周上を 10000 分割くらいして解いたら通ったみたいな問題があったのを思い出した。
しばらく考えてだめなら泥臭くいこ～

C. House of Kittens

04:19 |

N 角形の頂点に色を塗る。
頂点間には辺があることがある。辺は交わらない。
辺で区切られた領域それぞれについて、使用する色がすべて含まれる必要がある。

使う色の上限を求めて、総当りで頂点に割り振って、条件を満たすかチェックして、だめなら使う色を減らして、... で Small くらいは通るんじゃないかと思って実装。
が、「全ての頂点とそこから１歩で行ける頂点」内で、使用する色がすべて含まれる必要がある　と勘違いしていたことに気づく。
頂点と辺の情報を領域に変換するコードが残り20分で書ければ....
無理でした。

Google Code Jam 2011 Round1A -> 16pt(通過できず)

18:13 |

A. FreeCell Statistics

18:13 |

N, PD, PG が与えられる。
今日の試合数 <= N、今日の勝率はちょうど PD%、今までの勝率はちょうど PG%。
上記のようなことが有りうるかどうかを判定する問題。
例えば 10 50 100 なら今日の勝率 50% なのに全体の勝率は 100% にならないのでありえないと答える。

今日の試合数 <= N をチェックする。今日の試合数の最小値は、今日の勝率と100の最大公約数で100を割ったものになる。
試行錯誤しつつ、今日の勝率>0 なのに全体の勝率=0 とか極端な場合だけチェックすれば全体の勝率についてはなんとでもなるということが判明

コンテスト終了後、Large incorrect であることが判明。
Large 通している人のコードで実行した結果と自分のを diff で比べると、N が 10 桁とかでかいときに違っている。
Large では N <= 10**15 という条件があったのであった！
int N としていたのを long long N としたら一致。
くやしけり。
提出前にチェックすべき事をリスト化するなど、ミスを減らす仕組みづくりをしないといけない。

（以下、long long に修正後のソース）

int gcd ( int a, int b )
{
	if(a<b)
	{
		int tmp=a;
		a=b; b=tmp;
	}
	
	int c;
	while ( a != 0 ) {
	c = a; a = b%a;  b = c;
	}
	return b;
}

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int ans = 1;
		int pd, pg, d=100, g=100, v;
		ll n;
		cin>>n>>pd>>pg;
		//cout<<n<<pd<<pg;
		v = gcd(d, pd);
		pd/=v; d/=v;
		v = gcd(g, pg);
		pg/=v; g/=v;
		//cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl;
		
		//if(g<d)
		//{
		//	int a=d/g + 1;
		//	g*=a; pg*=a;
		//}
		if((pd!=d&&pg==g)||(pd>0&&pg==0) || d>n)
		{
			cout<<"Case #"<<t+1<<": Broken"<<endl;;
			continue;
		}
		//cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl;
		
		cout<<"Case #"<<t+1<<": Possible"<<endl;;
	}
	return 0;
}

B. The Killer Word

18:13 |

文字列 N 個からなる辞書からこっちが1個えらんで、Sean がそれを当てるゲーム。
最初、えらんだ文字列はすべて伏せてある。文字数はわかる。
Sean は文字(a-z)をguessする。guessした文字が文字列にあったらそれをオープンにする。なかったら 1pt 減点。
Sean のアルゴリズムは、文字の優先順位が与えられるので、その順かつ現時点で有効な選択肢に１つでも含まれる文字ならguessするというもの。
その際、そもそも伏せられた文字数から答えが１つに絞れる場合はguessしないで終了するなど、Seanは賢くやるとする。
文字の優先順位が M 個与えられるので、それぞれについて、Sean の減点が一番多くなるような文字列を求める。

とりあえずシミュレーションしてみる。
Small 通ったので Large やるが計算が終わらない。
Large は N <= 10000, M <= 100 で、コードを見るとなにやらループの入れ子が結構深くて M, N, Nのループになってる。
１つ１つ Sean の減点を求めて最大のものを出すとかいって、なんか重複して計算してるものが多そうだから DP みたいなことをやるんだろうけど思いつかず。

解説を見てると、文字数でクラス分けして、さらに1文字guessするごとにオープンされた文字の位置によってさらにクラス分けして、選択肢が1個になるまでシミュレートしていくとよいと書いてある。なるほど.....
今までいろんな問題を見てきて、「なんとかが最大になるようななんとかを求めよ」みたいなときは DP 感がするようになったのでこれをもっと推し進めたく。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int N, M;
		cin>>N>>M;
		string D[N];
		string L[M];
		REP(i, N) cin>>D[i];
		REP(i, M) cin>>L[i];
		//REP(i, N) cout<<D[i]<<endl;
		//REP(i, M) cout<<L[i]<<endl;
		
		cout<<"Case #"<<t+1<<":";
		REP(Li, M)
		{
			int lose[N];
			CLR(lose);
			REP(di, N)
			{
				// choose D[di]
				//cout<<"choose "<<D[di]<<endl;
				int ng[N];
				int nng=0;
				CLR(ng);
				REP(i, N)
				{
					if(D[di].SZ != D[i].SZ) {ng[i]=1;nng++;}
				}
				if(nng==N-1) continue;
				
				// begin guess
				REP(li, 26)
				{
					int contains=0;
					REP(i, N)
					{
						if(ng[i]) continue;
						if(D[i].find(L[Li][li])!=D[i].npos) { contains=1; break; }
					}
					if(contains)
					{
						char guess = L[Li][li];
						//cout<<"guess "<<guess<<endl;
						int revealed=0;
						REP(p, D[di].SZ)
						{
							if(D[di][p]==guess) {revealed=1;break;}
						}
						if(!revealed) lose[di]++;
						REP(i, N)
						{
							if(ng[i]) continue;
							REP(p, D[i].SZ)
							{
								if(D[di][p]==guess && D[i][p]!=guess || D[di][p]!=guess && D[i][p]==guess) {ng[i]=1;nng++;break;}
							}
						}
						if(nng==N-1) break;
					}
				}
			}
			int max = -1;
			int maxi = -1;
			REP(i, N)
			{
				//cout<<lose[i]<<endl;
				if(max<lose[i]) {max=lose[i];maxi=i;}
			}
			cout<<" "<<D[maxi];
		}
		cout<<endl;
	}
	return 0;
}

C. Pseudominion

18:17 |

A, B に手こずったので眺めただけ。