Hatena::Grouptopcoder

hotpepsiの練習帳

2011-05-12

Google Code Jam 2011 Qualification Round

01:16

準備

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

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

A Bot Trust

問題

ポイント

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

実装内容

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

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は通過したいなあ。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20110512