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

初めに

drken さんの記事の10問をF#で解いてみました．
元記事はこちらです． https://qiita.com/drken/items/fd4e5e3630d0f5859067

目的

　F#はいわゆる関数型言語ですが，mutable変数や.Netの恩恵が受けられるという事があって個人的に面白くかけるなぁという印象のある言語です．イチ押しはパイプライン演算子というやつで，この記事では主にその魅力をアピールしたいと思います．
（堪能というわけではないのと，僕自身は普段の競技プログラミングにはC#で参加しているので，多少の訛りや不格好な点は大目に見ていただければ．．）

パイプライン演算子

　F#におけるパイプライン演算子|>は，いわゆるUNIX/LINUX系のシェルでサポートされているパイプ|のような動作をする演算子です．
　ある型aの値 x を受け取って違う型bの値を返す関数をfとするとき，F#の記法では

// f : x :a -> b   a型の値xを受け取ってb型の値を返す関数
let y = f x

と書くことでx に f を作用させた値を yで受け取る（束縛）事が出来ます．数学で出てきたようなy = f(x)という書き方に似ています．パイプライン演算子はこれを単純に書き順をひっくり返すものになります．

// f : x :a -> b   a型の値xを受け取ってb型の値を返す関数
let y = x |> f

　これで何が嬉しいかというと，fを作用させた結果にさらにgを作用させた結果を得たいような局面で，次のように

// f : x :a -> b   a型の値xを受け取ってb型の値を返す関数
// g : y :b -> c   b型の値yを受け取ってc型の値を返す関数
let z = g (f x)

と書かないといけないところが，パイプライン演算子を使うことで

// f : x :a -> b   a型の値xを受け取ってb型の値を返す関数
// g : y :b -> c   b型の値yを受け取ってc型の値を返す関数
let z = x |> f |> g

という風にどんどん右側につないでいくことでができるようになります．C#のLINQやjQueryのメソッドチェーンと同じような印象ですが，つなぎ目で型がつながっていればどんどんつないでいける点で，こちらの方がかなり自由度が高い記述が可能です．
（例えばLINQだとIEnumerableが途切れてしまうようなメソッド（例えば.Sum()）の後につなげられるメソッドはないですが，パイプライン演算子ならその結果にさらにほかの関数を作用させたりできます）

　さらに頼もしいのが，F#は関数の部分適用をサポートしているので，1つの引数に作用させて違う結果を得るような関数を手軽に作ることができるという点です．
　月並みな例だと，例えば次の足し算addは引数を2つとる関数ですが，「1つだけ与えておいてスタンバっている関数」を作ることができれば，（少し語弊はありますが）それは1つの引数を受け取って値を返す関数とみなすことができます．これを部分適用と呼んでいます．

// add0 : (x，y) : (int * int) -> int
// int型の値の組(x, y)を受け取ってint型の値 (x + y)を返す関数 (x と yの両方がそろわないと動かない）
let add0 (x, y) = x + y

// add : x: int -> y:int -> int
// int型のxを受け取って，（int型のyを受け取って intの値 x + y を返す関数）を返す関数
let add x y = x + y

// add には x を適用させただけの状態で意味がある（部分適用）
let f = add x    // こう書くことで f : int -> int が得られる

// fに束縛しなくてもそのまま使うこともできる
let z = 12 |> (add 9)    // z = 21

// 演算子の優先順位と型推論により括弧も省略できる
let w = 32 |> add 16     // w = 48  

　前置きが長くなりましたが，実例を見ていきましょう．

回答

第１問: ABC086 A - Product

open System

let inputArray = stdin.ReadLine().Split(' ') |> Array.map int
let a = inputArray.[0]
let b = inputArray.[1]

let f x y = if (x % 2) = 0 || (y % 2) = 0 then "Even" else "Odd"

f a b |> printfn "%s"

　標準入力をうけとっているのはstdin.ReadLine().Split(' ')で，これはいかにもC#っぽい書き方ですが，これは1行読んだ文字列を' '区切りにしてstringの配列（Array）に変換したものを返します．
　その後ろにパイプライン演算子|>が早速登場しています．
　Array.map f ar は後ろに2つ引数をとります．1つ目の引数fがmapの内容，2つ目の引数arが作用させるArrayになり，arの各要素にfを作用させた結果を要素に持つArrayを返します．ここではfにあたるint はint型へのparseであり，arにあたる部分にstdin.ReadLine().Split(' ')がパイプライン演算子で持ってこられているという感じです．
　最終行も同様で，f a bの結果にprintfn "%s"を作用させていて，意味としてはprintfn "%s" (f a b)と同じになるわけです．（printfnはprintfプラス改行(n)らしいです）

第 2 問: ABC 081 A - Placing Marbles

open System

stdin.ReadLine()
|> Seq.sumBy (fun c -> if c = '1' then 1 else 0)
|> printfn "%d"

　文字列中にある'1'の数を数える問題です．
　funはいわゆるラムダ式をつくる構文で，(fun c -> if c = '1' then 1 else 0)はc:char型が'1'なら1,それ以外は0を返す関数を作っています．Seq.sumByは第1引数の関数を用いて各要素を計算した値を合計する関数です．文字列はF#ではchar型のシーケンス（Sequence)として扱うことが可能です．

第 3 問: ABC 081 B - Shift Only

open System

let N = stdin.ReadLine() |> int
let A = stdin.ReadLine().Split(' ') |> Array.map int
// 180504 加筆：canDiv2は 0入力で無限ループするので注意
//（今回は問題の制約で0が入力されない事が保証されている）
let rec canDiv2 = fun v -> if v % 2 = 1 then 0 else (1 + canDiv2(v / 2))

A
|> Array.map canDiv2
|> Array.min
|> printfn "%d"

　与えられた配列Aの各要素に対して，2で何回割ることができるかを計算して，その最小値を求める問題です．
　ここではcanDiv2という関数を定義していますが，キーワードrecを付けることで再帰定義が可能になります．また，F#のifは文ではなく式であるため，必ず値を持ちます．canDiv2では奇数なら1，偶数なら2で割った結果をcanDiv2で計算した結果に1を足す，という再帰で関数の値が決まっています．
　パイプライン演算子は改行でどんどんつないでいくのが，F#の慣例的なコーディングスタイルのようです．

第 4 問: ABC 087 B - Coins

open System
let readInt () = stdin.ReadLine() |> int

let A = readInt ();
let B = readInt ();
let C = readInt ();
let X = readInt ();

[ for i in [0..A] do
    for j in [0..B] do
        for k in [0..C] do
           yield i * 500 + j * 100 + k * 50]
|> List.sumBy (fun v -> if v = X then 1 else 0)
|> printfn "%d"

　A枚以下の500円とB枚以下の100円とC枚以下の50円でX円を作る方法がいくつあるかという問題です．
　ここではリストの内包表記というものを使って（コード中の[]で囲まれた部分），実際にi * 500 + j * 100 + k * 50の取りうる値が全て入ったリストを作成しています．F#のリストはいわゆる線型リストで実装されているようで，実際に領域を確保して生成されます．

　リストを遅延評価で生成する方法もあります．シーケンスというものを使います．

open System
let readInt () = stdin.ReadLine() |> int

let A = readInt ();
let B = readInt ();
let C = readInt ();
let X = readInt ();

seq {for i in 0..A do
         for j in 0..B do
              for k in 0..C do
                  yield i * 500 + j * 100 + 50 * k}
|> Seq.sumBy (fun v -> if v = X then 1 else 0)
|> printfn "%d"

第 5 問: ABC 083 B - Some Sums

open System
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int

let [| N; A; B |] = readIntArray ()

let digSum n =
    n
    |> string
    |> Seq.sumBy (fun c -> int c - int '0')

[1..N]
|> Seq.sumBy (fun v -> if (digSum v >= A) && (digSum v <= B) then v else 0)
|> printfn "%d"

　1からNまでの間に桁和がA以上B以下になるものがいくつあるかという問題です．
　コード中のlet [| N; A; B |] = readIntArray ()の部分は，F#の型推論・パターンマッチの出番ですが，3要素の配列の0番目1番目2番目の要素をそれぞれN A B に束縛するという指定で書くことができます．N A Bの方はreadIntArrayから推論されます．
（一般にはreadIntArrayが3要素とは限らないのでコンパイル時にはその意のwarningがでます）

第 6 問: ABC 088 B - Card Game for Two

open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int

let N = readInt ()
let A = readIntArray () |> Array.sortWith (fun a b -> a.CompareTo b |> (*) -1);

let rec takeFirst xs =
    match xs with
        | []   -> 0
        | x :: [] -> x
        | _    -> xs.[0] + takeFirst (List.skip 2 xs)


let total = A |> Array.sum
let alice = Array.toList A |> takeFirst
let bob = total - alice
printfn "%d" (alice - bob)

　N枚のカードの山から互いにカードを取っていくというのを，それぞれが最大化した際に合計にどれだけの差が最終的につくかという問題です．降順にソートして交互に取っていくイメージです．
　パターンマッチということで，takeFirstという関数を考えて，Aliceの手番に取るスコアの計算しています．
　降順にソートされたAに対して
　・要素数0なら何も取れない（= 0)
　・要素数1ならそれをとる （= x，リストが[x]という形)
　・それ以外なら，1つ目をとって（2つ目はBobがとるので）スキップ
という風にして，0,2,4,..番目の値を足し合わせた値を返す関数がtakeFirstです．

第 7 問: ABC 085 B - Kagami Mochi

open System
let readInt () = stdin.ReadLine() |> int

let N = readInt ()
let A : int [] = Array.zeroCreate N
for i in [0..N-1] do A.[i] <- readInt ()

A
|> Array.distinct
|> Array.length
|> printfn "%d"

　真に昇順となる列の最長の長さを求める問題です．異なる数字がいくつあるかをかぞえるので，それ自体はArray.distinctという関数があります．
　ここで初めてでてきたのは，Array.zeroCreateという関数で，これは第一引数の数だけのデフォルト要素をもつ配列を生成します．Array.zeroCreateはジェネリックな関数であるため，返り値を受ける変数に型情報を与えてやることで，所望の型の配列を作ります（let A : int []の部分で int []だと教えている）
　もう一つ配列の重要な特徴に，各要素がmutable（可変）であるということがあります．この例ではAのi番目の要素A.[i]にreadInt ()の値を代入しています．代入は<-を使います．

第 8 問: ABC 085 C - Otoshidama

open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int

let [| N; Y |] = readIntArray ()

let showResult (a, b, c) = printfn "%d %d %d" a b c

seq { for i in [0..N] do
          for j in [0..(N - i)] do
              yield (i , j, N - i - j)}
|> Seq.tryFind (fun (a, b, c) -> a * 10000 + b * 5000 + c * 1000 = Y)
|> (fun opt -> if Option.isSome opt then Option.get opt else (-1, -1, -1))
|> showResult 

　合計N枚の10000円札，5000円札，1000円札でY円が作れるか，作れるなら一つ作り方を答えろという問題です．
　10000円札の枚数と5000円札の枚数から1000円札の枚数が決まるという事から，10000円札の枚数と5000円札の枚数を総当たりして探すという解法です．ここでも作りえる組み合わせのシーケンスを作って，そこから探す（tryFind）という方針をとります．
　tryFindはOption型という値を返します．これはNone(失敗）であるか，Some(成功)であって値があるという成功失敗に関する戻り値を付随させるような型です．成功したなら値をもってきているのでその値を採用し，なければ(-1, -1, -1)にするという感じですね．

第 9 問: ABC 049 C - Daydream

open System

let S = stdin.ReadLine()
let N = S.Length
let dp : bool [] = Array.zeroCreate (N + 1)

let candi = [ "dream"; "dreamer"; "erase"; "eraser" ]

dp.[0] <- true
for i in [0..N-1] do
    if dp.[i] then
       candi |> List.iter (fun str -> if (i + str.Length <= N && S.Substring(i, str.Length) = str ) then (dp.[i + str. Length] <- true))

if dp.[N] then "YES" else "NO"
|> printfn "%s"

　"dream", "dreamer", "erase", "eraser" の4つをうまく結合させて文字列Sを作ることができるかという問題です．この問題は300点にしては難しいと思ったら，後ろから見れば一意にとって行けるという性質があったようですが，思いつかずにdpをしてしまいました．
　配列はmutableという性質があるので，時には思い切って書けるというのも，ゆるふわでいいものだと思います．

第 10 問: ABC 086 C - Traveling

open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int

let N = readInt ()
let TXY : (int * int * int) [] = Array.zeroCreate (N + 1)
TXY.[0] <- (0, 0, 0)
for i in [1..N] do
    let [| x; y; z |] = readIntArray ()
    TXY.[i] <- (x , y , z)

let check (((t0, x0, y0) , (t1, x1, y1)) : (int * int * int) * (int * int * int)) =
    ((x0 + y0) % 2 = t0 % 2) && ((x1 + y1) % 2 = t1 % 2) && (Math.Abs(x0 - x1) + Math.Abs(y0 - y1) <= t1 - t0)

TXY
|> Array.pairwise
|> Array.map check
|> Array.reduce (&&)
|> (fun b -> if b then "Yes" else "No")
|> printfn "%s"

　時刻と座標が時系列に沿って与えられるので，その通りに移動できるかという問題です．
　問題の本質は，時刻の偶奇とX + Yの偶奇が一致しているかということとマンハッタン距離が時間以下に収まるかということで判定できるという部分で，ここはコーディングよりも考察ウェイトが大きいです．
　このコードでは checkという関数でそれをチェックしています．型推論の手掛かりがないため，引数に型注釈（:で型を明示できる)をつけています．型推論できない記述があるときはコンパイルが通りません．
　ちょっと物珍しい関数としては，Array.pairwiseという関数があって，これは配列内の隣接要素をタプルにした配列を作るという関数です．つまり

[| 1; 4; 6; 8; 9 |] |> Array.pairwise 

は

[| (1, 4) ; (4, 6); (6, 8); (8, 9) |]

になります．上の回答コードでは (T, X, Y)のタプルの配列を作って，今と1手先とのペアの配列を作って，それぞれチェックするという感じになっています．Array.reduceは全要素を第1引数の関数で演算してつないだ結果を返す関数です．

おわりに

　パイプライン演算子の魅力がどれくらい伝わったかは疑問があるような記事になってしまったかもですが，Haskellに挫折した人でも.Netに抵抗がなければゆるふわ関数型への導入としてF#は楽しいと思うので，興味がわいた方はぜひやってみてください．
　F#が使える競技プログラミングサイトは意外と少ないので，atcoderで使えるというのは練習にいいですね．yukicoderでも使えます．
　いつかC#にパイプラインと部分適用が導入される日を夢見てます．