AtCoder Beginners SelectionをOCamlで（後編）
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
今回は最後の２問、白昼夢 / DaydreamとTravellingの解法とOCamlを使った所感。
ABC049C - 白昼夢 / Daydream
ある文字列が、"dream", "erase", "dreamer", "eraser"の四語のどれかを繰り返すことで作られているかを判定する
open Batteries let s = read_line () |> String.explode |> List.rev let rec f = function | [] -> true | 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | _ -> false let ans = if f s then "YES" else "NO" let () = print_endline ans
"dream"と"dreamer"、"erase" "eraser"と先頭から読んでいくと候補が重複してしまう。バックトラックするようなロジックも考えられるが、この四語だったら一番楽なのは後ろからパースすることだろう（後ろから見ると重複する候補はないため）。
OCamlのリストと文字がパターンマッチ可能なことを利用した再帰関数でパースできる。
ABC086C - Traveling
格子上の点を特定のスケジュールで移動できるかどうかを判定する。
open Batteries let parse_triplet s = Scanf.sscanf s "%d %d %d" (fun a b c -> (a,b,c)) let diff ((_,_,_), (a,b,c)) (x,y,z) = ((x-a,y-b,z-c), (x,y,z)) let pred (a, b, c) = let d = abs b + abs c in a >= d && a mod 2 = d mod 2 let n = read_int () let x = Enum.init n (fun _ -> read_line ()) |> Enum.map parse_triplet |> Enum.scanl diff ((0,0,0), (0,0,0)) |> Enum.map fst |> Enum.for_all pred let ans = if x then "Yes" else "No" let () = print_endline ans
スケジュールは時間順に与えられるので、隣接するスケジュールの差だけを調べていけばいい。
スケジュールの差が可能かどうかの判定は以下の二点：
- 移動量は時間内に収まるか
- 移動量と時間の偶奇が一致するか（余った時間は２つずつ無駄に消費することが可能なため）
Enum.scanlはfoldに似ているけど、foldでいうところの中間結果をすべて要素として持つ遅延リスト。
Enum.scanl f x (a1; a2; a3)は(x; f x a1; f (f x a1) a2; f (f (f x a1) a2) a3)となる（ここでは(x;y;z)はx``y``zを要素に持つ遅延リストだとする）。
これを使って「差額の遅延リスト」を作成して、すべてが上記の二点を満たしているかをEnum.for_allで判定している。
OCamlをAtCoderで使ってみて
OCamlは去年の１０月くらいからかれこれ四ヶ月ほど（業務外で・・・）使っていて少しは慣れてきたと思うのだが、主に言語実装系のことばかりしていたので競技プログラミングは勝手がけっこう違った。言語処理系の実装だとASTなどの処理のために「再帰関数でパターンマッチ」が多くなるのだが、AtCoder Beginners Selectionではあまり木構造をどうこうすることもなく、直線的かつフラットにデータ変換のロジックを書いていくことが多かった。
OCamlは|>演算子やEnumの各関数などで十分そのような書き方もできる言語だとわかったのは嬉しい。
個人的にはOCamlの命令型でも記述できるところはすごく便利だと思っているのだが、振り返ると一度もref、Array、Hashtblなどの破壊的代入が可能なデータやforループなどの命令的な構文などを使う必要がなかった。Dynamic Programmingなどでは絶対必要になってくると思うが、Batteriesのモジュールや関数、とくにEnum関連を使いこなせば関数型プログラミングのスタイルだけでもかなりの処理を（しかもそれなりに宣言的に）記述できることも実感できた。個人的にはこれはPythonなどでも感じていたことだが・・・
Pythonとは実行速度が比較にならないほど早い、という点もAtCoder向きだ。
比較のためにOtoshidamaをPythonとOCamlで同じ（意図的にアルゴリズムの良さよりも記述の明快さを重視した）ロジックで書いてみた：
Pythonの内包表記的なgenerator expressionは記法としてはやはりすごく好きだ・・・ がほぼ完全に一致するロジックのコードで、Pythonが719 ms、OCamlが58 msで十倍以上の差がある。コードが煩雑になるような定数倍最適化を行わなくてはならない、というケースが減りそうでとても魅力的。
というわけでこれからもちょくちょくOCamlでAtCoderの過去問を解いていこうと思う。ArrayやHashtblなどを使ってDPやUnion Find Treeなどの問題を解いていって、それらの記法にも馴染んできた時点で実際のコンテストにもまた参加したい。まずは最近開催されたEDPCの問題かな・・・
