AtCoder Beginners SelectionをOCamlで（中編）
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
（この記事はSome Sums, Card Game for Two, Kagamimochi, Otoshidamaの４問について）
ABC083B - Some Sums
0~Nまでの数で、各桁の合計がa以上b以下になるものを合計する。
open Batteries let add_digits x = string_of_int x |> String.explode |> List.map (fun x -> int_of_char x - 48) |> List.fold_left (+) 0 let n, a, b = Scanf.scanf "%d %d %d" (fun n a b -> n, a, b) let ans = Enum.range 1 ~until:n |> Enum.filter (fun x -> let y = add_digits x in a <= y && y <= b) |> Enum.reduce (+) |> string_of_int let () = print_endline ans
問題をそのままコード化できたように思うがどうだろうか。
ABC088B - Card Game for Two
交互に数字の書いてあるカードをとっていくゲームで、お互いに最善を尽くした場合の点差を計算する。
open Batteries let rec diff_two n = function | [] -> n | [x] -> n + x | x :: y :: zs -> diff_two (n + x - y) zs;; let _ = read_line () let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> diff_two 0 |> string_of_int let () = print_endline ans
降順にソートされた数字の奇数番と偶数番の和の差。
List.sort (flip compare)で逆順ソートになるのは思いつけてよかった。(fun a b -> - (compare a b)とか書くのかなー、いやだなーと思っていたので・・・
逆に再帰でdiff_twoを書いているのは少し不満がある。なんらかの高階関数を組み合わせて表現できないものか・・・
今ふとこんな解も思いついたが
let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> List.fold_left (fun (n, m) x -> (n + (m * x), - m)) (0, 1) |> fst |> string_of_int
これはちょっと問題固有の部分に引きずられすぎているだろうか？あまりテクニックとして汎用性がなさそうにも見える。
ABC085B - Kagami Mochi
いくつかの直径の餅を「下にある餅は必ず上にある餅よりも直径が大きい」という制約でいくつ積み重ねることができるか。
open Batteries module S = Set.Make(Int) let n = read_int () let ans = List.init n (fun _ -> read_int ()) |> S.of_list |> S.cardinal |> string_of_int let () = print_endline ans
ユニークな直径の数を求めればいいのでSetを使う。OCamlだとSetはFunctor（モジュールをうけとりモジュールを返す「関数」）なので、Batteriesで定義されているIntモジュールを渡すことで整数を要素にとる集合を表すことができる。
あとはList.init n (fun _ -> read_int ())でn行に渡る整数の入力値をリスト化し、S.of_listで集合化し、S.cardinalで要素数を数えてstring_of_intで文字列化する。
ABC085C - Otoshidama
10000円札、5000円札、1000円札を合計N枚使ってY円を作ることができるか。
open Batteries open Enum.Infix let n, y = Scanf.scanf "%d %d" (fun n y -> (n, y)) let f i = let z = (y - 10000*i - 1000*(n-i)) / 4000 in (i, z, n - i - z) let p (a, b, c) = y = a * 10000 + b * 5000 + c * 1000 && 0 <= a && 0 <= b && 0 <= c let xs = Enum.map f (0--(y / 10000)) let ans = let a, b, c = try Enum.find p xs with Not_found -> (-1, -1, -1) in Printf.sprintf "%d %d %d" a b c let () = print_endline ans
「5000円札、1000円札を合計N枚使ってY円を作る」というのはつるかめ算的なサムシングなので、それをまずf関数で表す。
ただし、5000円札A枚、1000円札B枚のAとBが整数でなかったり片方が負数だったりする場合を排除しないといけないので、そのためのp述語を定義する。
あとはEnum.Infixに定義された--演算子でrangeを手軽に表したものにfでmapし、`try＋Enum.find pで合致する要素を探し、見つからなかった場合はNot_foundをキャッチして(-1, -1, -1)を返している。Enum.Infixは継続して使うか少し悩むところだ・・・ （関数でも同じことができるのと、ぱっと見で理解しやすいか微妙な気がするため）
あと今回も入力が一行のみなのでScanf.scanfを使っている。
やはり長くなってきたので後編に続く。
