miau's blog?

Google Code Jam 2006

Google Code Jam 2006

また Qualification Round で撃沈しました。
とりあえず軽くレポートでも。




■事前準備

大会の概要とかは過去のレポートでも見ていただくとして。

Google Code Jam 2005 - miau's blog?
Google Code Jam India 2006 - miau's blog?

今回は使用可能な言語に Python が追加されてるので、LL Ring との絡みもあってこれを勉強してみることに。
準備としては初めてのPython 第2版 を半分くらい読んだ。少なくとも Qualification Round ではモジュールとかクラスとかの詳細を押さえる必要はないので、まあ必要十分と言ったところ。

■練習

どうでもいいけど、今回はログイン直後にどの Qualification Set / room を使うべきか案内メッセージが表示されるようになっていた。
少しずつ親切度がアップしてる感じ。

○Practice Room 250 点問題

経路問題。

"001100",
"000001",
"100010",
"100010",
"001101",
"010010"

こんな感じの文字列リストで移動可能な経路が表現(1 になっているところは移動可能)されていて、場所0 (一列目&一行目に対応)から場所1(二列目&二行目に対応)まで最大何ルート使えるか、という感じ。ただし一つの経路は一度しか利用できない制限つき。
んー・・・?解けなくはないけど、今までの 250 点問題に比べると難易度高いような。

とりあえず IDLE 開いて解いてみる。
Python の勉強中にも練習問題とか解いたんだけど、いざ使ってみると色々わからなくてエラー出しまくったり。Python って文字列の一部を hoge[i] = '1' とかやって変更できないのね・・・。
それ以外のところは別に難しくないと思ったんだけど、結局一時間かかった。Submit すると 95.31 points とか。・・・あまりよくないっぽい。

○Practice Room 750 点問題

Palindrome(回文)の問題。
"acdadc" みたいな文字が渡されるので、それを回文に分割してその個数を返す。このときなるべく長い回文になるようにしなければならない、と。この例だと "a" と "cdadc" に分割できるので答えは 2、みたいな。
なんかいいアルゴリズムありそうだけど、とりあえず何も考えずに Brute Force っぽい再帰処理で解くかな・・・。

とかやってたんだけど、気がついたら 23:55 とかだったので諦め。
後でちょっと手直しして Submit してみよう。


■本番

今回も 60 分で 250 点問題と 750 点問題の 2 題を解く感じ。

○250 点問題

カードのシャッフル問題。
シャッフルのルールが (3, 1, 5, 2, 4) みたいな配列で渡される(この場合は 3 枚目を 1 枚目に、2 枚目を 1 枚目に・・・というようにシャッフルする)から、これを n 回繰り返した結果を返す、と。
そこは理解できたんだけど、例題の結果がイマイチ納得できない。んー・・・?

しばらく悩んだ後、カードの初期状態は昇順に並んでっぽいことがわかった。あー・・・てっきりルールの配列が初期状態だと。「英文は適当に読んで例題で内容を理解」というスタンスだったけど、ちゃんと英文も読まないとダメですね。

この時点で 15〜20 分経過してて、結構やばめ。急いでコーディング&テストして Submit すると 126.55 points と。30 分経過。やばい。

○750 点問題

8-bishops 問題。
8-queens 問題知ってる人には説明不要でしょうが、n x n の盤に k 個の bishop を(互いに取り合わない位置で)置く方法は何通りあるか、という感じ。ただし盤には駒が置けない場所ってのが存在する。

"........",
"......#.",
"........",
".#......",
"........",
".....#..",
"........",
"...#...."

こんな感じで盤の状態が渡されるから、# になっている場所には駒を置けませんよと。駒を取り合うかどうかの判定にはこの # は使わなくていいらしい。
ちなみに bishop ってのは・・・ナナメにだけ動けるらしい(Wikipedia で調べた)。
大学の演習で 8-queens なら解いたことあるけど、あの時は Brute Force で解いたんだよなぁ。もっと効率のいい方法知ってないと高得点狙えないんじゃなかろうか。
そんな不安を覚えつつ、策もないので結局 Brute Force な再帰処理を適当に書きはじめる。

ただ、当たり判定に関しては「駒を置こうとしてる場所から斜めに検索かけて、すでに駒があるようならスキップ」みたいな処理・・・C風に書くと

for (i = 0; i < n; i++) {
if (placed[x+i][y+i] == 1 ||
placed[x+i][y-i] == 1 ||
placed[x-i][y+i] == 1 ||
placed[x-i][y-i] == 1)
{
continue;
}

みたいな処理は効率悪すぎなので、一応右斜め方向(x+yをキーにしたもの)と左斜め方向(x-yをキーにしたもの)でもう置けない場所を覚えることにする。

20 分くらい経過。大体の流れはできてるんだけど、なかなか答えが合わない。緊張で手が震えてきた。
残り 3 分くらいになって、Python の配列は参照渡しっぽい動作をすることを思い出して、書き直す。よし、それっぽい答えが出てるっぽい。・・・ってあと 10 秒?急いでコードを Code Jam の画面にコピーして・・・ああっ!手が震えて Submit 押し損ねた!

ちーん。


■その後

折角なので、750 点のコードを IDLE で検証してみた。あれ?なんか答えが違ってる。
・・・あー。駒を n 個置く場合に、駒の組み合わせを重複して数えちゃってるよ、これ。
だったら Submit しててもあまり意味なかったな。

楽に解くには n! で割ればいいんだけど、それだと n! 倍処理時間がかかるわけだし、一応ちゃんと解こう。ということで、ちょっと手を入れて。
んー・・・これでも 8 x 8 の盤に 7 個置くようなケースだとかなり(数分間)時間がかかる。

再帰呼び出しの度にリストを作り直してるのがいけないのかな?
ということで、
・「もう置けない場所リスト」のコピーを作成
・置けない場所リストを更新
・再帰呼び出し
みたいな処理を、
・置けない場所リストを更新
・再帰呼び出し
・置けない場所リストを元に戻す
ように書き換えてみた。でも体感的にはあまり変わらず。(後で計測したらこれで 30% くらいは性能向上してたけど)

アルゴリズムを変えないとなー、ということで、ごろごろしながらちょっと考えてみた。
・・・よく考えたら bishop って斜めにしか進めないんだから「何度移動してもたどり着けない位置」ってのが出てくるはずでは。チェス盤でいうと、黒いマスの駒はどうやっても白いマスにたどり着くことはできない。そうなると黒いマスの駒は白いマスの駒と取り合うかチェックを行う必要はない→黒いマスだけで n 個置くケースと白いマスだけで n 個置くケースとを別々に考えて、最後にそれを組み合わせればいい、ということに気づいた。
8 x 8 の盤に 7 個の駒を置くケースで言うと、64 マス全体で 7 個置くよりも、黒/白それぞれの 32 マスに 7 個置くケースを独立して考えて、
・黒7/白0
・黒6/白1
・黒5/白2
・黒4/白3
・黒3/白4
・黒2/白5
・黒1/白6
・黒0/白7
の組み合わせを足してやればいいのでは?単純に考えるマスの数が半分になるから、2 ^ 7 = 128 倍くらいのオーダーで速くなるはず。

ということで、実装してみると 1000 倍くらいのパフォーマンスが。枝きり(っていうんだっけ?)な効果で思いのほか速くなってるらしい。とりあえず 0.2 秒くらいで終わったので満足。
同じ Room(50人)の結果を見ると、この問題解けてる人が 5 人、System Test をちゃんと通してる人は 1 人だけ、という結果。その 1 人もこれと同じようなアルゴリズム使ってるみたい。・・・1 時間でこんなの思いつけないよ。もう 1 時間くらいあればなんとかなったんだけど。

ついでに 250 点問題も上位の人のコードを見てみる。シャッフルの度に配列を毎回作成するんじゃなく「前回の並び」配列を交互に使いまわしてるところがポイントみたい。マージソートとかでよく使われる方法なわけで・・・これを思いつかなかったのはちょっとヘボいなぁ、我ながら。

■感想

そんなわけでまた予選通過できませんでしたが、勉強になったし、いい刺激になったし。やっぱりかなり楽しめました。
次も絶対参加しよう。
posted at 08:34:14 on 2006-09-07 by miau - Category: General No Trackbacks - Permalink

TrackBack

このエントリにトラックバックはありません
現在トラックバックは受け付けていません。

Comments

No comments yet

Add Comments

現在コメントは受け付けていません。
お手数ですが、 こちら のコメント欄にでも記載していただければと思います。