競技プログラミングのためのF#入門

サンプルコード

ごちゃごちゃと説明を読むよりもコードをさっと見たい人も多いでしょう. データ構造とアルゴリズム, さらには私の競プロのコードを集めたAlgorithmsAndDataStructureByFSharpを参考にしてください. 特に次の2ファイルが役に立つでしょう.

基本的に収録しているF#コードのインデントは標準の4ではなく2です.

C#との相互運用

.NETの資産が使えます. F#との相性は必ずしもよくないものの, 入門レベルでも.NETの破壊的なQueueはよく使います. F#標準の非破壊的なQueueはないようです.

F#開発環境構築

F#入門

まずは命令型的なコードの直移植に役立つ要素から解説し, 関数プログラミング的な最小限の解説をします. 競技プログラミングの実コードが大量にあるため例はほぼ割愛します.

一般的な特徴

(可変な)変数定義

for

1
2
for i in 0..10 do
  pritfn "%A" i
1
2
for i in 10..(-1)..0 do
  printfn "%A" i

データ構造は配列を例にする

配列リテラル

配列の参照

forの二つの役割: 新たな配列作成・結果の積み上げ

関数の定義

1
2
3
4
5
#r "nuget: FsUnit"
open FsUnit

let f x y = x + y
f 2 3 |> should equal 5
1
2
3
4
5
#r "nuget: FsUnit"
open FsUnit

let f = fun x y -> x + y
f 2 3 |> should equal 5

関数の部分適用

1
2
3
4
5
6
#r "nuget: FsUnit"
open FsUnit

let plus x y = x + y
let plus2 x = plus 2 x
plus2 3 |> should equal 5

パイプライン演算子|>

map

1
2
3
4
5
#r "nuget: FsUnit"
open FsUnit

[|1..5|] |> Array.map (fun i -> i*2)
|> should equal [|2;4;6;8;10|]
1
2
3
4
5
#r "nuget: FsUnit"
open FsUnit

[|1..5|] |> Array.map ((*) 2)
|> should equal [|2;4;6;8;10|]

fold

1
2
[|1..3|] |> Array.fold (fun acc i -> acc + i) 0
|> should equal 6
1
2
(0,[|1..3|]) ||> Array.fold (fun acc i -> acc + i)
|> should equal 6
1
2
3
4
#r "nuget: FsUnit"
open FsUnit

[|1..3|] |> Array.reduce (+) |> should equal 6

配列処理関数の最後の引数は配列

再帰関数

return

その他の配列処理

注意

剰余の処理

他の言語のコードを参考にする場合は気をつけるべき要素です.

F#は負の数の剰余を考えると負の数が出てきます. 特にF#では(-1) % 1000 = -1です. 一方例えばPythonでは(-1) % 1000 = 999です. この挙動が問題になる場合は剰余を取りたい数を足してから剰余を取りましょう. 特にF#では((-1) + 1000) % 1000 = 999が得られます.

入出力の基礎

注意

私は以下のテンプレートを使っています. 注意を箇条書きにします.

入門レベルの入出力なら下記コードの多少のバリエーションでまかなえます. 私の勉強が進んでもっと凝った入出力テンプレートが必要になってきたら追記・修正します.

記号選択

テンプレート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#r "nuget: FsUnit"
open FsUnit

System.IO.Directory.SetCurrentDirectory __SOURCE_DIRECTORY__

let solve Xa =
  let MOD = 1_000_000_007L
  System.Int32.MaxValue
  System.Int64.MaxValue
  1

let N = stdin.ReadLine() |> int64
let M = stdin.ReadLine() |> bigint.Parse
let D,X = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
let Xa = stdin.ReadLine().Split() |> Array.map int64
let Aa = Array.init N (stdin.ReadLine() |> int64)
let Aa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int64 |> fun x -> x.[0],x.[1])
let Alls = Console.ReadLine() |> Seq.initInfinite |> Seq.takeWhile ((<>) null)
let S = stdin.ReadLine()
solve Xa |> Array.map string |> String.concat " " |> stdout.WriteLine
solve Xa |> Array.iter stdout.WriteLine
solve Xa |> stdout.WriteLine

solve Aa |> should equal 1