はむ吉（のんびり）の練習ノート

プログラミングとことばに関する話題を中心に，思いついたこと，試してみたこと，学んだことを，覚え書きを兼ねてまとめます．その際に役立った，技術書，参考書，辞書，機器などの紹介も行います．

AtCoder に登録したら解くべき精選過去問 10 問 (AtCoder Beginners Selection) を F# で解く：別解

競技プログラミング プログラミング AtCoder F#

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita （drken さん）で紹介されている 10 問を，二番煎じではありますが F# で解きました．Pythonista 兼駆け出し Haskeller の視点から，言語機能やライブラリの紹介に重きをおいて，他言語との比較もはさみつつ，簡単な解説を添えてコード例を示します．

はじめに

先日，drken さんは AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita と題して，代表的プログラミングコンテストサイトの一つである AtCoder に登録したばかりである競技プログラミング入門者の方々を主な対象とした記事を書かれました．この記事においては，過去の AtCoder Beginner Contest (ABC) を中心とする，入門者向けの問題 10 問（および Practice）が精選され，その解法および C++ *1 によるコード例について詳しく述べられています．この記事を受けて，この「精選過去問 10 問」が AtCoder サイト上で AtCoder Beginners Selection - AtCoder (ABS) としてまとめられるとともに，ほかの競技プログラマーの方々によって，C++ にとどまらない，多数のプログラミング言語 *2 による解答例及び解説が寄せられています．

今回私がとりあげる F# についても，すでに kuuso1 さんが AtCoder に登録したら解くべき精選過去問 10 問を F# で解いてみた - Qiita を書かれ，F# の概要，特徴的言語機能，ならびに F# による ABS の解き方（問題自体の解法も含む）について，丁寧に解説されています．そのため，私が重ねて記事を作成する必要性はあまりなかったかもしれません．しかし，私自身のためのメモを兼ねて，またせっかく解いたこともあり，本記事を執筆しました．

F# は関数型とオブジェクト指向を併せ持つマルチパラダイム言語です．競技プログラミングのオンラインジャッジでは，AtCoder のほかに yukicoder および HackerRank で使用可能です．また，出力ファイルのみをもとに判定する，かつての Google Code Jam のようなコンテストでも，当然使用可能です．本記事ではなるべく「関数型っぽい」*3 コードで ABS を解くことを目的とします．競技プログラミングで必須である標準入出力からはじめて，基本的な言語機能やライブラリの用法も適宜解説します．

なお，私は普段 Python と Haskell を競技プログラミングで多用しているので，その影響が強いコードになっています．そのため，以下のコードが必ずしも一般的な F# のコーディングスタイルに沿っているとは限りません．理解のサポートとして，適宜，Python や Haskell など他言語との比較についても言及しています．なお，これら二つの言語についても，すでにほかの方々による ABS の解説記事が存在します．

コード例と解説

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

まずは，0 問目 (!) である PracticeA - はじめてのあっとこーだー（Welcome to AtCoder） で，標準入出力を練習しましょう．コード例は次の通りです．

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


// (1) エントリーポイント
[<EntryPoint>]
let main argv = 
    // (2) 標準入力から一行読み取り，整数に変換し， a を得る
    let a = stdin.ReadLine() |> int
    // (3) 標準入力から一行読み取り，空白で分割し，2 整数 b, c を得る
    let [| b; c |] = stdin.ReadLine().Split(' ') |> Array.map int
    // (4) 標準入力から一行読み取り，文字列 a を得る
    let s = stdin.ReadLine()
    // (5) printfn 関数で計算結果を出力し，改行する
    printfn "%d %s" (a + b + c) s
    // 正常終了を示す終了コード
    0

上の (1) に示したように，エントリーポイント *4 を明示的に指定できます．引数 argv はコマンドライン引数ですが，競技プログラミングではほとんど使いません．また，(2)-(4) は，競技プログラミングで必須の，標準入力から一行読み取り，必要な操作を施して変数に格納する操作です．ここで，(3) では，いわゆるパターンマッチングを使っています．右辺の stdin.ReadLine().Split(' ') |> Array.map int は，標準入力から一行読み取り（ここでの結果は string），空白で分割し（同 string），各要素を整数に変換 （同 int） する操作を示しています（|>はパイプライン演算子）．すなわち，最終結果は二つの int 値を格納した配列 int[] になることが期待されます．そこで，これに対応するパターン [| b; c |]を使い，変数 b, c に各 int を格納しています*5．最後の (5) printfn 関数は C 言語の printf 関数や Haskell の Text.Printf.printf 関数と似ていますが，F# の printfn では出力後改行されることに注意して下さい．

ABC086A - Product

(*
    ABC086A - Product
    https://beta.atcoder.jp/contests/abs/tasks/abc086_a
*)


(*
    (1) 所与の 2 整数 a, b の積が偶数か判定して返す関数
    型注釈により引数の型を明示している．返り値は型推論に任せる
*)
let isEvenProduct (a : int) (b : int) =
    // 最後に書いたものが返り値となる．return は不要
    (a * b) % 2 = 0


// エントリーポイント
[<EntryPoint>]
let main argv =
    // 入力を受け取る
    let [| a; b |] = stdin.ReadLine().Split(' ') |> Array.map int
    // (2) 判定し，その結果を出力する
    printfn (if isEvenProduct a b then "Even" else "Odd")
    0

上記 (1) のように，自作の関数を定義できます．return が不要で，最後に書いたものが返り値となるのは，Haskell, Scala や Ruby に似ているかもしれません．また，(2) のように，if 条件式を使って条件分岐を行います．C 言語や Python の if 文よりも，Haskell の if 式によく似ています．

ABC081A - Placing Marbles

解法

与えられた文字列に，'1' が何回登場するかを求めればよいです． 実装上は，文字列を数（0 または 1）の配列に見立てて，その和を求めても同じことになります．

コード例
(*
    ABC081A - Placing Marbles
    https://beta.atcoder.jp/contests/abs/tasks/abc081_a
*)


// (1) System 名前空間内のメソッド (Char.GetNumericValue) を利用する
open System


(*
    (2) 文字列を受け取り，各文字に対応する数の和を求める関数
*)
let countCells (ss: string) =
    Seq.map (Char.GetNumericValue >> int) ss |> Seq.sum


[<EntryPoint>]
let main argv = 
    // 入力を string として受け取る
    let ss = stdin.ReadLine()
    // 計算結果を出力する
    countCells ss |> printfn "%d"
    0


上記 (1) では，.NET Framework *6 の System 名前空間 にある Char.GetNumericValue メソッドを使うために open を記述しました．Python や Haskell の import と似ています．このメソッドは与えられた char を対応する float に変換する（例：'1' から 1.0 へ）もので，次の (2) で使います．このように .NET の遺産を使えるのも，F# の利点です．(2) では，配列やリスト，文字列など，同じ型の要素が連なったものを，シーケンス としてまとめて一般的に扱えることを利用しています．上で，Char.GetNumericValue >> int は合成関数であり，引数を受け取り Char.GetNumericValue に与え，その返り値を後者のint に与え，その返り値を返すものです．これを string である ss の各要素に Seq.map で適用したうえで，得られた int[] の和を Seq.sum で計算しています．

ABC081B - Shift only

解法

整数 A_i に含まれる素因数 2 の個数を B_i とすれば， \min B_i が答えです．

コード例
(*
    ABC081B - Shift only
    https://beta.atcoder.jp/contests/abs/tasks/abc081_b
*)


(*
    (1) 与えられた整数が，2で何回割り切れるかを返す関数
    再帰を用いているので，rec キーワードが必要
*)
let rec countFactors (n : int) =
    let d = n / 2  // 2 で割った商
    let m = n % 2  // 2 で割ったあまり
    if m = 0 then 1 + countFactors d
    else 0


(*
    (2) 与えられた整数のシーケンスから，求める最大の操作回数を求める
    Seq.min は，シーケンスの要素の最小値を求める
*)
let maxOperations (xs : seq<int>) =
    Seq.map countFactors xs |> Seq.min


[<EntryPoint>]
let main argv =
    // 本問では，N は不要なので読み捨ててよい
    let _ = stdin.ReadLine()
    // A を配列（シーケンスとして扱える）として読み取る（便宜上 xs としている）
    let xs = stdin.ReadLine().Split(' ') |> Array.map int
    // 答えを出力
    maxOperations xs |> printfn "%d"
    0

上記 (1) のように，再帰を用いた関数を定義するには rec キーワードが必要です．ここは Python や Haskell とは違います．

ABC087B - Coins

解法

条件 500p + 100q + 50r = X かつ 0 \le p \le A, 0 \le q \le B, 0 \le r \le C を満たす (p, q, r) を全探索し，その個数を求めればよいのです．実装上は，見つかったときに 1 を返し，その和を求めます．

コード例
(*
    ABC087B - Coins
    https://beta.atcoder.jp/contests/abs/tasks/abc087_b
*)


(*
    (1) 全探索により求める場合の数を計算する関数
    シーケンス式を用いている
*)
let countWays (a : int) (b : int) (c : int) (x : int) =
    let cands =
        seq {for p in 0 .. a do
                for q in 0 .. b do
                    for r in 0 .. c do
                        if 500 * p + 100 * q + 50 * r = x then
                            yield 1}
    Seq.sum cands


[<EntryPoint>]
let main argv = 
    let a = stdin.ReadLine() |> int
    let b = stdin.ReadLine() |> int
    let c = stdin.ReadLine() |> int
    let x = stdin.ReadLine() |> int
    countWays a b c x |> printfn "%d"
    0

上記 (1) では，シーケンス式 を用いて，条件を満たす (p, q, r) を直感的記述で列挙しています．これは Haskell や Python のリスト内包表記（今回は Python のジェネレータ式［内包表記］がより近いか）に似ています．なお，この表記は，値が必要となるまで計算されないという性質がある，シーケンスを与えます．表記を変えて，配列やリストを得ることもできますが，今回の場合には，シーケンスを使ったほうが性能上よいでしょう．

ABC083B - Some Sums

解法

問題文の条件通りに，素直に全探索しましょう．

コード例
(*
    ABC083B - Some Sums
    https://beta.atcoder.jp/contests/abs/tasks/abc083_b
*)


open System


// 桁和を求める関数
let sumOfDigits (n : int) =
    string n |> Seq.map (Char.GetNumericValue >> int) |> Seq.sum


// 与えられた条件を満たす整数の和を，全列挙により求める
let solve (n : int) (a : int) (b : int) =
    let cands =
        seq {for i in 1 .. n do
                let s = sumOfDigits i
                if a <= s && s <= b then yield i}
    Seq.sum cands


[<EntryPoint>]
let main argv = 
    let [| n; a; b |] = stdin.ReadLine().Split(' ') |> Array.map int
    solve n a b |> printfn "%d"
    0

ABC088B - Card Game for Two

解法

カードを降順で整列し，値の大きいものから両者が交互にとっていくのが最適です．

コード例
(*
    ABC088B - Card Game for Two
    https://beta.atcoder.jp/contests/abs/tasks/abc088_b
*)


let calcDelta (n : int) (xs : int[]) = 
    // Alice と Bob の得点の和は，a[] の和（便宜上 xs とする）
    let totalScore = Array.sum xs
    // a[] を昇順ソートして，逆順にする
    let ys = Array.sort xs |> Array.rev
    (*
        Alice がとるカードを集めたシーケンスをつくる
        ここで，0 .. 2 .. n - 1 は，0, 2, 4, ..., n - 1 の意味
        また，ys.[i] は，配列 ys の第 i 要素
    *)
    let alices = seq {for i in 0 .. 2 .. n - 1 do yield ys.[i]}
    let aliceScore = Seq.sum alices
    let bobScore = totalScore - aliceScore
    aliceScore - bobScore


[<EntryPoint>]
let main argv = 
    let n = stdin.ReadLine() |> int
    let xs = stdin.ReadLine().Split(' ') |> Array.map int
    calcDelta n xs |> printfn "%d"
    0

ABC085B - Kagami Mochi

解法

与えられた d_1, d_2, \cdots, d_N にある値の重複を取り除き，各値が 1 回ずつ登場するようにした d'_1, d'_2, \cdots, d'_M を考えると，その列の長さ M が答えです．すなわち， d_1, d_2, \cdots, d_N に distinct な値が何個あるかを数えます．

コード例
(*
    ABC085B - Kagami Mochi
    https://beta.atcoder.jp/contests/abs/tasks/abc085_b
*)


let computeMaxHeight (ds : seq<int>) = 
    Seq.distinct ds |> Seq.length  // そのものずばりの関数がある


[<EntryPoint>]
let main argv = 
    let n = stdin.ReadLine() |> int
    // (1) 複数行の値をシーケンスに格納する
    let ds = seq {for n in 1 .. n do yield stdin.ReadLine() |> int}
    computeMaxHeight ds |> printfn "%d"
    0

複数行の値を読み取るのにも，(1) のごとくシーケンス式を使えます．なお，後で入力値に行う処理によっては，配列やリストに格納したほうがよいこともあります．今回は上の関数で 1 回使うだけなので，これで OK です．

ABC085C - Otoshidama

解法

全探索により解を探索します．解が存在しない場合に注意しましょう．

コード例
(*
    ABC085C - Otoshidama
    https://beta.atcoder.jp/contests/abs/tasks/abc085_c
*)


// (1) 全探索による
let findCand (n : int) (y : int) =
    // 簡単のため，Y を 1000 で割っている
    let y0 = y / 1000
    let cands =
        seq {for a in 0 .. n do
                for b in 0 .. n do
                    let c = n - a - b
                    if c >= 0 && 10 * a + 5 * b + c = y0 then
                        yield (a, b, c)}
    Seq.tryHead cands


[<EntryPoint>]
let main argv = 
    let [|n; y|] = stdin.ReadLine().Split(' ') |> Array.map int
    // (2) option 型から値を取り出して出力する
    match findCand n y with
        | None -> printfn "-1 -1 -1"
        | Some((a, b, c)) -> printfn "%d %d %d" a b c
    0

上記 (1) のように，解たちを集めたシーケンスをつくり，その先頭を答えとして返します．解が存在しない場合もあるので，option 型を返す Seq.tryHead を使っています．解が存在する場合には Some が，しない場合には None が返ります．これは Haskell の Maybe モナド（Just a または Nothing）とよく似ています．そのままではうまく出力できないので，(2) のように match を用いて値を取り出しています．これは Haskell の case 文に似ています．

ABC049C - 白昼夢 / Daydream

解法

文字列 S の各文字を逆順にしたものを S' とします．また，"dream", "dreamer", "erase", "eraser" をそれぞれ逆順にしたものを U_1, U_2, U_3, U_4 とします．このとき， S' の先頭から U_i のいずれかを取り去り，得られたものを新たな S' とする操作を繰り返し，空文字列にできるかを判定することができればよいことになります．

コード例
(*
    ABC049C - 白昼夢 / Daydream
    https://beta.atcoder.jp/contests/abs/tasks/arc065_a
*)


// 文字列 s の接頭辞として p があれば，それを取り去る
let stripPrefix (p : string) (s : string) =
    if s.StartsWith(p) then s.Substring(p.Length) else s

(*
    文字列を反転する関数
    https://rosettacode.org/wiki/Reverse_a_string
*)
let reverseString (s : string) = new string (s.ToCharArray() |> Array.rev)


// 与えられた追加する文字列をそれぞれ反転させた配列
let reversedSufs = Array.map reverseString [|"dream"; "dreamer"; "erase"; "eraser"|]


// ボイラープレート．もう少し簡潔に書けるかも
let rec judge (s : string) =
    if Seq.isEmpty s then true
    elif s.StartsWith(reversedSufs.[0]) then stripPrefix reversedSufs.[0] s |> judge
    elif s.StartsWith(reversedSufs.[1]) then stripPrefix reversedSufs.[1] s |> judge
    elif s.StartsWith(reversedSufs.[2]) then stripPrefix reversedSufs.[2] s |> judge
    elif s.StartsWith(reversedSufs.[3]) then stripPrefix reversedSufs.[3] s |> judge
    else false


[<EntryPoint>]
let main argv = 
    // 文字列を反転してから渡していることに注意
    let t = stdin.ReadLine() |> reverseString
    printfn (if judge t then "YES" else "NO")
    0

ABC086C - Traveling

解法

時刻 t では (x, y) にいて，その次の時刻 t' では (x', y') にいるような移動ができるかを考えましょう．このときに， \Delta t = t' - t および \Delta r = |x' - x| + |y' - y| とおくと， \Delta t \ge \Delta r かつ \Delta t \equiv \Delta r (mod 2) が満たすべき条件です（参照：公式解説）．この条件を満たせば，有効な移動方法が存在することになります．この判定を繰り返し，すべての移動が valid になるかを求めます．

コード例
(*
    ABC086C - Traveling
    https://beta.atcoder.jp/contests/abs/tasks/arc089_a
*)


(*
    時刻 t1 で (x1, y1) にいて，時刻 t2 で (x2, y2) へ移動できるか
    タプルを利用して実装している
*)
let isValidMove ((t1, x1, y1) : int * int * int) ((t2, x2, y2) : (int * int * int)) =
    let dt = abs (t2 - t1)
    let dxy = abs (x2 - x1) + abs (y2 - y1)
    dxy <= dt && dxy % 2 = dt % 2


// (1) 与えられた移動の列は，有効か
let isValidTravel (zs : seq<int * int * int>) =
    let zs' = Seq.append [(0, 0, 0)] zs  // 初期位置を加える
    Seq.pairwise zs' |> Seq.forall (fun (zi, zj) -> isValidMove zi zj)


[<EntryPoint>]
let main argv = 
    let n = stdin.ReadLine() |> int
    let zs =
        seq {for _ in 1 .. n do
                let [|t; x; y|] = stdin.ReadLine().Split(' ') |> Array.map int
                yield (t, x, y)}
    printfn (if isValidTravel zs then "Yes" else "No")
    0

上の (1) では，Seq.pairwise 関数を使っています．これは，例えば [1, 2, 3, ...] のようなシーケンスがあったときに，[(1, 2), (2, 3), ...] を返す関数です．今回は，各移動について判定し，それらの結果全てが valid であることを確認すべく，Seq.forall を使いました．Python や Haskell の all 関数に似ています．Seq.forall には述語となる関数を与えるのですが，型が合わないのでそのままでは isValidMove を与えられません．そこで，ラムダ式をかませています．

感想

ここまで，ABS を題材にして，F# による競技プログラミングによる基本を説明しました．私は F# をはじめてまもないのですが，今回の取り組みを通じて，F# を体系的に学ぼうという思いを新たにしました．特に，上で述べたように，Python や Haskell で学んだ書き方に引きずられすぎず，F# らしいコーディングスタイルを身につけたいものです．今回の記事が，今まで使ってきたのとは別の言語で競技プログラミングに取り組むきっかけとなれば幸いです．

*1:競技プログラミングで多用される言語のひとつ．

*2:本記事執筆時点でおよそ 30 言語．

*3:明確な定義はありません．

*4:プログラムのうち最初に実行される関数．C 言語での main 関数に近い．

*5:なお，パターンが網羅的ではないという警告を得るが，本問では入力の形式上考慮しなくてよい．

*6:大まかには，F# や C# が動作する基盤となっているシステム．