AtCoder Beginners SelectionをOCamlで（前編）
以前DP問題を解いてみたこともあったように、親和性は高いように思う。
具体的には、関数型・命令型どちらでも表現力が高く、実行過程の予想がつきやすく、コンパイルされるので早い、という利点がある。いろんな方面から嫌がられそうな表現だが、「早いPythonとして使えそう」というのが個人的な思惑。
とはいってもいろいろと文法もライブラリも流儀も違うので、練習のためにまずAtCoder Beginners Selectionをやってみた
PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）
まずはAtCoderでの入出力を試す練習問題。
OCamlだと入出力関数にread_int, read_line, Scanf, print_int, read_endline, Printfなどいろいろあってどれをどう使うのがいいか、ちょっと考えどころかもしれない。
とりあえず現在の自分のスタイルだとこんな感じ：
let n = read_int () let a, b = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> (a, b)) let s = read_line () let ans = Printf.sprintf "%d %s" (n + a + b) s let () = print_endline ans
Scanf.scanfという直接stdinから文字列をとってパースする関数もあるのだが、入力が複数行に渡る場合よく問題が起きるので使わないことにしている。多分改行のパースなどでエッジケースがあったりするのではないかと思うのだが・・・
なので単一の整数を取る場合はread_int、複数の場合はいったんread_lineとった文字列をScanf.sscanfでパースするようにする。
Scanf.sscanfは第三引数に関数を取り、パースした値をさらにどのようにでも加工できる。が、それはできるだけ使わないほうが読みやすいと思う。単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。
あと最終的に答えをlet () = ...で出力するのだが、そこはほぼ決め打ちでlet () = print_endline ansにして、その上の方でansの文字列を作成するようにしている。print_intなども使いたくなるが、それだと改行が入らないのでどうせもう一手間必要になる。それよりは文字列を作成して、それを最後の行でprint_endlineで出力することに決めた方が考えることを減らせていい。
ABC086A - Product
一行の入力に含まれている二つの整数の積の偶奇を判定する。
let x = Scanf.scanf "%d %d" (fun a b -> a * b) let ans = if x mod 2 = 0 then "Even" else "Odd" let () = print_endline ans
はやくも自分の言った
単一の整数を取る場合は
read_int、複数の場合はいったんread_lineとった文字列をScanf.sscanfでパースするようにする。（
Scanf.sscanfからは）単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。
という考えを破っているが、まあこれくらいはいいのではないか。受け取る入力が一行だけで、それに対する処理も一目でなにが起きているかわかるし。
ABC081A - Placing Marbles
三つの文字が1の値をとる回数を数える。
open Batteries let ans = read_line () |> String.explode |> List.map (fun c -> int_of_char c - 48) |> List.fold_left (+) 0 |> string_of_int let () = print_endline ans
文字が取り得る値が0か1なので各桁を足し合わせればいい。
- 入力を受け取り
- 文字列を文字のリストに変換し
- 各文字を数値に変換し
- 足し合わせ
- 数字を文字列化する
あとは今までどおりその文字列を出力するだけ。
OCamlの標準ライブラリ拡張のひとつであるBatteriesがAtCoderでも使えるので、open BatteriesしてString.explodeとint_of_charを利用する。あと|>パイプ演算子でできるだけ直線的に計算の流れを表す。
ABC081B - Shift only
複数の数字を２で割り切りつづけられる回数を数える。
まずは再帰を使った解：
open Batteries let _ = read_line () let xs = read_line () |> String.split_on_char ' ' |> List.map int_of_string let rec f n = let m = Int.pow 2 (n+1) in if List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n let ans = string_of_int @@ f 0 let () = print_endline ans
入力を変更はせず、2 ** (n+1)ですべての数が割り切れたら次のnを調べる、という意味の
List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n
がキモになっている。
つぎに再帰ではなく無限の遅延リストを使った解：
open Batteries let _ = read_line () let xs = read_line () |> String.split_on_char ' ' |> List.map int_of_string let p n = let m = Int.pow 2 (n+1) in not (List.for_all (fun x -> x mod m = 0) xs) let ans = Enum.range 0 |> Enum.find p |> string_of_int let () = print_endline ans
Batteriesで定義されている遅延リストEnumを利用している。
Enum.range 0で0からはじまる無限の数列を作るEnum.findでその無限リストからnot (List.for_all (fun x -> x mod m = 0) xs)があてはまる最初の数を見つける
この問題だとまだそこまで有り難みがないが、無限リストとそれに対する処理、無限リストから他のデータ構造への変換などを多く定義しているEnumモジュールはかなり便利。Pythonでいうところのgeneratorとitertoolsにあたる概念である。
ABC087B - Coins
500円A枚、100円B枚、50円C枚から合計X円になる組み合わせ方は何通りあるか。
open Batteries let a = read_int () let b = read_int () let c = read_int () let x = read_int () let p n = n mod 50 = 0 && n / 50 <= c let count n = Enum.init (b+1) (fun i -> n - i*100) |> Enum.take_while ((<=) 0) |> Enum.filter p |> Enum.hard_count let ans = Enum.init (a+1) (fun i -> x - i*500) |> Enum.take_while ((<=) 0) |> Enum.map count |> Enum.reduce (+) |> string_of_int let () = print_endline ans
- 「50円C枚からX円を作ることができるか」を判定する関数
pを作成 pを使って「100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算する関数countを作成countを使って「500円A枚、100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算
この解ではEnumの各種関数を多用している。
Enum.init n fで(f 0, f 1, ... f (n-1))という遅延リストを作成Enum.take_while p xsで遅延リストxsの先頭から述語pを満さない初めの要素までを含む新しい遅延リストを返す。（述語pを満さない要素は含まれない）Enum.filter p xsで遅延リストxsの述語pを満たす全ての要素を含む新しい遅延リストを返すEnum.hard_count xsで遅延リストxsの要素数を返す。Enum.map f xsで遅延リストxsの各要素に対して関数fを適用した新しい遅延リストを返すEnum.reduce f xsでxsの第一要素を初期値としてfold的にf関数を累積的に適用した値を返す
と遅延リストやストリームでおなじみの関数群を使っている。
これらや他の遅延リスト関連の関数については
に詳細が載っていて、このページをずっと読み返しながら解いていた。はやく自然と使いこなせるようになりたい。
長くなってきたので後編中編に続く。
