Google Code Jam 2006 Qualify参戦記

年休取って参戦してました。言語はPythonです。

Coding Phase前

最初に出てきたメッセージボックスを流し読みで消してしまい、自分がassignされた部屋がどこか判らなくなる。
流し読みした記憶を元に、/room [自分のID] で入れた。
Set2のRoom16で、IDはomoikane_nd001。

250点問題

リストのシャッフル。シャッフル法はリストで渡され、[2,3,1]なら、入力の2番目を先頭に、3番目を2番目に、1番目を最後に、とシャッフルする。
ここまでは超簡単な問題なんだけど、初期入力について勘違い。問題としては、初期入力を[1,2,,,,m]としてそれを渡された順序で指定された回数シャッフルするというもの。
それを、ルール用のリストと入力のリストが同じだと勘違いしてしまっていた。シャッフル後のリストが次の入力であり、次のシャッフル法でもあると思ってしまった。
たとえば、「[2,3,1]を3回」という問題なら、[1,2,3]→[2,3,1]→[3,1,2]→[1,2,3]が答えなんだけど、[2,3,1]→[3,1,2]→[2,3,1]→[3,1,2]を計算していた。
どうしても答えが合わず、途中結果を出力しても思い通りなので、問題を読み直してみたら・・・orz
この時点で30分近く経過しており、スコアは127.3

750点問題

ビショップ配置問題。ただし、盤面は文字列のタプルで渡され、矩形だけど正方形とは限らない。文字が'#'になっているところにはビショップを置けない。
まず、文字列操作でつまずく。Pythonでは文字列は変更不可能だから、「n文字目をxに置換した新しい文字列を作る」という関数をリファレンスマニュアルで探すも、なかなか見つからない。結局、new_str = str[:n] + x + str[n+1:] で対処したんだけど、どうせ編集するなら最初からリスト型に変換しておけば良かったんだな。list("abc") → ['a', 'b', 'c'] って。途中で気づいたけど時間がもったいないからそのままGo。
その後も、ビショップの利きが'#'を超えられないと勘違いしていたりして、あと少しのところで時間切れ。0点。

反省

高専プロコンは、4月に問題の形式が発表され、10月に計算プログラムを持ち寄って戦わせるという形式だから、制限時間内にプログラムを作れというタイプのプロコンは初めて。慣れないために結構ミスって時間を潰してしまった。問題自体は簡単で時間勝負だったから、非常に残念。

  1. 問題文を読む時間が惜しくて流し読みするのはNG。
  2. まだまだPythonC++ほどには使えてないorz もうC++よりPythonの方がコーディング早いと思っていたが、それはライブラリの性能であって、for文のテクニックとか文字列操作のテクニックとかがダメダメだ。
  3. Pythonで問題を解くときは、タプルや文字列はlistに変換してから解こう。最初に内容を変更する気が無くても、後で変更したくなったときに面倒。

ということで、もともと予選突破できないと思ってたけど、かなり悔しいので、来年は予選突破+1回戦突破くらいねらおうと思います(`・ω・´)

このブログに乗せているコードは引用を除き CC0 1.0 で提供します。