つーさのくーかん

前回Qualに通過したので、Google Code Jam Round1Aに参加。

問題 http://code.google.com/codejam/contest/1645485/dashboard
スコア http://code.google.com/codejam/contest/1645485/scoreboard

問題文はCreative Commons Attribution Licenseらしいので、
概要を日本語に超訳したものを、続きを読む以下に書いた。*1

ラウンドの結果から言うと、A, Bのlargeまで正解。Cは出せず。
oooo-- 53点 849位 でR2へはギリギリ通過という感じ。
Bのlargeは正直不安だったけど、通ってよかったね、という感じ。
個人的には、この問題内容なら、もうちょっとがんばれてもいいよなーと思う順位。
ooo-o- の52点ではR2進出にならないのが怖いところ。うん、R2もがんばるし。

なんか、Googleは貪欲法好きですね。前のGCJJでも出てた気がするし。
僕も貪欲法好きなので、貪欲法が使える問題はもっと出るといいですね。

以下、参加記録。
今回はコード貼り付けはなしで……。だって恥ずかしい//
どうせ誰も読まないし、僕も誰かに読んでもらおうと思って書いてないし。
ここにあるしね。

A

10時スタートなのに、9時55分まで寝てた。
紙と鉛筆の準備をして、コーラの準備をして、座ったのが30秒前、落ち着く暇なくスタートです！

問題

サンプルテストケースとかはこっちをみてね
http://code.google.com/codejam/contest/1645485/dashboard#s=p0

文字数がB(最大10万)あるパスワードを打つ。文字ごとに打ち間違える確率が与えられる。
今A文字目まで入れてみたけど、こっから先のタイプ数の期待値を最小化したい。
そこまでの入力は間違ってるかもしんない。
できることはそのまま入力を続けてEnterを押すか、何度かBSを押して消してから続きを打つか、今すぐEnterを押すか。
もちろん、入力が間違ってたらもう一回打ち直しなんだが、打ち直しの時は100%正確に打てるぜ。

読み終わった

ね、寝ぼけた頭では英語が読めないでござる……。問題文長いのもあって、読解に手間取った。
そのまま入力を続ける場合、最初の2文字の入力があってれば、gu... e s t Enter で4打鍵、
間違ってたらgu... e s t Enter g u e s t Enter、でなるほど10打鍵か。なるほどなるほど。
とかやってたのは、開始から優に15分後の出来事である。

で、考えた

制約は……。smallだと問題文にあるような表作れるけど、largeだと10万かぁ。
10万文字のパスワードなんか誰が設定するのかなぁ……。
10万でO(N^2)はきっついから、O(NlogN)かO(N)なんだろうなぁ(←
まぁ、8分あるから、N^2でも余裕っちゃ余裕だけど。
各戦略を全部試すことを考えるか。

つーか、間違えたとこまでBackspaceが届いてるかどうかが問題なんよね。
(n-1)文字は正確に打てててn文字目で初めて打ち間違えてる確率 の 表に変換。
いきなりEnter押す！　Backspaceを0回～A回押してから続きを打つ の、 A+2通りの戦略に分解できる。
それぞれで成功してるか失敗してるかの2種類から確率求めて、一番小さいの返せばいいのかな。

コード書いた

何気に添え字の処理が面倒だった。1引いたり。
こういうところが1発で書けなかったコードっていうのはたいていどっかに爆弾を抱えることが多い。

実行

あ、あれ？　
全然結果が返ってこないぞ。smallなのに。
インプット中身ある？　メモ帳。わ、LF。もしかして改行コードとか？　えーとえーと。
vim A0.inして、:w ++ff=dos
あ、あれ、やっぱ返ってこないぞ。っと、よく見ると、
GCJ.exe A0.in > A0.out とか書いてる。違う。
GCJ.exe < A0.in > A0.out こう。おｋ
提出締め切りまで30秒しかないし、ひー。
で、とりあえずsmall通った。

largeも時間計算量はO(N)まで落としてあるからその点は大丈夫。
うーん、落ちるとしたらどんなケースがあるのかなー……。さっぱり。
まぁいいや、提出して次っ

B

うひー。Aに結構時間掛かっちゃったなぁ。もう1200人以上提出してるよー。これじゃあ通過できないかも。
いや、Bで追い抜けばいいんだ。がんばろがんばろ。

もんだい

サンプルテストケースとかはこちらをみるのよ
http://code.google.com/codejam/contest/1645485/dashboard#s=p1

Ryanくんが Nステージ(最大1000)あるゲームを完全攻略する最短プレーを求める問題。
各ステージをクリアするとランクがつく。ランクは「☆クリア」と「☆☆クリア」の2種類。
初めて「☆クリア」すると☆が1個、その後「☆☆クリア」すれば☆がもう1個。
いきなり「☆☆クリア」すると☆が2個もらえる。つまり各ステージで2個ずつ☆が集められる。
どのステージからやってもいいんだけど、各ステージごとにクリア条件があって、
「i番目のステージを☆クリアするには a_i個の☆が必要」
「i番目のステージを☆☆クリアするには b_i個の☆が必要」と決まっている。
スーパーゲームプレーヤーであるRyanくんは、必要☆が集まってればいきなり☆☆クリアも可能。
☆0個の状態からスタートして、全ステージを☆☆クリアしたい。
プレーしなきゃいけないゲームの最小回数は？　理論上無理ゲーならToo Badと出力しなさい。

読み終わった

ゲームクリア……最初っから☆☆クリアしてけばいいよね。
フツーに貪欲法だよね？　ゲーマーだったらすぐ思いつくでしょ。あれ、簡単？
☆☆クリアできるステージがあるなら☆☆クリアする。そうじゃなかったら、☆クリアする。

かんがえ……てない コード書いた

これで、サンプルは通るね、うん。じゃあ、提出。　incorrect! なん、だと……？
え、ちがうの？　ちがうのかー！　なにがちがうんだー！

考えたケド……

5分考えて、どこが間違ってるかさっぱりわからないので……。
ダウンロードしたsmallテストケースを手で解いてみよー！
プログラムが出した答えと手計算で出した答えを比較してみることに。
メモ帳……うわ、改行コードLFだ。だめじゃん！
コマンドプロンプトから more で……。

で、5個目ぐらいのケースを手で解いたときに、
プログラムが出した答えよりも小さい回数でクリアできたちゃった。

全 5ステージ
ステージ1 ☆条件: 0 / ☆☆条件: 2
ステージ2 ☆条件: 0 / ☆☆条件: 9
ステージ3 ☆条件: 0 / ☆☆条件: 1
ステージ4 ☆条件: 0 / ☆☆条件: 4
ステージ5 ☆条件: 0 / ☆☆条件: 2
ってなケースだった。

どうみても、最初は「☆クリア」しか選べない。
正解は 2☆ 3☆☆ 1☆☆ 5☆☆ 4☆☆ 2★☆ みたいなルートで6プレーなんだけど。
最初にステージ2以外を選んでしまうと、 3☆ 3★☆ 1☆☆ 4☆☆ 5☆☆ 2☆ 2★☆ で 7プレー必要……！
わ、「☆クリア」しか選べないときに、適当にえらんじゃだめなんだ……。

うーん？　「☆☆クリア」に必要な☆の数が多い順にソートしとけば……いいのかな？
うーん、わかんないけど、出してみよ。あ、small通った。
でも、わかんない。いいのかなこれで……うーん……てやっ(提出)

まぁ、落ちちゃったら次がんばればいいよね。

C

ラウンドっていつまでだっけ？　2時間半か。ってことは後40分しかないのか。うーん、行けるかなー。
Bも1000人近く出してるし、2回wrong出してるから抜かれちゃうかなー。
ううー、C-smallまで取っとけば安心かなぁ？*2
ってゆか、前のGCJJ決勝って、largeまで取ろうとして失敗したんだよ。
smallだけ取るつもりでいってみよ。

問題

サンプルなどは↓
http://code.google.com/codejam/contest/1645485/dashboard#s=p2

一方通行の2車線道路に車が最大50台。各車はそれぞれの速度で等速に進行する。車長は5メートル。
ドライバーは瞬時に車のレーンを変更できるけど、併走する2台の車がその場で入れ替わるのは不可。
各車の初期レーンと初期座標と速度が与えられるので、車同士が衝突事故を起こすまでの時間を求めよ。
事故を起こさずに走行し続けられる場合はPossibleと答えよ。

注: まぁ、本当は事故を起こさないようにドライバーは等速運転を解除できて、
いずれかのドライバーがやむを得ず等速運転を解除するまで、最高何秒間続けられるかって問題なんだけど、
めんどくさいから、事故るまでの時間でいいよね＊

読み終えた

あと30分。一番点数高いのを30分で解けるかって？
うーん、でも幾何……のような、感じ。幾何ならワンチャンあるか？
衝突判定なんて、普段ゲーム作りで書き慣れてるでしょ？

考え……ながら書く

50台しかなくて、車が自由にレーンチェンジができるってことは、
追い越し車線をあけといて、追い越したいときだけ右行けって感じで、
3台が同時刻に同じぶつかる位置に来ないようにすればいいのかな？
とりあえず、
　「追い越される車」「追い越す車」「それをさらに追い越そうとする車」
の、3重ループを書いた。後は衝突判定か……。
っていうか、これ合ってるならlargeも時間計算量は余裕だけど……。
追い越される車の速度 ≦ 追い越す車の速度 ≦ それをさらに追い越そうとする車の速度
として、追い越される車 が 追い越され始める瞬間だけチェックすればいいのかな？
えーと衝突判定関数は……幅が5メートルだからー……こうか。
あれ、なんか違う。うーん。

あと10分……。あ、順位ここに出てたのか。
現時点で990位？　これは出せなくてもギリギリ通ったり、する？ω

判定関数がなんかおかしいよなー。見る条件間違ってるかなー。
ちょこちょこ書き換え、テスト。わー、全部Possible返ってきたー。
残り時間あと30秒！　わぁい ＼(^owata^)／

終わり

なんか、結果もう出てる。早い。
これ確定？　確定らしい。849位。AもB通ってた。安堵。

SRMでもCfでも、何かしらプロコンが終われば、その途端にそれまで静かだった僕のTLが加速する。
みんな思い思いに感想をつぶやくので、TLは賑わうだけど、ほとんど＠がなくて、
あっても、 上位入賞おめでとうございます！ とかそんなんがちらほら散見される程度。
コミュニケーションらしいものはほとんどないのに、それでも、
ただ眺めてて面白いTLになることは間違いなくて、結構その時間が好きだったりする。

30分後ぐらいに問題の解説が公開された。
Cの解説がめっちゃ長いな－。
「洞察力と正確な実装力を要するチャレンジングな問題でした。」までしか読んでないけど。
めっちゃ長いから、ここで書いたみたいな単純な解法じゃないんだろなー。
こういうの読まないで放置するから、いつまでたっても私は黄色なのだろうなー。
これから読む(読んでから書け

ICPC出てたころは、計算機な日記 カテゴリでよかったけど、
最近は、どっちかというと ゲーム日記::その他プロコン が正しいと思う。
そのうちまとめてカテゴリ移動しよう。(そのうち、って書いたからしないかも)