2012-04-28 [長年日記]
λ. Google Code Jam 2012 : Round 1A
A-Largeの予想外の不正解で Rank: 1274 Score: 43 となってしまいパスできず。(id: sakai で参加中)
Problem A. Password Problem
即座にenterを押して全文字入力し直すのと、バックスペースを何回か押して残りを入力するのと、全部期待値を計算して、その最小を取れば良い。 Smallは超素朴に計算(A.hs)。 Largeは適当に実験すると非常に時間がかかったので、全部の確率の積を毎回計算しないようにした(A2.hs)。 ただ、全部の積を計算してから要らないやつで割るという方法を取ってしまっていて、そのせいで計算誤差が蓄積してしまったようで不正解を食らってしまっていた。 逆に順番に掛けていくようにしたら、正しく計算できるようになったようだ(A3.hs)。 浮動小数点数の誤差でハマったのは生まれて初めてかもしれない。 あるいはいっそ有理数で計算していればよかったかも。
Problem B. Kingdom Rush
2-star rating でまだクリアしていなくて今クリアできるレベル(1-star rating でクリア済みのものを含む)がある場合には、それを選んでいけば良い。 問題は 2-star rating でクリアできるレベルが存在しない時に、どのレベルを 1-star rating でクリアするか。 Smallはまずは全通り試して最短手数のものを選択する方法で解いた(B2.hs)。 Largeはそれだと解けないので、レベル選択をちゃんと考える必要がある。 直観的には、(今 1-star rating でクリアできる未クリアのレベルのうち) 2-star rating に必要なスター数が大きいものは、その後スターが増えても一気に 2-star rating でクリアできる見込みは小さい。そこで、2-star rating に必要なスター数が最大のものを(諦めて) 1-star rating でクリアするようにしたら、Smallのデータセットの範囲では結果が一致したので、それで(B3.hs)。
Problem C. Cruise Control
任意の二つの車について初期位置と速度から隣り合ってもしくは重なってしまう時間を計算し、これを各車ごとに車線変更不可能な時間として保持。 その上で、初期時刻および何れかの車が車線変更不可能な時間に入るタイミングを順番に見ていき、そのタイミングであり得る車の車線の配置の全可能性を考える。 全可能性を考えるには、前のタイミングで在り得た配置をもとに、そのタイミングで車線変更可能な車を任意に車線変更したものを考えれば良いはず。 そうやって初期時刻から順に見ていき、可能な全ての配置で衝突状態になっている最初の時刻が答え。 車線変更不可能なタイミングに入るタイミングを全部見終わってそういう時刻がないなら、Possible が答え。
……と思ったんだけど、実装は間に合わず。
