競技プログラミングを学ぶための、おすすめの練習法

• 

ステップ1：プログラミング言語を学ぶ

最初のステップは、ある1つのプログラミング言語 (C++やPythonなど) を習得することです。競技プログラミングの問題を解くには、一番簡単な問題であっても実際にプログラムを書く必要があるため、このステップは非常に大切です。

それでは、プログラミング言語を習得するにはどうすれば良いのでしょうか。おすすめのオンライン上の教材として、以下の2つが挙げられます。

APG4b：AtCoder Programming Guide for Beginners

「APG4b」は、国内最大級の競技プログラミングサイト「AtCoder」が提供するC++入門用教材です。解説と演習問題がセットで提供されているため、非常に進めやすい教材となっています。なお、この教材は4章までありますが、競技プログラミングを始めるにあたっては2.02節まで取り組めば十分です。

ITP1：Introduction to Programming I

「ITP1」は、会津大学のオンラインジャッジAOJが提供する、プログラミング入門用教材です。前項で記したAPG4bはC++しかサポートしていませんが、この教材はC++、Python、JAVA、Cの4つの言語について解説が記されているため、Pythonなどの他の言語を学びたい方にもおすすめです。なお、この教材は11章までありますが、競技プログラミングを始めるにあたっては10章まで取り組めば十分です。

ステップ2：競プロの問題形式に慣れる

次のステップは、競技プログラミングの問題形式に慣れることです。競プロでは、標準入力を受け取る必要があったり、実行時間制限に間に合わなければ不正解となったりするなど、特徴的な形式がいくつかあるため、問題形式に慣れることは非常に大切です。

それでは、問題形式に慣れるためにはどうすれば良いのでしょうか。おすすめの方法は、AtCoderが提供する入門用教材「AtCoder Beginners Selection」を解くことです。たった10個の問題を解くだけで、競プロの問題傾向や、今後上達するにあたって重要となる「計算量の感覚」などが身に付くため、ぜひ取り組んでいただければと思います。なお、AtCoder Beginners Selection の解説は、大槻兼資氏の記事「AtCoder に登録したら次にやること ～これだけ解けば十分闘える！過去問精選 10 問～」に掲載されています。

• 

ステップ3：アルゴリズム・思考テクニックを知る

ここまで進めると、AtCoderで定期的に開催されている「AtCoder Beginner Contest（ABC）」で出題される全7問のうち、2問程度が解けるようになります。しかし、さらに多くの問題を解けるようになるには、プログラムの実行時間を速くするための「アルゴリズム」や、典型的な「思考テクニック」を身に付ける必要があります。

それでは、アルゴリズムや思考テクニックを身に付けるにはどうすれば良いのでしょうか。筆者作成の教材で誠に恐縮ですが、『競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術』（発行：マイナビ出版）を読み、その演習問題を解くことがおすすめの方法の1つです。

この本では、競プロで出される知識を77個のポイントに整理し、フルカラーの図解でわかりやすく解説しているため、初学者にとっても取り組みやすい内容になっています。興味のある方はぜひお読みください。

• 

  紙面イメージ

ステップ4：過去問を解く

競プロではアルゴリズムなどの知識を付けることも重要ですが、「実際の問題に応用する力」もそれと同じくらい重要です。

例えば、二分探索と動的計画法という2つのアルゴリズムを組み合わせて解く問題が出題されたとしましょう。もちろん2つのアルゴリズムを知っていることが、この問題を解く前提条件になりますが、アルゴリズムをたんに知っていることと、「ここで二分探索を使えば良いのか」「こう組み合わせれば良いのか」と考えて実際に問題を解くことでは、大きなギャップがあります。

それでは、応用力を付けるにはどうすれば良いのでしょうか。筆者おすすめの方法はAtCoderの過去問を解くことです。過去問を解くにあたっては「AtCoder Problems」というサイトがとても便利ですので、ぜひご活用いただければと思います。

しかし、AtCoderの過去問は5000問以上あるため、どれから手を付ければ良いか分からないという方も多いでしょう。そこで初心者の方は、直近10～20回のABCの2問目から4問目に挑戦することをおすすめします。

• 

ステップ5：実装力を付ける

競プロのコンテストでは、制限時間内にできるだけ多くの問題を解くことが要求されるため、プログラムを実装する速度も大切です。そのため、過去問がある程度解けるようになったら、自分なりの実装のフォームを意識したり、どうすればプログラムをバグらせずに済むのかを分析してみたりするのも良いでしょう。

ステップ6：コンテストに参加する

最後に、競プロ上達にあたっては、たくさんのコンテストに参加することが一番大切です。

しかし、世界ではさまざまなコンテストが開催されているため、どれに出場すれば良いか分からない方も多いでしょう。そこで初心者の方は、前述のABCに参加することをおすすめします。毎週土曜か日曜に定期的に開催されるほか、日本語の問題文が提供されており、比較的取り組みやすいと思います。

なお、このコンテストは「Beginner」という名前が付いているとおり、AtCoder開催のコンテストの中で最も簡単ではあるのですが、後半の問題は上級者向けであることに注意してください^※。例えば、筆者は日本国内でトップ50に入る実力を持っていますが、それでも最後の問題が解けるかどうかは五分五分です。多くの問題が解けないからといって挫折せずに、モチベーションを保つことも重要です。

※一度でも出題される全7問中4問解ければ、競プロ中級者の仲間入りと言っても良いでしょう