はじめに

「AtCoderではじめるF#入門」は、オンライン参加ができる競技プログラミングサービス "AtCoder" を通して、F#を習得するためのマガジンです。

F#とは

F#はMicrosoftが開発したOCamlベースの.NET向けのプログラミング言語で、OCamlと同様に関数型とオブジェクト指向を併せ持つマルチパラダイムな言語です。

2019年8月現在、関数型プログラミングが注目されてきており、F#も.NET上で動作する関数型言語として海外を中心に再注目され始めています。

F#は強い静的型付け言語であり、多くのケースで型の記述を省略可能となっています。
また、関数型プログラミング言語全般に言えることですが、"単純な機能を連結していくことで複雑な機能を実現する" というコーディングスタイルのおかげで、シンプルにプログラムを記述することが可能となっています。

とはいえ、2019年8月現在では F# は主流なプログラミング言語ではありません。同じ .NET での開発であれば、多くの場合 C# が選択されるでしょう。

しかし、C# や他の多くのプログラミング言語に関数型プログラミングの機能や思想が組み込まれ始めている今、関数型をメインパラダイムに持つ言語を学習することには一定の価値があります。

また、F# は .NET 上で動作する言語ですので、他の言語に比べて C# との相互運用性にも優れています。
「メインは C# で開発し、サブモジュールは F# で開発を実施する」というようなことも可能です。

このように、"シンプルにコーディングが可能" で "C#との相性も良い"、"関数型プログラミング言語" が F# という言語の特徴です。

競技プログラミングとは

"競技プログラミング" とは、競技参加者全員に同一の問題が出題され、より早く正しい解答を提出することを競い合う競技です。

競技プログラミングで出題される問題を解くには各プログラミング言語の基本的な構文をマスターしている必要があります。

また、効率的なプログラムの実装方法やアルゴリズムの実装方法なども抑えておく必要があります。

裏を返せば、競技プログラミングの問題を解けるようになったとき、上記の能力が身に付いたと言えます。

AtCoder とは

"AtCoder" は数ある競技プログラミングサービスの一つです。

当マガジンでは、AtCoder のコンテストを通して後述するレートを上げることを目標としているため、まずは こちら から AtCoder への登録をおこなってください。

競技プログラミングサービスは数多く存在していますが、AtCoderは日本企業が運営しており、問題の出題も日本語で行われるため英語が苦手な方でも手軽に始めることができます。

またAtCoderには "レートシステム" があるため、自分のレート値で実力が可視化できるのも良い点です。

AtCoderではレートが400上がる毎に "色" が変化していきます。

当マガジンでは茶色レートの後半(600~799)を目指していきます。

AtCoderのレートシステム

AtCoderのレートシステムは以下のように区分されています。各レートのコメントについては、AtCoderの高橋直大代表の記事より参考・引用させていただいております。

--------------------------------
灰色 (Eランク Rating ~ 399)

灰色になる条件は「AtCoderに1回参加する」です。そのため、AtCoderが保証できる実力は全くありません。

--------------------------------
茶色 (Dランク Rating 400 ~ 799 : 上位 50%)

AtCoderが保証できる実力ですが、正直あまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまい人が多いので、十分にやる気がある人であると言えます。

スキルとしては、

・標準入出力、if、forなどの単純な操作ができる　
・問題文を正しく理解し、仕様通りの実装をすることが出来る　
・複雑な問題や、数学的処理が必要な問題を解決する能力はない　

という感じです。

--------------------------------
緑色 (Cランク Rating 800 ~ 1199 : 上位 30%)

緑色までくると、運だけで到達することはまず出来ないラインとなってきます。
エンジニアとしてもある程度の安心感があり、「論理的に複雑な処理の実装に対応できない、なんてことはなさそう」と思わせる実力を有しています。

スキルとしては、

・深さ優先探索や幅優先探索などのキューや再帰を使った実装が出来る　
・簡単な動的計画法の問題や、少し数学的に工夫する問題など、計算量の工夫も出来始める　

という感じです。

--------------------------------
水色 (Bランク Rating 1200 ~ 1599 : 上位 15%)

水色はかなり優秀です。普通の企業で超優秀と言われるプログラマがいた時に、半数くらいがこのランクとなります。

半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。

スキルとしては、

・計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
・深さ優先探索や幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る　
・貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る　
・累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る　
・ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える　
・木構造やグラフ構造に対して適切に処理を行うことが出来る　
・一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる　

という感じです。

--------------------------------
青色 (Aランク Rating 1600 ~ 1999 : 上位 7%)

青は超優秀です。学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいます。

競技プログラミング未経験者では、このレベルと競技プログラミングで戦うことは殆どの場合は無理です。8割以上のIT企業において、アルゴリズム力はカンストです。一部企業においては、少し持て余してしまうかもしれません。

スキルとしては、

・複雑な処理でも難なく高速に実装出来る
・水色のアルゴリズム知識に加え、最大流やSegment Treeなど、高度なアルゴリズム、の知識がある　
・データ構造やアルゴリズムを知っているだけでなく、適切な場面で活用することが出来る　
・どういう問題の時にどういう計算量改善の方法があるか、というような、典型テクニックを多く知っている　
・複雑な計算量改善を要求された際に、紙などを用いてきちんと考察を進めることが出来る　
・その他、水色レベルよりも一段階能力が上昇している　

という感じです。

--------------------------------
これ以降の説明は割愛します。詳細は高橋直大代表の記事を参照ください。

黄色 (Sランク Rating 2000 ~ 2399 : 上位 3%)
橙色 (SSランク Rating 2400 ~ 2799 : 上位 1%)
赤色 (SSSランク Rating 2800 ~ 3199 : 上位 0.3%)
銀色 (SSSランク Rating 3200 ~ 3599 : 上位 0.1%)
金色 (SSSランク Rating 3600 ~  : 上位 0.03%)

おわりに

当マガジンでは競技プログラミングを通して F# に入門しますが、競技プログラマとなることを目的とはしていません。

競技プログラミングを通して、"基礎的なコーディング能力を養うこと" を目的としています。

昨今、プログラマを目指す人々が多くなってきましたが、それと同時に条件分岐やループ処理などの初歩の初歩ができず、頭を悩ませている方々も散見されるようになりました。

繰り返しとなりますが、そういった基礎的なコーディング能力の地固めを行うことが当マガジンの目的であり、「基礎的なコーディング能力を養えた」と実感するための目標が "茶色レートの後半(600~799)になる" というものです。

既に茶色レートの後半(600~799)以上のレベルの方には、当マガジンは不要です。
しかし、近年話題の関数型プログラミングの基礎を学習したいと考えているプログラミング入門者の方にはうってつけの教材です。

そういった方向に興味がある方は、ぜひご購読ください。