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

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

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

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

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

```

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

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

```

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

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

```

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

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

```

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

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

```fsharp
// 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
https://beta.atcoder.jp/contests/abc086/tasks/abc086_a

```fsharp
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
https://beta.atcoder.jp/contests/abc081/tasks/abc081_a

```fsharp
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
https://beta.atcoder.jp/contests/abc081/tasks/abc081_b

```fsharp
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
https://beta.atcoder.jp/contests/abc087/tasks/abc087_b

```fsharp
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#のリストはいわゆる線型リストで実装されているようで，実際に領域を確保して生成されます．

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

```fsharp
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
https://beta.atcoder.jp/contests/abc083/tasks/abc083_b

```fsharp
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
https://beta.atcoder.jp/contests/abc088/tasks/abc088_b

```fsharp
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
https://beta.atcoder.jp/contests/abc085/tasks/abc085_b

```fsharp
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
https://beta.atcoder.jp/contests/abc085/tasks/abc085_c

```fsharp
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
https://beta.atcoder.jp/contests/abc049/tasks/arc065_a

```fsharp
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
https://beta.atcoder.jp/contests/abc086/tasks/arc089_a

```fsharp
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`という関数があって，これは配列内の隣接要素をタプルにした配列を作るという関数です．つまり

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

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

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

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