F#でAtCoder（入門編）

AtCoderの過去問題の提出をF#でやり始めてから結構経ったので、布教活動でもしようかなあと思い立って書き始めました。

はじめに

まず、別にF#でAtCoderをやったところでレート上がるとかそういうのじゃないです。自分自身、万年緑コーダーなので、あんまり説得力もないというか。
ただF#は関数型言語なので、C++やC#のような命令型（オブジェクト指向）言語とはちょっと違ったアプローチが必要なこともあります。それを通して、もしかしたら新しい学びがあるといいなとか、そう言う感じで臨んで欲しいです。

F#とは

そもそもの話、F#とは何か。
F#はOCamlをベースにマイクロソフトが開発したプログラミング言語です。
先に「関数型」と書きましたが、実際はオブジェクト指向も扱えるマルチパラダイムな言語だったりします。それ故、参照透過性を持たない関数を定義できるため、非純粋な関数型言語となります。
ただ、F#のFはfunctional(関数型)に由来しているようなので、この特性を極力生かしてコードを書いて行くことを目指していこうと思います。

ABSを解いていく

今回は入門編ということで、ABS(AtCoder Beginners Selection)を通してF#でどんなことができるを紹介していきましょう。

PracticeA - Welcome to AtCoder

この問題で求められるのは入力、整数型変換、演算、出力です。
これが出来ないと他の問題も解けませんので、この問題だけは詳細に解説をしていきます。

F#の入力はstdin.ReadLine()で行います。
変数の宣言にはletを使用します。これはJavaScriptと同じですね。
なので入力した値を変数aに入れようとすると次のようになります。

F#

let a = stdin.ReadLine()

ここで宣言した変数aですが、このままではイミュータブル(不変)になります。イミュータブルなのに変数とはいったい……。

さて、ここで得られるのは文字列型(string)です。後の工程で3つの整数の和を取りたいので、整数型(int)に変換する必要があります。
intへの変換には関数intを使用します。関数を呼び出したいときには、関数名の後ろに半角スペース区切りで引数を指定していきます。

F#

// わかりやすくシステムハンガリアンで書いてるだけなんで許して
let str_a = stdin.ReadLine()
let int_a = int a

実際のところ、他の言語なんかでは直接引数にstdin.ReadLine()の戻り値を渡すことも少なくないと思うので、以下のように変数aを宣言してしまいましょう。

F#

let a = int stdin.ReadLine()

これで変数aには入力された値を整数型にした結果が格納されます。これでもいいのですが、折角なのでF#の持つパイプライン演算子|>を活用してみましょう。
パイプライン演算子は、左辺の値や関数の結果を、右辺の関数の引数に渡す演算子です。先ほどの変数aの定義をパイプライン演算子で書き換えてみると次のようになります。

let a = stdin.ReadLine() |> int

パイプライン演算子の利点は可読性にあります。仮に関数Aの戻り値を関数Bに渡し、さらにその戻り値を関数Cに渡したいとき、C#などの言語では次のように記述します。

C#

C(B(A()));

通常、コードを読むときは左から右へ読むかと思います。しかしこの書き方だと、人が関数を呼んだ順序と実際に実行される順序が逆転してしまいます。
そこでパイプライン演算子です。これを使うと次のようになります。

F#

A |> B |> C

これならば、人が読んだ順序と実際の実行順序が一致するのでコードが読みやすくなるのではないでしょうか。

パイプライン演算子を上手く活用すると、問題によってはワンライナーで回答できます。しかし、かえって可読性が悪くなる事もあるのでほどほどに。

さて、次は入力B、Cの受け取りですね。これは空白区切りで入力されますので、stdin.ReadLine()の結果は"B C"のようになります。これを分割するにはどうするか。Split()メソッドですね。

F#

let array_bc = stdin.ReadLine().Split()

パイプライン演算子は？　何で括弧付けるの？　そんな疑問があるかと思います。
よく解ってないので雑に言うと、Split()はstringクラスの持つメソッドなので括弧が必要で、intは関数だから括弧が不要になります。C#と同じ.NETを使ってる部分についてはどうしてもC#の仕様に寄ってしまいますね。

さて、Split()した結果である変数array_bcは文字列の配列です。
欲しいのは２つの整数型なので、配列の要素をint関数で変換したい。ただ、array_bc自体は配列なのでそのままではint関数を通せない。
そこで使うのがArray.map関数です。この関数は配列の要素１つ１つを変換するための関数です。どのように変換するかは引数で指定するのですが、ここに関数を渡すことができます。
先ほどのパイプライン演算子を使って書くと、次のようになります。

F#

let array_bc = stdin.ReadLine().Split() |> Array.map int

Array.map関数は２つの引数を受け取るのですが、パイプライン演算子を使った場合には、２つめの引数に値が渡されます。イメージとしてはArray.map intという１つの関数に対して値を渡しているような感じです。いわゆるカリー化。
あとは変数の宣言の仕方も変えてみましょう。JavaScriptなんかでも配列の要素をバラして変数に入れて宣言できますが、同じようなことがF#でもできます。

F#

let [|b;c|] = stdin.ReadLine().Split() |> Array.map int

ちょっと違うのは配列の書き方でしょうか。他の言語では[b,c]のようになりますが、F#ではこの書き方は「１つのタプルを含むリスト」を意味します。配列を表す場合は[||]で囲い、要素の区切りには;を使いましょう。

これでようやく変数a、b、cが宣言できたので、最後は文字列sを取得しましょう。

F#

let s = stdin.ReadLine()

ここまでできたら、次はA+B+Cの演算です。これは特に難しいこともなく、他の言語と同様に+演算子で計算します。

F#

let ans = a + b + c

ちなみにF#には(+)という関数が存在します。これは与えられた２つの引数の和を求める関数です。これとパイプライン演算子を使えば、次のように演算することもできます。

F#

let ans = a |> (+) b |> (+) c

まあただ、今回の場合に関して言えば、どちらが読みやすいかというと、前者ですよね。

これで答えが求められたので、最後は出力です。
末尾の改行を伴う出力にはprintfn関数を使用します。最初の引数に出力したい文字列を渡すのですが、この文字列にはパラメータを含めることができます。整数を含めたければ%dを、文字列であれば%sを使用します。なので今回の場合は次のように出力をします。

F#

printfn "%d %s" ans s

最終的な提出コードは次のようになります。

ABS_PracticeA.fs

let a = stdin.ReadLine() |> int
let [|b;c|] = stdin.ReadLine().Split() |> Array.map int
let s = stdin.ReadLine()
let ans = a + b + c
printfn "%d %s" ans s

ABC086A - Product

制約上、２つの積を取ってもintの範囲に収まるので、問題通り積を取って2で割り切れるかを判定します。

ABC086A.fs

stdin.ReadLine().Split()
|> Array.map int
|> fun [|a;b|] ->
    // 積が偶数か奇数かを表す文字列をリターン
    if a * b % 2 = 0 then
        "Even"
    else
        "Odd"
|> printfn "%s"

letで変数を宣言しない書き方にしてみました。
funは匿名関数(ラムダ式)の宣言です。ここではaとbの２つの要素を持つ配列を引数に受け取る関数を定義しています。
関数の中ではif文で分岐していて、それぞれのケースの中で"Even"ないし"Odd"と書かれています。F#は、C#等の言語のようなreturn句を持たず、最後に書かれたものが戻り値となります。ここでは"Even"や"Odd"という文字列が最後に書かれているので、これが戻り値になります。
C#ではa * b % 2 == 0 ? "Even" : "Odd"のような三項式が書けますが、これと同じような感じだと思って貰えればいいです。

ちなみにF#のif文は、if a * b % 2 = 0 then "Even" else "Odd"のようにワンライナーで三項式のように書くこともできます。
また厳密に言えばif式であり戻り値を持ちます。"Even"なんかも実はif式の戻り値です。
なので三項式と同様に結果を変数に入れたり、パイプライン演算子で別の関数へ値を渡すことも出来ます。

あともう１点ポイントとして、C#のように{}でブロックを表すのでは無く、Pythonのようにインデントによってブロックを表します。
なので

F#

if a < b then
    b <- b + 1
    a <- a % b

と

F#

if a < b then
    b <- b + 1
a <- a % b

では別の結果になるので注意してください。

ABC081A - Placing Marbles

この問題の解き方はいろいろあるのかなと思いますが、今回は文字列として１文字ずつ見ていき、1がいくつあるかを数える方法を採用してみます。

ABC081A.fs

stdin.ReadLine()
|> Seq.filter ((=) '1') // 文字'1'に絞り込む
|> Seq.length // 要素数を数える
|> printfn "%d"

Seqにはシーケンスを操作するための関数が定義されています。シーケンスは.NETで言うところのIEnumerable相当で、配列、リスト、文字列のいずれもシーケンスをとして扱えます（ただし戻り値はシーケンスになるので注意。LINQと同じですね）。

ここではSeq.filter関数を使ってシーケンスの要素を選別して、残った要素数(Seq.length)を出力しています。

ABC081B - Shift only

数列Aの各要素について、値が0になるか最下位ビットが1になるまで何回右シフトできるかを求め、その最小値を答えとして出力します。

ABC081B.fs

/// 右シフト可能な回数を求める関数
let countShift v =
    /// 右シフトを繰り返すループ用再帰関数
    let rec loop v acc =
        match v with
        | 0 -> acc
        | x when x &&& 1 = 1 -> acc
        | x -> loop (x >>> 1) (acc + 1)
    loop v 0

let n = stdin.ReadLine() |> int
stdin.ReadLine().Split()
|> Array.map (int >> countShift) // int関数とcountShift関数の合成関数で要素を変換
|> Array.min // 最小の要素を求める
|> printfn "%d"

まずは与えられた数vを何回右シフトできるかを求める関数countShiftを定義します。関数の定義も変数と同じくletを使います。変数との違いはスペース区切りで引数を定義していく点です。

では引数無しの関数はどうやって定義するのか。
参照透過性を持っていれば引数無しの関数は常に同じ値を返しますから、それはもう変数に結果を入れておけばいいですよね？
見方を変えれば、letで宣言しているのは変数ではなくて引数無しの関数ということにはなりますが、関数の中身は宣言時に一度しか実行されないので注意。

次に配列の各要素をArray.mapによって変換していきます。ここで変換に用いる関数として(int >> countShift)を渡しています。
この>>は関数の合成演算子で、関数を合成して一つの関数にします。合成と言ってもピンとこないかもしれませんが、単純に左辺の戻り値を右辺の引数へ渡しているだけで、考え方はパイプライン演算子とほぼ同じです。例えば1 |> A |> Bと1 |> (A >> B)は同じ結果となります。

あとは配列中の最小値をArray.minによって求めればそれが答えです。

ABC087B - Coins

この問題の制約であれば三重ループでも十分時間内に処理が終わります。

ABC087B.fs

// 入力
let a = stdin.ReadLine() |> int
let b = stdin.ReadLine() |> int
let c = stdin.ReadLine() |> int
let x = stdin.ReadLine() |> int

[0..a] // 500円の枚数0枚～a枚のパターンを表すリスト
|> List.map (fun i ->
    [0..b] // 100円の枚数0枚～b枚のパターンを表すリスト
    |> List.map (fun j ->
        [0..c] // 50円の枚数0枚～c枚のパターンを表すリスト
        |> List.map (fun k -> 500 * i + 100 * j + 50 * k) // 合計金額を求め
        |> List.filter ((=) x) // xと等しい要素のみ残す
        |> List.length // 要素数を取得
    )
    |> List.sum // 100円の枚数各パターンの総和を求める
)
|> List.sum // 500円の枚数各パターンの総和を求める
|> printfn "%d"

なんか違和感のあるコードですね。
[0..a]は「0から1ずつ増やしてaまでの数列となるリスト」の宣言です。これに対してList.map関数を使って要素を変換しています。

おそらく違和感はfor文がないことでしょう。
もちろんF#にもfor..in式があります。ありますけど、この手の「ループして数える」処理って

C#

var cnt = 0;
for (var i = 0; i <= n; i++)
{
    if (なんか条件) cnt = cnt + 1;
}

このように、ループの外側で宣言した変数をどんどん更新していくことが多いかと思います。
しかし先に紹介したように、F#のletで宣言した変数は不変です。一応、言語仕様としては可変にもできるので、次のように処理できます。

F#

let mutable cnt = 0
for i in 0 .. n do
    if なんか条件 then
        cnt <- cnt + 1

まあただ、やはりfor式の外側にある変数で状態を持つのはあまり嬉しくありません。
そこでリストを使った処理です。
イメージとしては下図のように、考えられる500円玉の枚数のパターンでリストを定義し、List.Mapによって「i枚のときに考えられるパターン数」のリストを生成します。最終的にこのリストの要素の総和を取ればそれが答えです。

List.Mapの中では100円玉に対しても同様に処理しています。更にその中では50円玉に対し、条件を満たすパターンをList.fliterによって求め、List.lengthをつかって数えています。

ABC083B - Some Sums

これも素直に全探索ですね。
数字和を再帰処理で求めるのはABC081Bと同じで、リストを作って処理するのはABC087Bと同じです。

ABC083B.fs

/// 数字和を求める関数
let sumDigit v = 
    /// 1桁ごとループする再帰関数
    let rec loop acc v =
        match v with
        | 0 -> acc
        | _ -> loop (acc + v % 10) (v / 10)
    loop 0 v

stdin.ReadLine().Split()
|> Array.map int
|> fun [| n; a; b |] ->
    [1..n]
    |> List.filter (fun v -> v |> sumDigit |> fun x -> x >= a && x <= b) 
    |> List.sum
    |> printf "%d"

ABC088B - Card Game for Two

数列Aを降順ソートして、奇数番目をAlice、偶数番目をBobの得点にして、その差を求めればOKですね。

ABC088B.fs

let n = stdin.ReadLine() |> int

stdin.ReadLine().Split()
|> Array.map int
|> Array.sortDescending // 降順ソート
|> Array.indexed // 要素にインデックス番号を付与
|> Array.partition (fun (i, v) -> i % 2 = 0) // インデックス番号の偶奇で分別
|> fun (a, b) ->
    let alice = a |> Array.sumBy snd // 偶数番号について総和を求める。sndはタプルの2要素目を取得する関数
    let bob = b |> Array.sumBy snd // 奇数番号について総和を求める
    alice - bob
|> printfn "%d"

まず、Array.sortDescendingを使って降順ソートした配列に対し、Array.indexedでインデックス位置を付与しています。これは配列のi番目の要素がxならば(i, x)というタプルを要素に持つ配列へ作り替えています。
次にArray.partitonです。この関数では、配列の各要素に対して引数で与えられた関数を適用し、その結果がtrueかfalseかによって2つの配列に分割します。
後はそれぞれの配列の要素の和を求め、その差を取ればOK。

ABC085B - Kagami Mochi

同じ数を使わずに降順で詰んでいけば良いので、与えられた数の種類を求めればいいわけですね。

ABC085B.fs

let n = stdin.ReadLine() |> int

Array.init n (fun i -> stdin.ReadLine())
|> Array.distinct
|> Array.length
|> printfn "%d"

この問題のようにN回入力を受け付けたい場合はAray.init関数を使うと便利です。こうすることでN回の入力結果を配列として取得できます。
あとは配列をArray.distinctでユニークにして、その要素数を数えれば終わりですね。

ABC085C - Otoshidama

https://atcoder.jp/contests/abs/tasks/abc085_c
三重ループするとTLEしてしまうのですが、10000円札と5000円札の枚数が定まれば1000円札の枚数も決まるので二重ループで探索していきます。

ABC085C.fs

stdin.ReadLine().Split()
|> Array.map int
|> fun [|n;y|] ->
    [0..n] // 10000円の枚数0枚からn枚の各パターンをリストで宣言
    |> List.map (fun i ->
        [0..(n - i)] // 5000円の枚数0枚からn-i枚の各パターンをリストで宣言
        |> List.choose (fun j -> // 要素を変換しつつ選別
            let x = y - (10000 * i + 5000 * j)
            let k = x / 1000
            if x >= 0 && x % 1000 = 0 && i + j + k = n then
                // 条件を満たせば出力用の文字列に変換しSomeにする
                (sprintf "%d %d %d" i j k) |> Some
            else
                // 満たさない場合はNone
                None
        )
    )
    |> List.concat // 結果配列を連結
    |> List.tryHead // 先頭要素の取得
    |> function
        | Some v -> v
        | None -> "-1 -1 -1" // 取得できなかった（＝条件を満たした要素がない）場合は"-1 -1 -1"
    |> printfn "%s"

思ったより長くなりましたね。
forループなら早期リターンですっきりするのですが、リストとして処理しているのでそれができず、「存在しない場合」の考慮もあるので余計に長くなってしまいました。

まずList.chooseです。これは「List.mapのように要素を変換しながら、List.filterのように条件を満たすものだけを残す」ような関数です。
残すか残さないかはSomeかNoneで決まります。これはちょっと違うかもですがC#で言うところのNull許容型のようなものです。None(≒null)の要素は結果から除外されます。
得られる結果は配列の配列です。そこでList.concatを使って1つの配列になるよう結合します。
最後に要素を1個取り出せばいいのですが、一切条件を満たすケースが存在しない場合、先頭要素のアクセスに失敗します。
そこでArray.tryHeadを使うことで、見つかればSome、そうでなければNoneとして値を取得できます。この結果がSomeなら持っている値を、Noneなら"-1 -1 -1"を出力します。

ABC049C - 白昼夢

少しズルいですが、正規表現を使用しましょう。F#も.NETの機能が使えるのでC#と同じ事ができるよという説明のためです。

ABC049C.fs

// 名前空間の利用宣言
open System.Text.RegularExpressions

// 正規表現の定義
let regex = new Regex("^((dream(er)?)|(erase(r)?))+$")

stdin.ReadLine()
|> regex.IsMatch // 判定
|> function // 判定結果で出力する文字を選択
    | true -> "YES"
    | _ -> "NO"
|> printfn "%s"

.NETのメソッドを呼ぶときは括弧が必要だと先に述べましたが訂正しましょう。引数が1つしかないのならば、このようにパイプライン演算子を使って引数を渡すこともできます。
呼び出しているのはregex.IsMatchです。

あと、.NETのクラスを使う場合は、そのクラスの名前空間をopenで指定する必要があります。C#で言うところのusingですね。

ABC086C - Traveling

前の状態から現在の状態に遷移出来るかを判定します。
移動距離 > 経過時間であれば遷移出来ないですし、移動距離 < 経過時間の場合もその差が偶数でないと遷移出来ません（超過分を行って戻ってするので）。

ABC086C.fs

let n = stdin.ReadLine() |> int
Array.init n (fun i -> stdin.ReadLine().Split() |> Array.map int)
|> Array.fold (fun (pt,px,py) [|t;x;y|] -> // 前回の結果を受け取って演算する
    if pt < 0 then
        // 時間が負数の場合途中で到達できなかったので何もせず同じ結果を返す
        pt,px, py
    else
        let dist = ((x - px) |> abs) + ((y - py) |> abs) // 次の目的地までの距離
        let time = t - pt // 経過時間
        if dist > time || (time - dist) % 2 > 0 then
            // 到達する条件を満たさなかった場合、時間を-1にして失敗を表す
            -1, x, y
        else
            t, x, y
) (0, 0, 0) // 第2引数では初期値としてt=0,x=0,y=0を渡す
|> fun (t, x, y) ->
    match t with // 最後まで時刻が負数にならず処理できたかで判定する
    | -1 -> "No"
    | _ -> "Yes"
|> printfn "%s"

Map.foldを使って処理していきます。これは前の要素での戻り値（1要素目の時は別に引数で与えた初期値）を引数で受けながら処理していける関数です。

移動距離を求める際には絶対値の計算が必要ですが、それはabs関数を使います。

おわりに

思ったより問題数が多かったですね。長くなってしまいましたが、こんな感じで大体A~C問題くらいは解けるんじゃないでしょうか。グリッドの処理はちょっと苦手ですけど。

この先、D問題を解こうと思ったら動的計画法を使う機会が増えてくるんですけれど、そこでも一工夫必要になってくるのでまたの機会にやれたらと思います。