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

はじめに

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を様々な言語で解くのが流行っているようなので，便乗して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を入れておけば十分でしょう．そこそこ速いし，対話環境もあって便利です．AtCoderに入っているのはMLtonですが，対話環境が付いていない上にコンパイルが壊滅的に重いので，手元でテストするのにはお勧めしません．
これだけ聞くとMLtonが駄目な処理系に思えますが，こちらには非常に速いコードを生成してくれる長所があります．トレードオフですね．OCamlが速いのは有名ですが，下手をすればMLtonの方が速いんじゃないでしょうか．定数倍に泣かされなくなる点では競プロに向いた処理系と言えるでしょう．

あまりSMLについて詳しく解説してもSMLの入門記事になってしまいますから，この辺で止めておきましょう．詳しい説明が読みたくなったらプログラミング言語Standard ML入門
なんかが良いと思います．

PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

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

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

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

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

TextIO.scanStream Real.scan TextIO.stdIn

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

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

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

標準ライブラリには無いですがprintfとかscanfみたいなのも一応，書こうと思えば書けます．

ABC086A - Product

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

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

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

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で言う所の

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

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

(* 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の拡張ライブラリには用意されているんですが，要望を出す際にMLtonでそれを使うための設定を忘れていたので，AtCoderの環境では使えません．

ABC085B - Kagami Mochi

(* 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の拡張ライブラリにしかないです．
なのでソートしてから隣同士の要素をみて，重複を無視する感じで解いています．前の要素を引回す感じで畳み込んでやると良いですね．

ABC085C - Otoshidama

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

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の拡張ライブラリにしかないので，想定解法の貪欲で解いています．

ABC086C - Traveling

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の配列は構文が重くて辛いんですよね〜