はじめに

意図・目的・背景

この記事群ではF#による競技プログラミング入門と題して関数型のデータ構造やアルゴリズムを議論します. 特にAtCoderを軸に展開します. AtCoderと関連した書籍・オンライン教材も適当な意味で組み合わせて使います. 2022/11時点では本格的な勉強をはじめて一年程度の競プロ初心者で, 私の学習ログの側面もあるため必ずしも専門的に優れた内容にはなっていません.

私は大学学部時代は物理, 修士は数学だったため計算機科学の素養がありません. 数値計算・数式処理系の素養があるわけでもありません. しかしこれらで遊び倒したいとは思っていていくらか勉強はしています. そしてその中で高速化に関連したデータ構造やアルゴリズムの重要性を痛感しています.

一方でプライベートで数学・物理・プログラミングのコンテンツ販売や通信講座を運営していて, そのコンテンツ作りの中で可視化やシミュレーションの需要に応えるための勉強も続けています. 自分が数学・物理を志す中高生だった頃に「こんなことをしたかった」と思っていた環境がいまや簡単に構築できます. そうした中高生向けのコンテンツ・サービス展開も含めて展開を考えているのも合わせ, 自分の趣味としての取り組みも含め, ゴリゴリの数値計算の厳しさとは別に何か遊べるネタがないか探す中で改めてデータ構造とアルゴリズム学習の観点から, 競技プログラミングに辿り着きました.

そして競技プログラミングは整数まわりの算数・数学要素もあれば, 場合の数や数え上げに関する数学要素もあります. とにかく大量に計算する意味で算数・数学枠に入れられるのではないかと思っていて, 実際に私はこの視点で楽しんでいます. 一般的なプログラミングで重要なコーナーケースの議論は競技プログラミングでも必要です. そして数学での反例の構成の訓練やその意義を知るためのアプローチの一つとしても使えないかと思って研究中です.

プログラミングの教育用の教材・サービスを作る上でもう一つ課題だったのはコードが腐る現象です. いわゆるアプリ開発・ゲーム開発では環境やツール・ライブラリの発展に応じて昔のコードが動かなくなります. このメンテナンスがとにかく苦行です. あくまで算数・数学・物理にこそ興味があって, プロダクトがほしいわけでもない状況でメンテナンスに時間を取られたくありません. 数値計算系のプログラムも同じで, 特に今流行りのPython・Juliaを使うとなるとライブラリを大量に使う以上メンテ地獄からは逃れられません. かといってC/C++/とgnuplotなどの枯れた技術を使うとそもそもの導入ハードルが高くなります. 一方データ構造とアルゴリズムは凝った言語機能を使うわけでもなく, 一度書いたらそう簡単には腐りません. 上で書いたように数学・物理への応用ではプログラムは高速化したいモチベーションが高いため, 決して無駄にもなりません. これも競技プログラミングで遊び倒してみようと決めた大きな理由の一つです.

2022/11時点で私はF#を仕事で使っているわけでもなければ, 現時点で関数型の言語を仕事で使っているわけでもありません. 特にプロジェクトベースの本格的なF#プログラムを書いた経験もなく, fsxでのスクリプトしか書いたことがありません. 最近はF#を書きたいから競技プログラミングに取り組んでいる側面さえあります. 自作Webアプリ作成で使っているJavaScriptをはじめPython・Juliaにはたくさん情報がある一方, お気に入りのF#は英語であっても極端に情報がありません. データ構造とアルゴリズムの観点から言えば関数プログラミングに特化した本やコンテンツ自体が少なく, あったとしてもHaskellがベースのように思います.

一方で.NET系としてC#には一定の人口がいます. 特にAtCoder社長のchokudaiさんはC#erと聞いています. そうした人を巻き込みつつF#人口を増やすべく, まずは自分から情報を出そうとしたのがこの記事群です.

言語選定の理由

まず関数プログラミングが一つの基準です. 仕事でHaskellを書いていた時期があり, 本当に大変だったものの非常に肌に合って読み書きしていて気持ちよかったのが理由です. 数値計算を考えるならC/C++/Rust, 数式処理を考えるならお手軽なSymPyがあるPythonがいいのでしょう. しかし便利に使える状況ならいわゆる関数型の言語を使いたいと思っています.

一方でHaskellは読み書きしていて楽しいものの私の手に余るのも現実です. 関数プログラミングの楽しさは享受しつつ, 程々にゆるい言語がないかと思ううちにF#に出会いました. Microsoft製の言語であるため, 私がメインマシンとして典型的に使うWindowsとの相性は問題ありません.

以前Windows上のOCamlではまっていたとき, OCamlのプロに「OCamlはWindowsで使うものではない」と言われたこともあり, OCamlはWindows対応がつらそうな印象があります. Haskellにも時々Linux前提のような印象を受けます.

Haskellほどではないにせよ, F#は標準ライブラリが充実しています. OCamlは「それもないのか」と思うほど標準ライブラリが充実していないように思います. 例えばArrayモジュールにsumがありません. もちろんその程度はすぐに書けますが, この程度の処理もいちいち書かないといけないのは億劫です. ライブラリを自由に導入できるわけではない競技プログラミング環境でOCamlはつらそうで, それもOCamlを避けた理由です.

自分だけならWSLなりDockerなり回避法はあります. しかし算数・数学・物理に取り組みたい中高生に真っ先に勧められる手段ではありません. 私のメインエディタはEmacsで, 私自身はあまり使っていないものの, 同じMicrosoft製のVSCodeによる軽量な開発環境整備も簡単でWindowsユーザーにも勧めやすい言語です. VSCode・Emacsともに程良い感じのREPLがあってとにかく快適です. (ライブコーディングの動画を撮るといいのかもしれません.)

Try F#のような環境もあるとはいえ, 情報の少なさもあって必ずしも中高生向けにF#を勧めにくい状況はありますが, 自分自身が気持ちよく取り組める言語として現状ではF#を選んでいます.

Haskellと違って雑なprintfデバッグもやりやすく, 型が強い割にはスクリプト言語のような書き心地で気持ちよく書けます.

AtCoder上でもいわゆる関数型言語はいくつかあります. 全ての言語と特徴が把握できていないものの, 少なくともClojureはあります. ただAtCoderのClojureは異様に遅いです. ちなみにAtCoder上の実行時間としてはF#は大して速くなく, 同種のコードでOCamlやHaskellの数倍から数十倍の時間がかかる場合はよくあります. ただし少なくともAtCoder上で他の言語と直接比較しても大したご利益はなく, コンパイル型の言語なら速度はほぼ問題ないというコメントもあります. そもそもF#を選んだ時点で一定程度最速を求めるのは放棄しているため, 他の言語との比較の意味での速度は必要以上に気にしません. ただし, もちろんF#プログラムとしての速度や効率はできる限り注意します.

F#のよい所

F#のよいところの宣伝といえばcannorinさんの記事が有名です.

他のよい点として, Haskellよりは遥かに命令型的に書きやすい点があります. C#を書いた経験がほぼないためひどくいい加減な感想ではあるものの, (おそらく)型まわりの指定がほぼないC#のようにも書けます. 特にCやPythonで書かれたアルゴリズムを直移植しやすい利点があります. 実際, 私自身も解答が思いつかずF#の解答提出がなかったり, 理解しにくいコードだった場合はPythonなど他の言語からコードを直移植してから書き直す場合があります. これらは人口が多いためサンプルコードも多く, 自分にとって読みやすいコードを見繕いやすくて便利です.

F#人口は少ないもののHaskellerは一定数いるため, Haskellから移植する場合もあります. さらに関数型で書くと逆にわかりにくくなる場合もあります. Haskellだとモナドの面倒なプログラムを書かないといけない場面でも, F#なら命令型的なコードが簡単に書けるのもよい所です.

AtCoderを選ぶ理由

F#が使えるからです. AOJ, Aizu Online JudgeはHaskell・OCamlはあってもF#がなく, アルゴ式もHaskellはありますがF#がありません. 私はデータ構造とアルゴリズムマニアというわけでもなく, そこまで調査に時間を使いたいわけでもないため, 手軽かつ有名で人口も多く日本語が使えて中高生にも勧めやすいとなるとAtCoderに利点があるように思います.

AOJにはアルゴリズムだけではなくデータ構造などに関しても教育用コンテンツ群があります. アルゴ式はもとから教育用サービスです. これらで使える言語ならこの二サービスもお勧めです.

書くコードの方針: 2022/11時点

曖昧に次の基準を採用して進めます.

解説の方針

お勧め学習法

何らかの手段でデータ構造やアルゴリズムの基本的な勉強はしているとして, ここでは実際の問題を解く場合のポイントを書きます. 一般的なプログラミング学習と同じく, 他人の書いたコードを読むのはとても勉強になります. 大事な点を箇条書きにします.