hotpepsiの練習帳

Google Code Jam 2011 Qualification Round

01:16

準備

GCJ勉強会に参加したので、せっかくなので挑戦。

過去のQRのTheme ParkとClosing the Loopを解いて、入出力のひながたを用意しておいた。

A Bot Trust

問題

• ロボットBまたはOと、ボタン番号が指定される
• 指定されたロボットが、そのボタンへ移動してボタンを押す
• 最小の時間(クリティカルパス)を求める

ポイント

• 指定された方が行動している間、指定されていない方も、次に指定された場所へ移動できる

実装内容

• 指定されたロボットは、行動時間を累計しておく
• 累計ぶん、指定されなかった方も動ける
• ロボットが交代(色が変化)したとき、必要な行動時間から、他方の累計行動時間を引く

https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_A_BotTrust.cpp

B Magicka

問題

• エレメントが1つずつ与えられ、リストに加わる
• 末尾の2つがcombine条件に合致したら、1つの別のエレメントに変化する
• opposedペアが発見されたら、リストをクリアする

ポイント

• opposedよりcombineが優先
• 1個足し、combine判定ループ、opposed判定、の繰り返し

実装内容

• combineとopposedの両方については、逆のパターン(AB→TならBA→T)も保持しておく
• opposed判定のために、エレメント毎の個数をひけるようにしておく
• opposed判定は、最後のエレメントと、opposedペアになるものがどこかに1個以上あるかどうかで判定
• ただしopposedペアが同じエレメントの場合は、2個以上あるかどうかで判定

https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_B_Magicka.cpp

C Candy Splitting

問題

• Seanは加算ができる
• Patrickが加算だと思い込んでいるのはXORである

ポイント

• XORが一致するというのは、SeanとPatrick全体でのXORがゼロである
• 全体のXORがゼロでない場合、Patrickは泣く
• 全体のXORがゼロの場合、1つだけキャンディーを渡すと、XORが一致する

実装内容

https://github.com/firewood/topcoder/blob/master/gcj_2011/QR_C_CandySplitting.cpp

D GoroSort

問題

• ソートされていない要素をランダムにシャッフルするとき、並ぶまでの期待値を求めよ

ポイント

• 2回で少なくとも要素ひとつは交換、すなわち揃えられるので、O(n)かなーと予想だけした。
• ふぞろいがn個のとき、1回シャッフルするとだいたい1個揃う(それぞれの1個が揃う確率が1/n、それのn倍)ので、直感的にはn回、つまり、ふぞろいの数=回答、ということらしい

結果

A、B、Cのlargeが通って70点。四時間くらいかかった。

largeが全部通ったのでとりあえずよしとしたい。Round 1は通過したいなあ。