kojingharangの日記

Google Code Jam 2011 Qualification -> 70pt (通過)

22:59 |

12121(?)人中3417位で予選通過ということです。次も頑張ります。

ツイートする

A. Bot Trust

22:59 |

• 廊下があって等間隔に1,2,3...のボタンが置いてある。
• ロボット２台が廊下の１ボタンのところに置いてある。
• それぞれのロボットは毎秒ごとに (1) ＋１方向または−１方向に１マス移動する、(2)移動しない、(3)今いるところのボタンを押す、のいづれかができる。
• 「ボタンの番号と押すロボットの名前」からなるリストが与えられるので、指定されたロボットが指定された番号のボタンをリストの順に押す。
• 全部押すまでに何秒かかるか。

• ロボットが押すべきボタンの位置と、全体として何番目にそのボタンを押すことになるかを各ロボット分のリストに用意する。
• ロボットがボタンを押せる位置にある　かつ　ボタン順番値==グローバルなボタンカウンタ　ならボタンを押す。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int ans = 0;
		VVI d;
		d.PB(VI());
		d.PB(VI());
		
		int N;
		cin>>N;
		
		REP(i, N)
		{
			char col;
			int loc;
			cin>>col>>loc;
			//cout<<col<<loc<<endl;
			int ci = col=='O'?0:1;
			d[ci].PB(i);
			d[ci].PB(loc);
		}
		//cout<<d<<endl;
		int pi = 0;
		int ci[2];
		int cur[2];
		ci[0]=ci[1]=0;
		cur[0]=cur[1]=1;
		REP(step, 100*100)
		{
			int pushed = 0;
			int end = 1;
			REP(col, 2)
			{
				if(ci[col]>=d[col].size()/2) continue;
				end = 0;
				
				int p = d[col][ci[col]*2+0];
				int loc = d[col][ci[col]*2+1];
				if(cur[col]==loc)
				{
					if(pi==p)
					{
						//cout<<col<<" push "<<cur[col]<<endl;
						pushed=1;
						ci[col]++;
					}
					else
					{
						//cout<<col<<" stay"<<endl;
					}
				}
				else
				{
					int dir = loc - cur[col] > 0 ? 1 : -1;
					cur[col]+=dir;
					//cout<<col<<" move to "<<cur[col]<<endl;
				}
			}
			if(pushed) pi++;
			if(end) break;
			ans++;
		}
		cout<<"Case #"<<t+1<<": "<<ans<<endl;;
	}
	return 0;
}

ツイートする

B. Magicka

22:59 |

• 変換規則とpushしていく文字リストが与えられる。
• １文字ずつリストにpushして、そのたびに変換規則によってリストを変化させるゲーム。
• リストの最後の２文字→新しい文字に置き換え
• リストの中に特定の２文字が両方含まれている→リストの中身を消去

（反省点）

• 変換して変化したらまた再評価するのかとか考えずに実装したらsmallもlargeも通ったけど、そのへん敏感に確認すべきだった。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		vector<string> com;
		vector<string> del;
		string v;
		int nc, nd, nv;
		cin>>nc;
		REP(i, nc)
		{
			string tmp;
			cin>>tmp;
			com.PB(tmp);
		}
		cin>>nd;
		REP(i, nd)
		{
			string tmp;
			cin>>tmp;
			del.PB(tmp);
		}
		cin>>nv;
		cin>>v;
		//cout<<com<<del<<v<<endl;
		vector<char> w;
		REP(i, nv)
		{
			w.PB(v[i]);
			if(w.SZ>=2) REP(j, nc)
			{
				if(w[w.SZ-2]==com[j][0] && w[w.SZ-1]==com[j][1])
				{
					w.pop_back();
					w.pop_back();
					w.PB(com[j][2]);
				}
				if(w[w.SZ-2]==com[j][1] && w[w.SZ-1]==com[j][0])
				{
					w.pop_back();
					w.pop_back();
					w.PB(com[j][2]);
				}
			}
			if(w.SZ>=2) REP(j, nd)
			{
				if(w[w.SZ-1]==del[j][0])
				REP(k, w.SZ-1)
				{
					if(w[k]==del[j][1])
					{
						w.clear();
					}
				}
				if(w[w.SZ-1]==del[j][1])
				REP(k, w.SZ-1)
				{
					if(w[k]==del[j][0])
					{
						w.clear();
					}
				}
			}
		}
		cout<<"Case #"<<t+1<<": "<<w<<endl;;
	}
	return 0;
}

ツイートする

C. Candy Splitting

22:59 |

• 正の整数値が書きこまれたアメが袋にたくさん入ってる。（なんだそのアメ！！）
• Seanがアメを２つのグループに分ける。
• Patrickが２つのグループそれぞれの合計を算出する。合計が等しくないとPatrickは泣き出す。
• Patrick が泣かなかった場合 Seanは自分がもらうグループを選ぶことができる。
• Patrick は２進数の加算の繰り上げができないので排他的論理和を計算してしまう。
• Seanははちゃんと加算できるので、自分で選ぶグループの合計が最大になるように２グループに分けたい。
• Patrick が泣かないようにできるか、もしそうならSeanが貰える合計の最大値を求める。

• Patrick が泣かない←→すべてのアメのXOR==0 でとりあえず判断できそう。
• で、分け方は 2^(アメの数) 通りある。largeではアメの数が最大1000なので全通り試すみたいなのは破綻するな
• なんかうまい方法があるんだろう
• （う〜〜〜〜ん.......）
• （う〜〜〜〜ん.......）
• （う〜〜〜〜ん.......）
• 最大にしたいということなので、強欲に「１番小さいのとそれ以外」で分けたらどうだ
• XORなのでなんかうまくいきそうな気がする
• 「全XORが0の場合、「任意の１つとその他」でグループ分けするとかならずXOR値が等しくなる」を証明したいでござる
• 全XOR==0 → 任意の２グループのXOR==0 ということなので、「１番小さいのとそれ以外」で分けても成り立つ。証明だん。

• なので、全アメの合計から一番小さいやつを引いたのが答え。
• ソートしたけど、最小値を求めるだけなら不要ですね。。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int n;
		cin>>n;
		VI c(n);
		int x=0;
		int sum=0;
		REP(i, n)
		{
			cin>>c[i];
			x ^= c[i];
			sum+=c[i];
		}
		SORT(c);
		sum -= c[0];
		//cout<<c<<endl;
		if(x==0)
		{
			cout<<"Case #"<<t+1<<": "<<sum<<endl;
		}
		else
		{
			cout<<"Case #"<<t+1<<": NO"<<endl;
		}
	}
	return 0;
}

ツイートする

D.

22:59 |

• 1〜Nのカードが順不同でおいてある。
• 任意のカード集合の位置を固定したまま机を叩くと、残りのカードが順不同にシャッフルされる。
• カードを抑える、机をたたく以外のことはできない。
• カードを昇順にソートしたい。
• 平均何回机を叩けばソートできるか？？ただし誤差は 1-e6 以内とする。

• なにこれ

• sample input, output を見ると、２枚のカードを固定しないでシャッフルすると平均２回でソートできるとなっている。ほう。
• 確率を計算しようと試みる。1*1/2 + 2*1/2*1/2 + 3*1/2*1/2*1/2 + ... と無限に足すと、...わかんないけど 2 に近づくようだ。
• では、「任意の２枚を入れ替える操作だけができるとして、初期状態から最小何手でソートされた状態になるか？」という問題を解けばいいんじゃね
• sample output と同じ結果になったので small 提出→incorrect
• ちょっとバグってたので再提出→incorrect

• (.....................)

• 諦める。

• 問題の解説を見たところ、「正しい位置にないカードだけを１回シャッフルすると平均１枚のカードが正しい位置に移動する」という性質が成り立つようで、
• 正しい位置にないカードの枚数に ".000000" を付けて出力すれば正解となるらしい。

（反省点）

• こういう、「サンプルみたいなシンプルなケースで考えてみて、なんか成り立ちそうな性質を思いついて、それをざっくりでもいいから証明してコードを書く」みたいなのが苦手。
• どう反省すべきか不明だが、もっと賢くなれということかorz

（以下、間違ってますが掲載）

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int n;
		int ans=0;
		cin>>n;
		VI d(n);
		REP(i, n)
		{
			cin>>d[i];
		}
		cout<<d<<endl;
		int ans2=0;
		REP(i, n)
		{
			if(i+1!=d[i]) ans2++;
		}
		REP(i, n)
		{
			if(i+1!=d[i])
			{
				int ti=-1;
				FOR(j, i+1, n) { if(d[j]==i+1) { ti=j; break; } }
				swap(d[i], d[ti]);
				ans+=2;
				//cout<<d<<endl;
			}
		}
		//cout<<d<<endl;
		cout<<"Case #"<<t+1<<": "<<ans<<".000000 "<<ans2<<endl;
	}
	return 0;
}

ツイートする