Google Code Jam 2012 - Qualification Round
今年もGCJの季節がやってきました。年々参加者が増えて競争が激化しつつありますね。自分はGCJはこれで3回目なのですが、毎度多倍長演算とかに悩まされてるもんで、ここ最近はPythonの練習がてらに参加しています。研究でも細々したプログラムはPythonで作ってるのですが、この活用範囲を広げるための練習という感じです。まだまだPythonの文法や関数を調べつつやってるのでコーディングが激遅ですが、少しずつ慣れつつあります。今回は自宅でゆっくりと挑戦しましてジャスト300位でした。
A. Speaking in Tongues
各アルファベットを別のアルファベットに置き換えるような暗号があって、その暗号文が与えられる。それを復号して表示しなさい、な問題。肝心の変換ルールが記載されてないけど、それはサンプルから自分で解析しなくちゃいけない。サンプルに乗ってない‘q’と‘z’は、文中にコソッとヒントがあるのでそれを見逃さないこと。実はこれでWAくらった（笑）。親切にもPythonに文字置換関数があったのでそれ使って終了。・・・Smallしかない問題ってGCJ初ですね。
B. Dancing With the Googlers
3人の審査員がダンサー達をジャッジしスコアをつける。審査基準があるので各審査員のスコアはだいたい1点差内に収まるが、たまに2点差があってそのとき観客は驚く。各ダンサーについて各審査員が何点をつけたか覚えてないけど、各ダンサーの合計得点と驚愕回数だけは覚えてるので、それらの参考に、審査員の誰かが×点以上つけたダンサーの数を推測し、その考えられる最大人数を出力。（説明むずい）
1点差スコアの場合、合計得点から審査員のつけたスコアの組み合わせは一意に決まる。この時点で審査員の誰かが×点以上つけてるダンサーをまずカウントしておく。残るダンサーのうち、もし2点差だったら最大点が×点以上に達するダンサーの数をカウントしておいて、驚愕回数と比べて、小さいほうを先ほどのカウントに足したのが答え。
C. Recycled Numbers
問題説明メンドイので解き方だけ（爆）。[A,B]範囲内の各数 n について、n
D. Hall of Mirror
幾何。怖いねぇ（笑）。案の定、ほとんどの人がスルーしてるし。でもこれを解いたら一気にヒーローだと思って頑張ることに（笑）。よくよく読んでみたら、Smallでは部屋の四方にしか鏡がないという制約らしくて、Xさんを反転コピーみたいに複製して、その鏡の中のXさんの位置をリストアップし、鏡の中のXさんとオリジナルXさんとの各距離を計算し、D以下なら到達不可とする、でイケると発見。Largeはどうにも実装できる気がしなかったので放置。そして一発AC！。
コンテスト後に@colun先輩の実装見たら、まー綺麗なこと。鏡の中のXさんの位置は各グリッド中心に限定されるはずなので、オリジナルXさんの座標位置から半径Dの円内にある各グリッド中心に向かって光線＝レイを飛ばして、その光線をトレース（鏡面反射のシミュレート）して、オリジナルXさんに戻って来れればOK!、っていうのを実装すれば良かったらしい。当初思ってたよりは単純なアルゴリズムだったけど、そのレイトレースをバグなしで実装する自信は僕にはありません。後ほど修業します。
