HaskellでGCJ (反省会 - Google Code Jam 2012 - Round 1-A Problem A)

B-small, B-largeをつまらないミスでWAしてeliminateされました。
本番に弱いなあ、まったく。

なんか悲しいので、勉強ついでにHaskellで解答を組んでみました。
入力パーサのコツを見つけるのにずいぶん手間取りましたが、なんとか以下の形になりました。
なにぶん初心者なので、よりシンプルな書き方があったらぜひコメントください。

まずは入力パーサの方式について。
IOアクションで、1行毎に数値1つ、および数値のリストを入力します。

数値1つを取得するIOアクション

IOモジュールのreadLnライブラリを利用します。
これは、標準入力から読み込んだ行をread関数で任意の型に変換して返してくれます。
入力したい値の型指定を、「IO a」の形で記述するのが最初はわかりづらいような。

数値のリストを取得するIOアクション

標準で良いライブラリが見つからなかったので、シンプルになるように作ってみました。
gcjの入力はスペースで区切られているので、wordsで個々の文字列のリストに分割してから
map関数でreadを適用します。
「mapM readIO」は「return . (map read)」と等価とのことで。

上記のIOアクションを用いて、入力をパースするアクションを組み立てます。

データ1つぶんを取得してタプルにするアクション


データを取得しながら、問題を解いて解答を表示するmainアクション

「sequence $ replicate t 」にたどり着くのには手間取りました。
「replicate t (IO a)」で問題数ぶんのIO aを生成し、sequence関数でIO aを順に実行します。
これでgetDataの結果のリストを取得するアクションを生成できるので、
「map solve ds」で解のリストを生成します。

あとはzip関数で問題番号と解の組みをタプルにし、format関数で解答文字列にして
purStrLnで表示します。
これ、mapを二重にかけるのってどうなのでしょうね？一重で行けないかな？

問題を解くアルゴリズムは、solve関数以下に実装します。
関数5つだけ。こういう問題は関数型に向いているのかな。

[p1, p2, ..., pA]から、[p1, p1*p2, p1*p2*p3, ..., p1*p2*p3*...*pA]を生成する関数initproductsを
作るのも時間がかかってしまいました。

初め、List.initsしたリストをproductsして生成しようとしたらまあ遅い遅い。

ex1関数は、

を変形した結果です。
文字の先頭からi文字目までBSで戻った場合、で計算しているので、(a-i)で計算しています。
A文字すべてをBSで消すパターンは、a+b+1 > b+2なので計算しないようにしています。
(zipの第一引数のリスト生成で[1..a]にしているところ)

一つ目のrealToFracは引数をカッコでくくらないとコンパイルが通りませんでした。なんでかな？

ghc -O2でコンパイルして、A-largeのサイズで解答時間は15秒くらいでした。
追記

> これ、mapを二重にかけるのってどうなのでしょうね？一重で行けないかな？

そんなに難しくなかった。

mapM_ (putStrLn . format . solve ) $ zip [1..t] ds

に書き換えて、

solve関数を

solve :: (int, (Int, Int, [Double])) -> (int, Double)
solve (n, (a, b, ds)) = (n, minimum $ (realToFrac b+2) : (exs a b ds))

にするだけで行けました。
なんか無駄な気もするけれど、実行速度はすこし上がりました。

タグ：Haskell gcj Google Code Jam