日々の流転

λ. Google Code Jam 2009: Round 1A

参加はしてないけど、また解いてみた。 Qualification Round は楽勝な感じだったけど、今回はさすがに難易度があがってるのね。 私には二時間半の時間内に全問解ける気がまるでしない……

A. Multi-base happiness

素朴に、各基底に対してその基底でハッピーな数の集合を昇順の無限リストとして定義しておいて、それらの共通部分の最初の要素として解を定義した。 Largeは数分かかってしまったけど、なんとか解けた。 基底に対するハッピーな数の集合だけじゃなくて、基底の集合に対する解の集合も再利用するようにすれば、テストケースを越えて計算を共有できて、Largeももっと速くなるかなぁ。

• A.hs

B. Crossing the Road

「Project Euler の Problem 15 をちょっと面倒にしたようなものか。これならDP一発で楽勝」と思って解いたら、サンプルは通るけど B-small-practice.in をパスしない。 数時間悩んで*1、ようやく南から北、西から東だけでなく、北から南、東から西へ移動することで時間が短縮できる場合(B-small-practice.in だと Case #5 と Case #6)があることに気づく(死亡確定)。 仕方がないので、後から逆向きも見て小さいほうを選ぶというのを収束するまで繰り返すようにした。ちょっとどうかと思ったが、一応Largeでも一瞬で解けたのでよしとする。

• B.hs

C. Collecting Cards

確率とか私には無理すぎる。 立てた式が間違っていて、何故答えが合わないのか数時間*2悩んでしまった(死亡確定)。 確率についてはもう少し慣れておくべきと思った。

• C.hs