競プロは初心者でPythonで時々AtCoderに参加する程度なので、OCamlと競プロを一緒に勉強してみようという魂胆です。

標準入力を読む

read_line (): 一行読んで文字列型で受け取る
read_int (): 一行読んで整数型で受け取る

一行をうけとってリストとして解釈する

例：で区切って複数の整数値が送られるので、それをint listにする

let read_int_list () =
  String.split_on_char ' ' (read_line ())
  |> List.map int_of_string

let lst = read_int_list ()

回答の提出

print_int 整数
print_string 文字列
print_endline 文字列

出力が発生する関数をいくつも並べる場合には;で区切って関数の入力範囲を明示する。

例：整数値文字列で出力したい

let () =
    print_int n;
    print_string " ";
    print_endline s;

やおふぁい

Beginners Selection A

b cの形で送られる整数型２つを取り出すのを

f lst = match lst with
    | x::y::_ -> x + y
    | _ -> 0

とパターンマッチにするのがやや冗長に感じる。

やおふぁい

OCamlでBeginners Selectionを解かれている方の解説を発見
https://zehnpaard.hatenablog.com/entry/2019/02/04/123417
https://zehnpaard.hatenablog.com/entry/2019/02/05/113710
https://zehnpaard.hatenablog.com/entry/2019/02/06/114255

やおふぁい

Scanf.sscanfという便利な関数を発見。

パースに使う文字列を解釈しないと関数の型を特定できないはずだが、どうやら型安全らしい。すごい。

Scanf.sscanf 文字列 パースに使うformat パース結果を使った関数

例：b cの形式で与えられる２つの整数を足す

Scanf.sscanf (read_line ()) "%d %d" (fun b c -> b + c)

やおふぁい

Beginners Selection 3

Char型の一文字の数字を整数として解釈するためにChar.code c - Char.code '0'を使ったけど、もっといい方法がありそう。

let a = read_line ()
let base = Char.code '0'

let () =
  print_int @@ String.fold_left (fun acc c -> acc + Char.code c - base) 0 a;
  print_endline "";

やおふぁい

Beginners Selection 3の鮮やかな回答

let () = Scanf.scanf "%1d %1d %1d" (fun a b c -> a+b+c)
  |> string_of_int
  |> print_endline

formatでは%1dで数値を一桁だけとってこれる

やおふぁい

Beginners Selection 3の別解

文字列をリストにしてList.fold_leftで畳み込む

let count_ones s =
  let chars = List.of_seq (String.to_seq s) in
  List.fold_left (fun acc c -> if c = '1' then acc + 1 else acc) 0 chars

let () =
  let s = read_line () in
  let result = count_ones s in
  print_int result;
  print_newline ()

やおふぁい

Beginners Selection 4

ただ、List.left_foldを使った方がわかりやすそうなので書き直し：

let read_int_list () =
  String.split_on_char ' ' (read_line ())
  |> List.map int_of_string


let n = read_int ()

let rec max_shift n
  = if n mod 2 = 0 then 1 + max_shift (n / 2) else 0



let () = read_int_list ()
  |> List.fold_left (fun acc a -> min acc (max_shift a)) max_int
  |> string_of_int
  |> print_endline

やおふぁい

Beginners Selection 5

手続き型で書いたほうがわかりやすそうな問題、敢えて関数型で書く必要あるか？

let a = read_int ()
let b = read_int ()
let c = read_int ()
let x = read_int ()

let rec solve ka kb kc cnt =
  let
    amount = 500 * ka + 100 * kb + 50 * kc
  in
    if kc > c then solve ka (kb + 1) 0 cnt
    else if kb > b then solve (ka + 1) 0 0 cnt
    else if ka > a then cnt
    else (
      if amount < x then solve ka kb (kc + 1) cnt
      else if amount = x then solve ka kb (kc + 1) (cnt + 1)
      else solve ka (kb + 1) 0 cnt
    )

let () =
    print_int (solve 0 0 0 0);
    print_endline "";

やおふぁい

より関数型っぽいIterモナドを使った回答

let a = read_int ()
let b = read_int ()
let c = read_int ()
let x = read_int ()

let () =
  Iter.(
    0 -- a >>= fun i ->
      0 -- b >>= fun j ->
        0 -- c >>= fun k -> return (500 * i + 100 * j + 50 * k)
  )
  |> Iter.filter_count (fun s -> s = x)
  |> string_of_int
  |> print_endline

モナドやbind演算子をどこまで理解したかは別として以下のように理解した。

Iter.(
    (* a -- b: aからbまでの範囲で遅延評価される整数値の列を作成 *)
    (* >>=: bind演算子、Iterでは直前の列の各要素を後の関数に渡す *)
    a -- b >>= fun i -> 式
)

デカルト積の全要素に対して実行する場合は結構使いやすそう。

やおふぁい

Beginners Selection 6

なかなかうまくいかず苦戦してついにAC

整数のべき乗は自分の競プロテンプレートに追記しておこう

let rec int_power a n = if n = 0 then 1 else a * int_power a (n - 1)

やおふぁい

各桁の和を求めるの、こんなに単純に書けるんだ！

let rec f v =
  if v < 10 then v else
  (v mod 10) + f (v/10)

入力が10より大きい場合には、その最下位だけ取得（v mod 10）して和にする
入力が10以下であれば、その値を返す

やおふぁい

Beginners Selection 7

let read_int_list () =
  String.split_on_char ' ' (read_line ())
  |> List.map int_of_string


let n = read_int ()
let a = read_int_list ()

let rec solve rem diff alice =
  match rem with
      [] -> diff
    | x::xs -> if alice then solve xs (diff + x) false else solve xs (diff - x) true

let rev_compare a b = compare b a

let ()
  = solve (List.sort rev_compare a) 0 true
    |> string_of_int
    |> print_endline

使う関数に多少差はあれど、みな並び替えて順に正負を入れ替えながら足していく感じ

やおふぁい

Beginners Selection 8

同じ大きさのものは重ねられないので、要は異なる要素を数えればいい。
自分は再帰関数を作るときにいらない引数を設定してしまう傾向がある。。

let n = read_int ()

let rec solve rem lst
  = if rem = 0
    then 0
    else (
      let elem = read_int () in
      if List.mem elem lst
        then solve (rem - 1) lst
        else 1 + solve (rem - 1) (elem::lst)
    )

let ()
  = solve n [] |> string_of_int |> print_endline

やおふぁい

Beginners Selection 8
要素のダブりを排除するだけだから標準で提供されている機能やデファクトのライブラリを使うことができる。
List.sort_uniq

List.unique (batteriesライブラリ)

やおふぁい

Beginners Selection 9

let n, y = Scanf.scanf "%d %d" (fun n y -> (n, y))

let _ =
  Iter.(
    0 -- n >>= fun a ->
      0 -- (n - a) >>= fun b -> return (let c = n - a - b in (a, b, c))
  )
  |> Iter.filter (fun (a, b, c) -> 10000 * a + 5000 * b + 1000 * c = y)
  |> Iter.head
  |> fun res -> print_endline @@ match res with
      | None -> "-1 -1 -1"
      | Some (a, b, c) -> (string_of_int a) ^ " " ^ (string_of_int b) ^ " " ^ (string_of_int c)

Iterの型を勘違いしているのか、以下で行けると思ったがうまくいかない

...
  |> Iter.head
  |> fun res -> match res with
      | None -> "-1 -1 -1"
      | Some (a, b, c) -> (string_of_int a) ^ " " ^ (string_of_int b) ^ " " ^ (string_of_int c)
  |> print_endline

やおふぁい

Beginners Selection 10
追加される順番を逆に回して後ろから単語を削除していく操作で空文字にもどれるかをシミュレート

let remove_suffix suffix s = String.sub s 0 (String.length s - (String.length suffix))

let rec remove_tail s =
  if
    String.ends_with ~suffix:"dream" s       then remove_tail @@ remove_suffix "dream" s
  else if String.ends_with ~suffix:"dreamer" s then remove_tail @@ remove_suffix "dreamer" s
  else if String.ends_with ~suffix:"erase"   s then remove_tail @@ remove_suffix "erase" s
  else if String.ends_with ~suffix:"eraser"  s then remove_tail @@ remove_suffix "eraser" s
  else s


let () =
  let s = read_line () in (remove_tail s)
  |> fun x -> (if String.length x = 0 then "YES" else "NO")
  |> print_endline

やおふぁい

Beginners Selection 10
https://atcoder.jp/contests/abs/submissions/49201886
自分でロジックを実装するよりおそらく最適化されているであろう標準提供の正規表現を使った方がコードもきれいで速度もでるのであった

やおふぁい

Beginners Selection 11 (最後)

OCamlでACしている中ではかなり短めに実装できた

let rec solve k t0 x0 y0 =
  if k = 0 then "Yes"
  else let (t1, x1, y1) = Scanf.sscanf (read_line ()) "%d %d %d" (fun a b c -> (a, b, c)) in
    if abs (x1 - x0) + abs (y1 - y0) <= t1 - t0 && ((abs (x1 - x0) + abs (y1 - y0) - (t1 - t0)) mod 2 = 0) then solve (k - 1) t1 x1 y1
    else "No"

let () = print_endline @@ solve (read_int ()) 0 0 0

やおふぁい

次は典型問題か動的計画法のどちらかのコンテストを教材にします

やおふぁい

EDPC 1
https://atcoder.jp/contests/dp/submissions/62957765
let read_int_list () =
  String.split_on_char ' ' (read_line ())
  |> List.map int_of_string

let n  = read_int ()
let hs = read_int_list ()

let rec solve i = match i with
  | 0  -> 0
  | 1  -> abs @@ List.nth hs 0 - List.nth hs 1
  | _  -> let
    step d = (solve @@ i - d) + abs (List.nth hs (i - d) - List.nth hs i)
  in
    min (step 1) (step 2)

let ()
  = solve (n - 1)
  |> string_of_int
  |> print_endline
素直な再帰による実装だと思うけどTLE。おそらく同じ値を何度も計算していることが原因。
メモ化で解消できないかなと思い、Hashtblを使って実装。
https://atcoder.jp/contests/dp/submissions/63086657
しかしこれでもダメ。
原因はListはランダムアクセスが遅いことで、代わりにArrayを使う必要があった。
https://atcoder.jp/contests/dp/submissions/63094389
let read_int_array n =
  Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0

let n  = read_int ()
let hs = read_int_array n

let memo_rec size f =
  let h = Hashtbl.create size in
  let rec g x =
    try Hashtbl.find h x
    with Not_found ->
      let y = f g x in
      Hashtbl.add h x y;
      y
  in
    g

let solve =
  let f self i = match i with
    | 0  -> 0
    | 1  -> abs @@ hs.(0) - hs.(1)
    | _  -> let
      step d = (self @@ i - d) + abs (hs.(i - d) - hs.(i))
    in
      min (step 1) (step 2)
  in
    memo_rec n f


let ()
  = solve (n - 1)
  |> string_of_int
  |> print_endline
ちなみにメモ化を付けずにArrayのランダムアクセスだけで実装してもTLEになってしまうので、両方必要。

やおふぁい

EDPC 2

EDPC1を少し一般化するだけなので特に変わったことはなさそうです。

(* minの一般化 *)
let rec min_k i step = if i = k + 1 then max_int else min (step i) (min_k (i + 1) step)