AtCoderに登録したら解くべき精選過去問10問をStandard MLで解いてみた

# はじめに

[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)を様々な言語で解くのが流行っているようなので，便乗してStandard ML (SML)でやってみました．SMLを知らなかった型にはこの機会に興味を持って頂いて，全国10人ぐらいのSMLプログラマの皆さんには競プロに興味を持って頂ければ幸いです．

# SMLとは?

強い静的型付きの，純粋*ではない*関数型言語です．そう聞くとOCamlっぽいなと思うしょうが，それもそのはず．SMLはOCamlと祖を同じくする親戚のような言語です．元々は名前の通りML系の言語のstandardになるよう設計されたんでしょうけど，de facto standardの座をOCamlに奪われてる辺り不憫ですよね．

一応SMLには言語仕様が厳密に（操作的意味論レベルで）決まっていて，数多くの個性的な処理系が存在するメリットがあります．思いつくだけでも

* Standard ML of New Jersey (SML/NJ)
* MLton
* Moscow ML
* MLKit
* Poly/ML
* SML#

とか色々ありますね．今でこそマイナー言語なSMLですが，プログラミング言語の研究に盛んに用いられてきた歴史があり，リージョン推論や多相レコード，篩型といった様々な概念のゆりかごとなりました．研究者達はSMLをベースに，最新の研究を反映させて想い想いのSML処理系を作ってきたのです．

まぁしかし，手っ取り早く手元で試したい場合は有名どころの，[SML/NJ](https://www.smlnj.org)を入れておけば十分でしょう．そこそこ速いし，対話環境もあって便利です．AtCoderに入っているのは[MLton](http://mlton.org)ですが，対話環境が付いていない上にコンパイルが壊滅的に重いので，手元でテストするのにはお勧めしません．
これだけ聞くとMLtonが駄目な処理系に思えますが，こちらには非常に速いコードを生成してくれる長所があります．トレードオフですね．OCamlが速いのは有名ですが，下手をすればMLtonの方が速いんじゃないでしょうか．定数倍に泣かされなくなる点では競プロに向いた処理系と言えるでしょう．

あまりSMLについて詳しく解説してもSMLの入門記事になってしまいますから，この辺で止めておきましょう．詳しい説明が読みたくなったら[プログラミング言語Standard ML入門
](http://www.kyoritsu-pub.co.jp/bookdetail/9784320120242)なんかが良いと思います．

# [PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）](https://abs.contest.atcoder.jp/tasks/practice_1)

こんな感じのコードを提出しました．

```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME a = readInt ()
val SOME b = readInt ()
val SOME c = readInt ()
(* skip newline *)
val _ = TextIO.inputLine TextIO.stdIn
val SOME s = TextIO.inputLine TextIO.stdIn

val () = print (Int.toString (a + b + c) ^ " " ^ s)
```

HaskellやOCamlなんかと似たような感じなんですが，SMLのプログラムって大雑把に言うと定義の列なんですよね．`fun x p1 ... pn = e`ってのが関数定義で，`val p = e`が変数定義．それらが上から順に評価されていって，その時の副作用で入出力が行われます．

SMLで入出力を扱うには主に[標準ライブラリ](http://sml-family.org/Basis/index.html)の`TextIO`モジュールの関数を使います．標準入力から1行文字列を読み取るには`TextIO.inputLine TextIO.stdIn`とやれば良いのですが，終端の改行も付いてくる（最悪）ので注意が必要です．
整数を読み取るには一癖が必要で，パーサーコンビネータみたいなやつを受け取って読み取りを行う`TextIO.scanStream`を使うことになるでしょう．まぁでも，整数を標準入力から読み取るときは

```sml
TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
```

と書くとか，浮動小数点数を標準入力から読み取る時は

```sml
TextIO.scanStream Real.scan TextIO.stdIn
```

と書くとか，「型」で覚えておけば良いと思います．長いので関数にしても良いですね．

```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn

fun readReal () =
  TextIO.scanStream Real.scan TextIO.stdIn
```

標準ライブラリには無いですがprintfとかscanfみたいなのも一応，[書こうと思えば書けます．](http://mlton.org/Printf)

# [ABC086A - Product](https://abs.contest.atcoder.jp/tasks/abc086_a)
```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME a = readInt ()
val SOME b = readInt ()
 
val () =
  print (if (a * b) mod 2 = 1 then "Odd\n" else "Even\n")
```
剰余を取りたい時は`e1 mod e2`と書きます．SMLは記号以外も二項演算子にできるんですよね．高階関数に渡したい時とか，普通の関数に戻したい時は`op mod`って書くと良いです．

# [ABC081A - Placing Marbles](https://abs.contest.atcoder.jp/tasks/abc081_a)
```sml
val SOME s = TextIO.inputLine TextIO.stdIn
val n = length (List.filter (fn c => c = #"1") (explode s))
val () = print (Int.toString n ^ "\n")
```

~~爆裂魔法~~`explode`を用いれば文字列（`string`）を文字のリスト（`char list`）に変換できるので，あとは関数型言語でよく見るリスト処理の関数を使えば良いでしょう．

# [ABC081B - Shift only](https://abs.contest.atcoder.jp/tasks/abc081_b)
```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val as_ = List.tabulate (n, fn _ => valOf (readInt ()))
 
fun ctz acc 0 = acc
  | ctz acc n =
      case n mod 2 of
           0 => ctz (1 + acc) (n div 2)
         | 1 => acc
val ctz = ctz 0
 
val n =
  foldl Int.min (valOf Int.maxInt) (map ctz as_)
 
val () = print (Int.toString n ^ "\n")
```
それぞれの数について何回2で割れるかを求め，畳み込みで最小値を取ります．関数型言語ではお決まりの高階関数を使うやつですね．

与えられた数だけ整数を読み取りたい場合，`List.tabulate`を用いると良いでしょう．`List.tabulate (n, f)`は`[f 0, f 1 ... , f (n - 1)]`を返す関数で，評価は左から右へ行われることが保証されています．なので`f`に整数を読み取る関数を入れておけば，入力順に並んだ`n`個の整数が手に入るわけです．

# [ABC087B - Coins](https://abs.contest.atcoder.jp/tasks/abc087_b)
```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME a = readInt ()
val SOME b = readInt ()
val SOME c = readInt ()
val SOME x = readInt ()
 
val n =
  length (List.concat (List.map (fn i =>
    if x < 500 * i then []
    else List.concat (List.map (fn j =>
      if x < 500 * i + 100 * j then []
      else List.concat (List.map (fn k =>
        if x = 500 * i + 100 * j + 50 * k then [(i, j, k)] else [])
        (List.tabulate (c + 1, fn k => k))))
      (List.tabulate (b + 1, fn j => j))))
    (List.tabulate (a + 1, fn i => i))))
 
val () = print (Int.toString n ^ "\n")
```
リストモナドをベタ書きしてます．Haskellで言う所の

```Haskell
do
  i <- [0 .. a]
  guard (500 * i <= x)
  j <- [0 .. b]
  guard (500 * i + 100 * j <= x)
  k <- [0 .. c]
  guard (500 * i + 100 * j + 50 * k = x)
  return (i, j, k)
```

みたいなのがやりたかった．

# [ABC083B - Some Sums](https://abs.contest.atcoder.jp/tasks/abc083_b)

```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val SOME a = readInt ()
val SOME b = readInt ()
 
val ans =
  foldl op+ 0 (List.filter (fn i =>
    let val n =
      foldl op+ 0
        (map (fn c => ord c - ord #"0")
          (String.explode (Int.toString i)))
    in a <= n andalso n <= b end) (List.tabulate (n, fn i => i + 1)))
 
val () =
  print (Int.toString ans ^ "\n")
```

問題文の指示通りに，1以上N以下の整数のリストを`List.tabulate`で作って，各桁の和がA以上B以下であるものを`List.filter`で選別して，総和を`foldl`で求めています．`ord`は文字コードを求める関数ですね．

# [ABC088B - Card Game for Two](https://abs.contest.atcoder.jp/tasks/abc088_b)
```sml
(* sorting *)
local
  fun revMerge' op<= [] ys acc = List.revAppend (ys, acc)
    | revMerge' op<= xs [] acc = List.revAppend (xs, acc)
    | revMerge' op<= (x :: xs) (y :: ys) acc =
        if x <= y then revMerge' op<= xs (y :: ys) (x :: acc)
        else revMerge' op<= (x :: xs) ys (y :: acc)
 
  fun sort' op<= op> 2 (x :: y :: _) =
        if x <= y then [x, y] else [y, x]
    | sort' op<= op> 3 (x :: y :: z :: _) =
        if x <= y then
          if y <= z then [x, y, z]
          else if x <= z then [x, z, y]
          else [z, x, y]
        else 
          if x <= z then [y, x, z]
          else if y <= z then [y, z, x]
          else [z, y, x]
    | sort' op<= op> n xs =
        revMerge' op>
          (sort' op> op<= (n div 2) xs)
          (sort' op> op<= ((n + 1) div 2) (List.drop (xs, n div 2))) []
in
  fun sort cmp [] = []
    | sort cmp [x] = [x]
    | sort cmp (xs as _ :: _ :: _) =
        sort'
          (fn (x, y) => cmp (x, y) <> GREATER)
          (fn (x, y) => cmp (x, y) = GREATER) (length xs) xs
end
 
 
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val as_ = List.tabulate (n, fn _ => valOf (readInt ()))
 
val (x, y) =
  foldl (fn (a, (x, y)) => (y, x + a)) (0, 0)
    (sort (fn (x, y) => Int.compare (y, x)) as_)
 
val () =
  if n mod 2 = 0 then print (Int.toString (x - y) ^ "\n")
  else print (Int.toString (y - x) ^ "\n")
```
ソートしてから`foldl`で交互に足していくだけなんですが，SMLの標準ライブラリにはリストをソートするための関数がない（は？）ため，OCamlの`List.sort`を移植しています．
一応[SML/NJの拡張ライブラリ](https://www.smlnj.org/doc/smlnj-lib/index.html)には用意されているんですが，要望を出す際にMLtonでそれを使うための設定を忘れていたので，AtCoderの環境では使えません．

# [ABC085B - Kagami Mochi](https://abs.contest.atcoder.jp/tasks/abc085_b)
```sml
(* sorting *)
local
  fun revMerge' op<= [] ys acc = List.revAppend (ys, acc)
    | revMerge' op<= xs [] acc = List.revAppend (xs, acc)
    | revMerge' op<= (x :: xs) (y :: ys) acc =
        if x <= y then revMerge' op<= xs (y :: ys) (x :: acc)
        else revMerge' op<= (x :: xs) ys (y :: acc)
 
  fun sort' op<= op> 2 (x :: y :: _) =
        if x <= y then [x, y] else [y, x]
    | sort' op<= op> 3 (x :: y :: z :: _) =
        if x <= y then
          if y <= z then [x, y, z]
          else if x <= z then [x, z, y]
          else [z, x, y]
        else 
          if x <= z then [y, x, z]
          else if y <= z then [y, z, x]
          else [z, y, x]
    | sort' op<= op> n xs =
        revMerge' op>
          (sort' op> op<= (n div 2) xs)
          (sort' op> op<= ((n + 1) div 2) (List.drop (xs, n div 2))) []
in
  fun sort cmp [] = []
    | sort cmp [x] = [x]
    | sort cmp (xs as _ :: _ :: _) =
        sort'
          (fn (x, y) => cmp (x, y) <> GREATER)
          (fn (x, y) => cmp (x, y) = GREATER) (length xs) xs
end
 
 
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val (d :: ds) = sort Int.compare (List.tabulate (n, fn _ => valOf (readInt ())))
 
val (ans, _) =
  foldl (fn (d, (ans, d')) => (if d = d' then ans else ans + 1, d)) (1, d) ds
 
val () =
  print (Int.toString ans ^ "\n")
```
集合に突っ込んで要素数を数えるだけの問題なんですが，やっぱり[SML/NJの拡張ライブラリ](https://www.smlnj.org/doc/smlnj-lib/index.html)にしかないです．
なのでソートしてから隣同士の要素をみて，重複を無視する感じで解いています．前の要素を引回す感じで畳み込んでやると良いですね．

# [ABC085C - Otoshidama](https://abs.contest.atcoder.jp/tasks/abc085_c)
```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val SOME y = readInt ()
 
val ans =
  List.concat (map (fn i =>
    List.concat (map (fn j =>
      if 9 * i + 4 * j = y div 1000 - n then [(i, j, n - i - j)]
      else [])
      (List.tabulate (1 + Int.min (n - i, (y div 1000 - n - 9 * i) div 4), fn j => j))))
    (List.tabulate (1 + Int.min (n, (y div 1000 - n) div 9), fn i => i)))
 
val () =
  case ans of
       [] => print "-1 -1 -1\n"
     | (i, j, k) :: _ =>
         print (Int.toString i ^ " " ^ Int.toString j ^ " " ^ Int.toString k ^ "\n")
```
またリストモナドをベタ書きしています．総当たりには便利ですね．

# [ABC049C - 白昼夢 / Daydream](https://abs.contest.atcoder.jp/tasks/arc065_a)
```sml
val SOME s = TextIO.inputLine TextIO.stdIn
 
fun solve (#"m" :: #"a" :: #"e" :: #"r" :: #"d" :: s) = solve s
  | solve (#"r" :: #"e" :: #"m" :: #"a" :: #"e" :: #"r" :: #"d" :: s) = solve s
  | solve (#"e" :: #"s" :: #"a" :: #"r" :: #"e" :: s) = solve s
  | solve (#"r" :: #"e" :: #"s" :: #"a" :: #"r" :: #"e" :: s) = solve s
  | solve [] = true
  | solve _ = false
 
val () =
  if solve (tl (rev (explode s))) then print "YES\n"
  else print "NO\n"
```
~~こころぴょんぴょん~~
正規表現を使うだけのような気もしますが，やっぱり正規表現を扱うための関数は[SML/NJの拡張ライブラリ](https://www.smlnj.org/doc/smlnj-lib/index.html)にしかないので，想定解法の貪欲で解いています．

# [ABC086C - Traveling](https://abs.contest.atcoder.jp/tasks/arc089_a)
```sml
fun readInt () =
  TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn
 
val SOME n = readInt ()
val txys = List.tabulate (n, fn _ =>
  (valOf (readInt ()), valOf (readInt ()), valOf (readInt ())))
 
val (adjs, _) =
  foldl (fn (txy, (acc, txy')) => ((txy', txy) :: acc, txy)) ([], (0, 0, 0)) txys
 
val () =
  if List.all (fn ((t, x, y), (t', x', y')) =>
    let
      val d = abs (x - x') + abs (y - y')
      val dt = t' - t
    in d <= dt andalso (d - dt) mod 2 = 0 end) adjs
  then print "Yes\n"
  else print "No\n"
```
`foldl`で隣接した要素を取り出してやって，`List.all`で全ての行程が成立するか調べています．

# おわりに
いかがでしょうか．これぐらいの問題ならSMLでも結構いけるもんですね．
SMLでAtCoderに参加している人は限りなく無に等しいのが現状なので，これを機に人口が増えると嬉しいです．
~~まぁ，肝心の僕がOCamlで参加している有様なんですが．今回の問題にはDPだとかグラフだとか，配列が欲しくなる所が無かったから良いですが，SMLの配列は[構文が重くて辛い](http://adam.chlipala.net/mlcomp/)んですよね〜~~