現役高校生が、AtCoderでレッドコーダーになるまでにやってきたこと。プログラミング上達の秘訣を全て教えます

こんにちは、はじめまして。筑波大学附属駒場高等学校 3 年生（今年 4 月から東京大学に入学予定）の米田優峻（@e869120）と申します。私は競技プログラミング（競プロ）が趣味で、AtCoder・情報オリンピック・パソコン甲子園などの大会に出場しています。2021 年 3 月時点で、AtCoder では赤色（レッドコーダー）です。また、国際情報オリンピックの 2018 年／2019 年／2020 年大会で金メダルを獲得しています。*1

とはいえ、決して簡単にこの記録を手に入れられたわけではありません。何度も挫折と失敗を経験しながら自分のスキルを磨いた結果、競プロを始めてから 3 年後にはレッドコーダーになることができたのです。

今回は「わたしの選択」というテーマで寄稿の機会を頂いたので、私が中学 1 年生の秋に競技プログラミングを始めてからレッドコーダーになるまで、そして国際情報オリンピックで 3 度目の金メダルを獲得するまで、競技者としてやってきたことについて、競プロの実力を上達させるテクニックなどを交えながら共有できたらと思います。

AtCoder などのプログラミングコンテストで問われる「プログラミング能力」「アルゴリズム構築能力」「問題解決力」といったものは、情報化社会が加速する今、とても重要になりつつあると考えています。特に 2020 年からは小学校でもプログラミング教育が必修化されるようになり、アルゴリズムやプログラミング的思考の注目度が急激に増加しています。そこで本記事では、

アルゴリズムや競プロといったものに少しでも興味を持っていただく
「私がどのような練習をしてアルゴリズム構築能力が上達したのか」を知ってもらい、上達に役立ててもらう

ことを最大の目標にします！！！

本記事の構成

この記事の全体的な構成は、以下のようになっています。

前半（1～2 章）では、競技プログラミングやアルゴリズムの面白さを読者の皆さんに知ってもらう
後半（3～5 章）では、自分が競技プログラミング上達のために、そして上達した後どのようなことを行ったかについて、上達のテクニックなどを途中で入れながら紹介する
最後に、競技プログラミングで問われる「アルゴリズム構築能力」をアップさせるために良さそうな書籍や記事を紹介する

なお、競技プログラミングを既に知っている方は [2 章]から読み始めても構いません。

章	タイトル	備考
1.	[導入～競技プログラミングについて～]	アルゴリズムやプログラミングコンテストについて紹介します
2.	[アルゴリズムの面白さ]
3.	[レッドコーダーになるまでの道筋]	本記事のメインです
4.	[国際情報オリンピックへの挑戦]	国際情報オリンピックへの挑戦などを書きます
5.	[終章～レッドコーダーとして、何かできる事はないか～]
6.	[おわりに]
7.	[関連記事・参考書]	競プロの実力などを高めたい人に適した記事等を紹介します

1. 導入～競技プログラミングについて～

本記事を読んでいる人の中には、「競技プログラミング（競プロ）」「アルゴリズム」といった言葉を始めて聞いた方もいると思います。そこで本章では、

競プロや情報オリンピックとはどのようなものか
プログラミングコンテストではどのような能力が問われるか

について、分かりやすく説明していきたいと思います。

1-1. 競技プログラミングとは？

まず、競プロとは以下のようなものです。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。 (Wikipedia より引用)

つまり、プログラミングで解ける問題が何問か出されて、制限時間内にできるだけ多くの問題を解くことが目的の競技です。いわゆるコーディング試験と似ています。競技の流れとしては、以下の図の通りになります。

特に AtCoder という有名なコンテストサイトでは、全世界で約 8000 人程度が同時にコンテストに参加しています（詳しくは [1-3. 節]で紹介します）。また、競プロでは自動採点システムという方法がとられており、ソースコードをコンテストサイトに提出すると概ね 1 分以内で正解かどうかの結果が出る他、コンテスト中はリアルタイムで順位表が更新されます。したがって、ただプログラムを書いているだけでなく、戦っている感じがあり、とても楽しいです。

さて、具体的にどのような問題が出題されるか、次節で紹介したいと思います。

1-2. 競プロで出題される問題　～アルゴリズムの改善～

まず、以下の問題を考えてみましょう。

整数とが与えられる。
以下の条件をすべて満たす整数の組の個数を求めよ。
${1 \leq i \leq j \leq k \leq N}$ である。

である。

《制約》
${1 \leq N, S \leq 100}$

この問題では、以下のように三重ループを用いて {(i, j, k)} として考えられる組を全通り調べ上げると、正しい答えが出ます。このように、競技プログラミングでは、正確に答えを出すコードを素早く実装する能力が求められます。

#include <iostream>
using namespace std;

int main() {
    long long N, S, Answer = 0;
    cin >> N >> S;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            for (int k = j; k <= N; k++) {
                if (i + j + k == S) Answer += 1;
            }
        }
    }
    cout << Answer << endl;
    return 0;
}

少し難しくした問題

では、上の問題を少し変更した、以下の問題を考えてみましょう。

整数とが与えられる。
以下の条件をすべて満たす整数の組の個数を求めよ。
${1 \leq i \leq j \leq k \leq N}$ である。

である。

《制約》
${1 \leq N, S \leq 10000}$ （変更部分）

一見上のプログラムが正常に動作するように思えますが、このようなソースコードを提出した場合実行時間超過（TLE）となり、不正解扱いとなってしまいます。

プログラムは高速に動作せねばならない

一般に、家庭用のコンピューターでは {1} 秒あたり $10^{8}$ ～ $10^{9}$ 回しか計算が行われない一方、多くの競技プログラミングの問題では、各テストケース当たり {2} 秒程度で実行が終了しなければなりません。したがって、概ね $10^{9}$ 回以上の計算回数を必要とするプログラムを提出しても正解にはなりません。

例えば、上のプログラムでは三重ループを書いており、おおよそ $N^{3}$ 回*2 のループを必要とします。したがって、 {N = 10000} の場合単純計算で $10^{12}$ 回の計算が必要となり、実行時間超過となってしまうのです。そこで、以下のような手法（アルゴリズム）を考えます。

の組を ${1 \leq i \leq j \leq N}$ の範囲で全通り試す。
とが決まれば、となるようなの値は一意に定まる。
そのとき、 ${j \leq k \leq N}$ が満たされていたら、個数をカウントしている変数にを増やす。

#include <iostream>
using namespace std;

int main() {
    long long N, S, Answer = 0;
    cin >> N >> S;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            int k = S - i - j;
            if (j <= k && k <= N) Answer += 1;
        }
    }
    cout << Answer << endl;
    return 0;
}

本質は「アルゴリズムの改善」にあり

上のようなソースコードであれば、おおよそ $N^{2}$ 回（ {N = 10000} のとき $10^{8}$ 回）*3 のループしか必要としません。したがって、 {1} 秒以内に実行が終了し、正解を出すことができます。また、少し難しいかもしれませんが、アルゴリズムを変えれば $N, S \leq 10^{9}$ の場合でも解くことができます。このように、競プロで最も面白く本質的な点は

高速に動作するようなプログラムの書き方（アルゴリズム）を考えること

にあると思います。より効率的なアルゴリズムの考察はパズル的な感じの面白さもあり、難しいアルゴリズムを思いついた時は嬉しい気持ちになるものです。競プロの世界は広く、本節で紹介した問題よりもっと難しい問題もたくさんあります。*4

1-3. 様々なプログラミングコンテストについて

さて、競技プログラミングの大まかな内容について知っていただいたところで、本節では

一番有名なコンテストである AtCoder について
中高生向けの大会である情報オリンピックについて

紹介していきたいと思います。

どのようなプログラミングコンテストがあるのか？

近年は情報化社会を担う人材への需要が急増しており、アルゴリズム構築能力・プログラミング能力といったものを競うコンテスト・資格が増加しています。本節では特に AtCoder と情報オリンピックについて紹介します。

コンテスト名	対象	備考
AtCoder	全年齢対象	日本で最も人気のあるコンテストで、約 8000 人が参加しています
CodeForces	全年齢対象	世界で最も利用者数の多いコンテストサイトの一つです
TopCoder	全年齢対象	2001 年から始まった、歴史の長いコンテストサイトです
アルゴリズム実技検定 (PAST)	全年齢対象	アルゴリズム構築能力を問う日本初の検定試験です
日本情報オリンピック (JOI)	中高生	勝ち進むと世界大会に行けるチャンスがあります
パソコン甲子園 (PCK)	高校生	高校生向けのチーム戦コンテストです
大学対抗プログラミングコンテスト (ICPC)	大学生	大学生向けのチーム戦コンテストです

AtCoder とは

毎週土曜か日曜の 21 時からプログラミングコンテストが開催されるサイトです。全世界から最大約 8000 人が参加し、リアルタイムで参加者と対戦できるようになっています。問題文が日本語で提供されているため、2021 年 3 月現在、日本では最も人気が高い競プロのコンテストとなっています。AtCoder では主に 3 種類のコンテストがあります。

コンテスト名	参加者数 (2021/3 時点)	備考
AtCoder Beginner Contest (ABC)	約 8000 人	初心者・初級者向けのコンテストです
AtCoder Regular Contest (ARC)	約 3000 人	ABC より難易度が高いです
AtCoder Grand Contest (AGC)	約 1000 人	レッドコーダーなど、トップレベル向けのコンテストです

また、AtCoder の特徴の一つとしてレーティングが挙げられます。レーティングはコンテストの戦績によって上下するため、その人の強さを表す指標になります。レッドコーダーが最高ランクで、多くの参加者の目標でもあります。また、最近はアルゴリズム構築能力のある人材に対する需要が急増しており、実際に AtCoder Jobs といったサイトでは、例えば水色コーダー以上になると就職に有利になることもあります。

「AtCoder についてもっと詳しく知りたい！」と思った方は、以下の記事をご覧ください。

日本情報オリンピックとは

日本の中高生のプログラミング能力・情報科学的能力の育成を目的として行われている、プログラミングが好きな中高生向けのコンテストです。日本で行われている 7 つの「科学オリンピック」（数学オリンピック・物理オリンピックなどを含む）のうち一つでもあります。この大会は、

競プロのコンテストである
アルゴリズム構築能力を問う大会である
無料で気軽に参加できる

という点では AtCoder と共通していますが、他にも以下のような特徴があります。

AtCoder と違い年に 1 回しか行われない
成績優秀者は国際情報オリンピックに派遣されるため、多くの中高生プログラマにとって一番の目標となる
予選を突破すると実際の会場で行われる本選に出場することができ、同じ目標を持つ選手たちと交流できる場合もある

日本情報オリンピックでは競技が 4 つの段階に分けて行われ、最も簡単な一次予選では「条件分岐・単純なループを含むプログラムが書けるかどうか」が問われる一方、最も難しい春合宿では超難問が出題され、様々なレベルの人が楽しめる大会となっています。

「情報オリンピックについてもっと詳しく知りたい！」と思った方は、以下の記事をご覧ください。

皆さん、競技プログラミングについて、ご理解いただけたでしょうか？

プログラミングコンテストで問われる「アルゴリズムを使った問題解決」、そして競技自体には、利点や面白さがたくさんあります。2 章ではそれについて紹介していきたいと思います。

2. 競プロ・アルゴリズムの面白さとメリット

21 世紀も中盤に差し掛かり、情報化社会が進行する中、プログラミング的思考ができる人材が重視される傾向が出てきています。また、2030 年には 78 万人の IT 人材が不足すると予測されており*5、競プロで使うような「アルゴリズム構築能力」を持つことが一つの武器になる時代が到来しつつあります。では、このような時代の中、競プロをやることはどのような点で楽しく、そしてどのようなメリットがあるのでしょうか。

2-1. プログラミングスキル向上に役立つ！

競プロでは、そもそもプログラムを書けなければ何も始まりません。したがって、少なくとも 1 つのプログラミング言語を習得することが最初のステップとなります*6。AtCoder などのコンテストサイトでは、初心者が気軽に練習できるサービス*7が整えられていますので、競技プログラミングをやってみることで、その機会に初めてプログラミング言語を習得するのも良いかもしれません。

2-2. アルゴリズム構築能力向上に役立つ！

AtCoder などで上位にランクインするためには、様々なアルゴリズムやテクニックを知っておくことが求められます。詳しくは [7 章]で述べますが、例えば水色コーダーになるためには、以下の 15 個のアルゴリズム・データ構造を知っておくことが重要です。

全探索	二分探索	深さ優先探索（DFS）	幅優先探索（BFS）
動的計画法（DP）	ダイクストラ法	ワーシャルフロイド法	クラスカル法
高速な素数判定法	べき乗を高速に計算する手法	逆元を計算する手法	累積和
グラフ	木構造	Union-Find

これらのアルゴリズムは、情報科学に関わる人ならば是非知っておきたい知識です。また、近年スパコン富岳などの登場でコンピュータの計算速度が向上していますが、アルゴリズム効率化の知識は計算速度とは関係なく常に役立つため、このような知識は一生使えます。競技プログラミングに参加することで、コンテストを楽しみながら将来有利になるであろう知識を付けられるのは、皆さんにとっても一石二鳥です。

2-3. 実社会の問題とプログラミングが繋がって面白い！

社会には様々な問題があふれていて、そのうちいくつかは皆さんも考えたことがあると思います。しかし、それらすべてが解けない問題ということではなく、中にはアルゴリズムの改善によって効率的に解ける問題もあります。そこで、競プロをやる過程でアルゴリズムを学習していくうちに、

あの考えていた問題はこういうアルゴリズムを使えば解けるのか！！！

実社会のああいう場面にアルゴリズムが使われていたのね！！！

と感動することがあるかもしれません。このような時に実社会とアルゴリズムが繋がって面白いです。例えば私の場合、アルゴリズムを学ぶ過程で

Google Maps のナビゲーションと最短経路問題が繋がった時
オセロ AI／チェス AI の中身と深さ優先探索が繋がった時

は感動した覚えがあります。

2-4. 難しい問題が解けた時は嬉しい！

競プロで出題される問題の中には、解けなさそうな見た目をしているものも多いです。しかし、

アルゴリズムを学習する
数学的考察力を身に付ける

などによって、競プロをやっていく過程で自然と問題が解けるようになっていきます。そこで、実力が上がって難問に挑戦した時に、解法の手筋がジグソーパズルのように見えていき、最終的に解法が分かった時はとても嬉しく思うでしょう。このような点でも競プロは楽しいです。

2-5. リアルタイムで戦えて楽しい！

[1-1. 節]でも説明した通り、AtCoder などプログラミングコンテストの多くは自動採点というシステムが利用されており、ソースコードを提出すると概ね 1 分以内で正解かどうかの結果が出ます。また、リアルタイムで以下のような順位表が更新されるため、実際に全世界からの参加者と一緒に戦っている感じがあります。

ですので、コーディング能力を高められるだけではなく、ネットゲームとしても楽しめます。

ここまで、競技プログラミングやアルゴリズムを学ぶことの面白さとメリットについて、5 個のポイントに分けて紹介してきました。文字数の都合上詳細は割愛させていただきますが、その他にも

実績で有利になることがある*8
参加費用が他の競技に比べ非常に安い
プログラムを速く実装する「実装力」が身につく*9
数学的考察力、数理パズルのような問題を解く能力が身につく
レッドコーダーなど強い参加者と同時に対戦できるので、自分の世界観が広がる

といった点が挙げられます。

次章では、私が AtCoder 最高ランクのレッドコーダーになるまで、そしてレッドコーダーになった後に行ってきたことについて、競プロ上達の道筋などを交えて紹介します。本記事のメインですので、引き続きお読みいただけると嬉しいです。

3. レッドコーダーになるまでの道筋

AtCoder の最高ランクであるレッドコーダーへの到達は、多くのプログラミングコンテスト参加者の夢となっています。しかし、簡単にレッドコーダーになれる参加者などいません。私もその一人で、練習と本番を繰り返す過程では何度も挫折と失敗を経験してきましたが、それを克服した結果、競プロを始めてから 3 年後にはレッドコーダーになることができました。本章では競プロを始めた時から、レッドコーダーになるまで、どのような方法を選び練習を進めてきたか記したいと思います。

3-1. 「アルゴリズムが面白い！」と思った中学 1 年

中学 1 年の 4 月、私は「プログラミングって楽しそう！」という単純な興味から筑波大学附属駒場中学校のパソコン研究部（通称：筑駒パ研）に入部しました。私の通っていた小学校はあまり先進的ではなく、プログラミングを本格的に学ぶような機会は無かったので、完全な初心者の状態からのスタートでした。

しかし運が良いことに、小学校とは違い、筑駒パ研にはプログラミングが得意な先輩方がたくさんいました。そこで多くの部員が主に使っている C++ を教えてもらい、手厚いサポートを受けながらソースコードを書いていくうちに、コーディングに慣れていきました。始めて 2 カ月経った頃には、現在の JOI 一次予選で問われる「入出力・配列・条件分岐・繰り返し処理などを含むプログラムを書く能力」を身に付けることができたため、毎年開催される文化祭に展示するゲームの作成に挑戦してみました。

ゲーム作成では、プログラミングというツールを用いて自分が思ったことをコンピューターに動かしてもらうというステップ自体が楽しいものです。また、自分が「面白そう！」と思ったゲームを作成するのは比較的長期間のプロジェクトであり、思い通りのゲームが完成した時は嬉しいものだと思います。（以下は高校 2 年の時に展示したゲームです。*10）

だが、少なくとも部活で展示されるゲームの多くは何のプログラムの工夫を行わなくても正常に動作してしまうため、ある意味ではただの作業なのではないかと思っている時期がありました。*11

ちょうどその頃、中学 1 年の秋のある日、先輩から AtCoder や情報オリンピックへの参加を勧められ、何問か AtCoder で出題された問題を解いてみました。世の中には全探索など単純な手法では効率的に解けない問題、そしてアルゴリズムの改善によって初めて高速に答えが求められる問題があることを知り、自分の頭で効率の良いアルゴリズムを考える面白さに気づき始めました。そこで、解ける問題の幅を広げていくために、

などを読むことで、有名なアルゴリズム（動的計画法やグラフアルゴリズムなど、主に [2-2. 節]に載っているもの）から学び始めました。なお、最近は 2015 年当時と比較すれば、初学者に分かりやすい書籍も新たに出版されている他、ネットではアルゴリズムに関する知見が得られる記事も増えていますので、本を買わずとも学習を進めていくことは可能です。詳しくは [7 章]をご覧ください。

アルゴリズムの面白さに感動し、情報オリンピックへの参加を決める

競プロの問題を解き、アルゴリズムを学んでいく過程で、

500 円以内の買い物で最大何カロリー得られるかは、ナップザック問題により計算できる
相手の年齢を当てるとき、二分探索を使えば質問回数を減らせる

など、実社会の問題とアルゴリズムが繋がっていることに気づき、感動しました。また、情報化が進行する社会の中でも、効率的なアルゴリズムを考えることこそコンピューターには難しく、人間に求められることだと考えるようになりました。

それをきっかけに、「自分も優秀な先輩方のように、いろいろな問題を効率的に解けるような能力を身に付けたい！」と思い、当時 12 月に行われていた情報オリンピックの予選に参加することを決めました。

3-2. 初めての情報オリンピックへの挑戦と挫折

私が情報オリンピックへの参加を決めたのは 11 月頃で、予選まであと 1 ～ 2 カ月しかありませんでした。しかし、私は当時から「重要な大会で勝ちたい」という気持ちが強かったため、

AIZU ONLINE JUDGE（通称：AOJ）に収録されている問題を解く
過去の情報オリンピックの予選・本選の問題のうち自分のレベルに合ったものを解く

といったことを進めていきました。一般に、競技プログラミングでは「習うより慣れろ」の精神で問題演習を行うことで、自然と解ける問題の領域が広がっていくと思います。（なお、現在は AtCoder の方が有名になっていますが、2015 年時点では AOJ の方が収録問題数が多く、練習に適していました。現在適している練習方法の一例については、レッドコーダーが教える、競プロ上達ガイドライン記事をご覧ください。）

また、私の双子の兄（@square1001）も中学 1 年の時から競プロを始めており、情報オリンピックにも出場予定だったため*12、お互いに知識を教え合い、切磋琢磨しながら実力を高めていきました。どんな時でも一緒に練習できる仲間がいたので、モチベーションにも繋がりました。多い時には 1 日 4 時間以上練習し、AOJ では解いた問題数が 100 位以内になるレベルまで過去問を解き進めました。このように、自分の興味のあることにひたすら向き合い続けた結果、当時情報オリンピックの競技人口が少なかったこともありますが、ギリギリの成績ながら予選・本選を突破することができました。

しかし、3 月に行われる春合宿での現実は、決して甘いものではありませんでした。まず、春合宿の競技問題は国際情報オリンピックの日本代表選手を選抜するために作られているため、以下のような難問ばかりが出題されるのです。

枚のカードが一列に並べられており、左から番目のカードに書かれている整数は ${A_i}$ である。が書かれたカードが枚ずつあることは知っているが、カードの並び順 ${(A_1, A_2, ..., A_N)}$ はまだ知らない。そこで、JOI 君に以下の形式の質問を回まで行うことで、カードの並びを特定するプログラムを書け。

枚のカードを指定する。左から番目と番目を選んだとする。

${A_i=A_j}$ の場合、JOI 君は ${A_i}$ と答える。

${A_i ≠ A_j}$ の場合、JOI 君は ${A_i}$ と ${A_j}$ のうち覚えやすい方を答える。つまり、予め整数の覚えやすさ ${P_0, P_1, ..., P_{N-1}}$ が決まっていて、 $P_{A_i}$ > $P_{A_j}$ の場合 ${A_i}$ を、 $P_{A_i}$ < $P_{A_j}$ の場合 ${A_j}$ と答える。

ただし、である。

《出典》JOI 2016 春合宿 1 日目 - Memory 2

この問題は典型的なアルゴリズムを 1 個か 2 個使うだけでは解けず、高度な考察力を必要とします。大部分の読者の方々が解けないほどの難易度だと思いますが、実はこの年の春合宿に出題された問題の中では簡単な方なのです。

もちろん、当時の私にとっては「12 問すべての問題が難しい」と感じました。解法が分かった問題は僅かにありましたが、100 行以上の実装を要する問題も多かったからか、コンテスト時間内に実装とバグ取りが間に合わず、本番で 1 問も完答することができませんでした。結果、20 人中 17 位という散々な成績で終わってしまい、初めての挫折となりました。

しかしながら、最終選考は 1 週間の合宿であり、当時の自分より遥かに実力の高い人と、出題された問題や今までの練習について一緒に話すなど、交流する機会がありました。そこで改めて「いつかは日本代表になりたい！」という気持ちが出てきて、周りから受けた刺激がモチベーション増加に繋がりました。そうして、合宿が終わったその日からまた、新たな練習が始まります。

3-3. 早解き力を鍛え、橙コーダーへ

合宿が終わってからまず最初にやったことは、失敗原因の分析でした。一般に、プログラミングコンテストにおいて失敗した時に、自分がなぜ良い成績を取れなかったのかを分析するのはとても重要だと思います。実際に中学 1 年の春合宿の時は、

解法が分かったのに、実装が間に合わずに得点を落としてしまった
コンテスト中の戦略や立ち回りで失敗した部分があった

というケースが何回かあって悔しかったので、これを克服する練習方法を考えました。そこで、ただ過去問を解くだけではなく、以下の点を意識して練習するようにしました。

基本的に、問題を速く解くことを意識する
問題を解く際に時間を測ったり、バーチャルコンテスト形式で練習をしたりする

なお、「バーチャルコンテスト形式」とは、AtCoder Problems や vjudge などのサービスを利用して、過去に出題された問題から何問か選んで、一定の制限時間でそれらの問題を解くという形式の練習のことを指します。場合によっては他の人と一緒に対戦することもできるため、コンテスト本番同様の気持ちで練習することができ、効率が非常に良いほか、コンテスト中の戦略確立なども同時にできるといったメリットがあります。詳しく知りたい方は、

早解きを鍛える！バーチャルコンテストのすすめ

などをご覧ください。（以下の画像は AtCoder Problems におけるバーチャルコンテストの例です）

なお、2020 年以降、初心者向けコンテストである AtCoder Beginner Contest (ABC) の開催頻度が増えているため、簡単な問題を素早く正確に解くスキル、いわゆる「早解き力」の重要性は増しており、同時にこのようなスキルがレーティングに与える影響も大きくなっています。実際に、AtCoder Beginner Contest 192 では、3 問正解の場合の順位とパフォーマンスは次表の通りであり、2 分素早く解くだけでも相当影響が大きいことが分かります。

時間	10 分	12 分	14 分	16 分	18 分	20 分	22 分	24 分
順位（約 8700 人中）	2483 位	2618 位	2781 位	2998 位	3237 位	3457 位	3660 位	3840 位
パフォーマンス	1058	1025	986	937	885	839	797	761

このように「早解き力」を鍛える練習を続けた結果、自分のレーティングに近い参加者のうち半分以上が解ける問題については、他の参加者に比べてかなり早く正解を出せるようになりました。それがきっかけでコンテストの成績が安定するようになり、橙コーダー（上位約 1%）に到達することができました。また、情報オリンピックでは「より制約を簡単にした問題」を解くことで完答できなくても部分点がもらえる特別ルールがあるのですが、早解き力を武器にすることで、取れる部分点がコンテスト中にすべて獲得できるようになりました（詳しくは [4-3. 節] を参照）。その結果、中学 1 年の時は 20 人中 17 位だった春合宿の成績も翌年には 6 位まで上昇しました。

3-4. 高難易度練習がレッドコーダーへの最後の一押しに

前章で紹介した通り、早解き力をひたすら鍛えることでレーティングが上がり続けていたので、そのままレッドコーダーになれると楽観的に捉えていた時期がありました。しかしながら、レーティングは 2600 付近 （上位約 0.5%）で頭打ちになり、半年以上の期間にわたってほとんど停滞してしまいました。

そこである時、なぜレーティングが上昇しなくなったかを分析してみたところ、以下のようなことが分かりました。

いくら早解きに成功しても、同じ点数の人のうち最高順位にしかならないため、難しい問題を 1 問解かなければ一定以上の順位・パフォーマンスは取れない
したがって、高難易度の問題を解く練習に集中した方が良い

それを受けて、多くの考察ステップを必要とする高難易度帯（特にレッドコーダー向けの問題たち）に、練習量の約 7 割を注ぐようにしました。その時点である程度上位に入れていたため、「解説を見ずに問題を解く」ことを意識しました。例えば、その時期の「解くのを諦めて解説を見るまでの時間」は基本的に以下のように決めていました*13。もちろんプログラムを実装し AC（正解）を出せたら解説を見ますが、時間がとても長いため、AC を出す前に解説を見た問題はほぼ無かったと思います。

難易度	時間
青色コーダーの半分が解けるレベル（Difficulty ≒ 1800）	考察時間だけで 60 分
黄色コーダーの半分が解けるレベル（Difficulty ≒ 2200）	考察時間だけで 90 分
橙色コーダーの半分が解けるレベル（Difficulty ≒ 2600）	考察時間だけで 150 分
赤色コーダーの半分が解けるレベル（Difficulty ≒ 3000）	考察時間だけで 240 分

なお、Difficulty の値は「半分の人が解けるレーティング」のことを指します。AtCoder Problems というサイトで採用されている基準であり、こちらのリンクで「Show Difficulty」を On にすれば確認することができます。例えば、

AtCoder Grand Contest (AGC) 051 F - rng_58's Last Problem

の Difficulty は 4061 です。

参考～難問練習の利点と欠点～

ちなみにこの練習方法は、AtCoder Beginner Contest (ABC) でレーティングが付く青色コーダー以下の参加者にはあまりお勧めできません。理由としては、以下のことが考えられます。

ABC では、典型的なアルゴリズムやテクニックを扱う問題が多く、非自明な考察ステップを必要とする問題が比較的少ない
- 詳しくは、黄色コーダーになるためのガイドラインを参照
ABC では、制限時間に対して解くべき問題数が多いため、早解き力がレーティングに影響する比重が大きい
- 詳しくは [3-3. 節]を参照

一方、AtCoder Regular Contest (ARC) や AtCoder Grand Contest (AGC) では AtCoder 特有の考察を必要とする問題も多いため、ABC でレーティングが変動しない黄色コーダー以上には特にお勧めできる練習方法だと思います。最近は上位参加者のレベルも上がっていることを考えると、早解き力を鍛えるだけでは橙コーダー到達すら難しいかもしれません。

このような練習を進めていくと、最初は 1 問難しい問題を解くのに数時間かかることも多かったですが、解くのにかかる時間が徐々に短くなっていき、最終的にはコンテスト中でも自分の実力相応以上レベルの問題（当時のコンテストで本番正解者数 50 人以下の問題たち）を解けるようになりました。結果、2018 年 3 月にレッドコーダー（上位約 0.2%）*14となることができました。

しかしながら、私はレッドコーダーになったから終わりではないと思っており、むしろ競プロをやっていく難易度が格段に上がったと思いました。次章では、国際情報オリンピックで金メダルを 3 回取るまでの挑戦の過程について、大会におけるテクニックなどを交えて記したいと思います。

4. 国際情報オリンピックへの挑戦

「レッドコーダーになる」ということは、多くのプログラミングコンテスト参加者の最終的な目標だと思います。しかし、これは人によって考え方が変わる部分だと思いますが、少なくとも私はレッドコーダーはただの通過点であり、到達したら新たな世界が見え、競プロをやる難易度が一層上がるのではないかと思います。ゲームに例えると、一度ステージクリアしたら制限時間・ライフ両方が少なくなるといったような感じでしょうか。

そのうち代表的な理由は「責任感」と「プレッシャー」に尽きます。レッドコーダーは数多くの参加者の憧れの的であるため、それにふさわしい結果を残さなければ恥ずかしいと考えているからです。

4-1. 代表選考で感じた「恥ずかしさ」

話が少し飛びますが、2018 年 3 月、レッドコーダーになったちょうど 1 週間後に、情報オリンピックの春合宿がありました。一応開催 1 週間前になった頃からは情報オリンピックの過去問を本格的に解き始めたのですが、それまで AtCoder を中心に問題演習を行っていたため、情報オリンピックの高難易度問題を解く時間的余裕がありませんでした。そんな状況でしたが、当時「レッドコーダーで情報オリンピックの代表選考に落ちた」という話は聞いたことがなかったので、ほぼ通ると思っていました。

だが、結果は 20 人中 5 位。次点で国際情報オリンピック（IOI）の日本代表選手に選ばれませんでした。その年の IOI が日本開催であったため、特別代表選手として IOI2018 に参加できることになったものの、非常に悔しい結果となりました。しかし、時が経つにつれて、徐々に悔しさより「レッドコーダーでも日本代表選手に選ばれなかったこと」に対する恥ずかしさの方が大きくなっていた気がします。

そこで、何としてでも次の IOI で名誉挽回したいと思い、失敗原因を考えてみたところ、「AtCoder と情報オリンピックの問題傾向が違うこと」が主な原因だと結論付けました。情報オリンピックの春合宿や IOI に出題される問題は、AtCoder と比較して以下のような傾向差があります。

特徴	AtCoder	情報オリンピック
実装量	少ない（基本的に 50 行以下）	非常に多い（200 行以上の実装も*15）
考察量	多い	多い
考察の種類	数学的なものが多い	情報オリンピック特有の考察パターンがある
問題の種類	全部 Batch 形式	Batch・Output Only・Communication など様々
ライブラリ	使用できる	使用できず、全部 1 からコードを書く必要がある

実際、私は AtCoder 対策に集中していた影響で、2018 年時点で情報オリンピック特有の考察パターンに対する理解が薄く、また 150 行を超えるプログラムを実装することにも慣れていなかったため、日本代表選手に選ばれなかったことが分かりました。そこで、特に 2018 年 7 月以降は

情報オリンピック関連の問題を中心に解く
国際情報オリンピック（IOI）・アジア太平洋情報オリンピック（APIO）などの過去問を解く

という練習方法に変えました。

4-2. 国際情報オリンピックへの参加で感じた「責任感」

そこで、短い練習期間だったので効果があったかどうか定かではありませんが、私が初めて参加した国際大会である IOI 2018 では問題の相性が非常に良く、運も重なり、自分の想定以上である金メダル相当の成績を獲得することができました。特別参加選手ながら、大半の日本代表選手に勝つ結果となってしまったのです。

そうすると、次の年の代表選考は 1 位で通過し、年齢的に出場可能である 2019 年・2020 年の国際情報オリンピックでは絶対に金メダルを獲得しなければならないという責任を感じるようになりました。金メダルを獲得した後に銀メダル以下となってしまった例が、日本の IOI 金メダリスト全 16 名中 2 名しかいないことを考えると、極めて自然な考えだと思います。

しかしながら、翌年の代表選考では日本代表にはなれたものの、20 人中 2 位という悔しい結果となりました。失敗原因は以下の通りだと考えていますが、これは今まで全く意識していなかった視点であり、IOI・APIO の過去問演習を行ってもなお偶然身につかなかったスキルだと思います。

いわゆる AtCoder では出題されにくい「高度典型」の知識不足。
情報オリンピック特有の高度なアルゴリズムとデータ構造に慣れていない。
- AtCoder とは違い、特に日本情報オリンピックでは遅延セグメント木・Convex Hull Trick・平衡二分探索木など高度なデータ構造が問われることもある
- また、マージテク・強連結成分分解・Lowlink（橋と関節点）・幾何計算・Monotone Minima・木の重心分解などのマニアックなアルゴリズムが問われることも多い

4-3. 究極的には「苦手を完封すること」

そこで、2019 年春合宿での苦い経験以降、責任感を原動力とし、苦手分野を消すことを常に意識して練習を行うことにしました。特に最初の課題は「高度典型アルゴリズムに慣れる」ことだったので、その課題を対策できる問題を自分で選び解いていきました。

なぜこのような練習方法に至ったのかを説明すると、練習の過程が以下のような感じになり、最終的に苦手分野がなくなった頃には全分野強くなっているのではないかと考えたからです。

苦手分野 A を重点的に対策する

そうすると A が普通の分野になり、次に苦手分野 B を重点的に対策する

そうすると B が普通の分野になり、次に苦手分野 C を重点的に対策する

（以下略）

しかし、その方法を単純に行っただけでは、一度得意になった分野がノータッチに近い状態になり、苦手分野になってしまう可能性があります。そうすると、年々レベルが上がる中高生競技プログラマーの実力についていけず、最終的には銀メダルに落ちてしまうかもしれません。

そこで、練習時間をさらに増やし、[3-3. 節]で紹介したバーチャルコンテストなどを行うことで、あらゆる分野の問題に相当な頻度で、少なくとも概ね 1 カ月に 1 回以上は触れられるように工夫しました。多い日は 1 日 15 時間以上練習したこともありました。また、2020 年 3 月には日本情報オリンピックの過去問をすべて解き切ってしまったように、AtCoder や情報オリンピックの問題だけではバーチャルコンテストや苦手分野演習に使う問題が足りませんでした。そこで、以下のような対策を行いました。

海外コンテストサイトである CodeForces の問題を解いたり、コンテストに出場したりする
例えば以下のような海外の IOI 形式コンテストを、バーチャルコンテストとして解く

戦略面でも苦手を完封する

だが、それだけ対策をしても結果は安定せず、100 回コンテストに参加すれば 15 回程度は失敗するものです。そこで、国際情報オリンピック（IOI）で仮に失敗しても金メダルを獲得できるように、競技中の戦略等にも一工夫行いました。例えば、JOI・IOI では各問題に対して部分点が設定されており、以下の例の通り小さいデータでもある程度の点がもらえるような形式になっています。

の入力データで解ければ点

${N \leq 20}$ の入力データで解ければ点

${N \leq 2000}$ の入力データで解ければ点

$N \leq 10^{5}$ の入力データで解ければ点満点

最初に満点解法の考察や実装に突撃してしまった場合、もし成功すれば金メダルの中でも上位の成績を残すことができますが、失敗すればこの問題の満点が取れないだけでなく、残り時間が少なくなり、ついには他の問題の簡単な部分点すら失ってしまうリスクがあるのです。そこで、バーチャルコンテストなどの成績をもとに熟考した結果、一つの武器である「早解き力」を生かし、取れる部分点から実装していくといった戦略を選びました。

このような練習の結果、3 年連続で金メダルを獲得することができました。特に最初の年は運もありましたが、最終的には苦手をほぼ完封することができ、それが一因となって良い結果に終わることができたのだと思います。このように、自分の興味のあることを全力でやり込んだ結果、その成果がメダルとして現れた時は本当に嬉しかったです。

5. 終章～レッドコーダーとして、何かできる事はないか～

本記事をここまで読んでくださり、ありがとうございます。いよいよ最終章となってまいりました。

さて、私が中学 1 年の時に競プロを始めてから、情報オリンピック・AtCoder・数々の書籍・コンテスト作問者・一緒に戦ってきた参加者や選手などから数えきれない支援を受け、そのおかげでレッドコーダーに到達し、情報オリンピックで 3 度の金メダルを獲得するに至ったと考えています。そこで何か恩返しができないかと思う日々を送っています。

また、プログラミングコンテストで上位に入る実力があれば様々な良い影響を及ぼすことができるにも関わらず、ただ競技に参加しているだけでは周囲や社会に対してあまり利益を生み出せません。そこで、IOI 2018 が行われた頃から、

レッドコーダーという希少な存在だからこそ貢献できることはないのか？

と考え始めるようになりました。

5-1. イベント開催でアルゴリズムへの興味を増やせないか

最初のきっかけは、[4-2. 節]で紹介した IOI 2018 への参加です。この大会では同じ志を持つ選手と同じ会場で戦ったり、競技問題や今までの練習などについて海外選手と話したり、様々な交流を行うことができました。単純に楽しかっただけでなく、プログラミングコンテストに対するモチベーションが大幅に上がった記憶があります。

そこで、国際情報オリンピックに参加できないような中高生に対しても、同じような経験をさせられないかと考え、「パ研合宿」という筑駒パ研初の合宿を 2018 年 12 月に主催しました。特に、合宿で行われたプログラミングコンテストの作題や準備では、AtCoder Beginner Contest 等における作問経験を活かせる形となりました。

また、2019 年には筑駒以外の中高生に対しても「競プロをやっていて楽しい！」と思うような体験をさせたいと思い、募集枠を全国に広げ 50 人規模で開催しました。合宿ではプログラミングコンテストの他、講義や体験企画などを行い、多くの参加者に楽しんでいただきました。その影響で部員数は 10 人から 40 人程度まで増え、競プロ・アルゴリズム・情報科学に興味を持つ中高生を増やせたのではないかと自負しています。

中高生だけでなく一般の方にも競技プログラミングの本当の面白さを知ってもらいたいと思い、2019 年 11 月に GigaCode 2019 というイベントを双子の兄（@square1001）と 2 名で主催しました。オンライン含め 430 名が参加する盛り上がりとなり、少しでも良い影響が与えられていれば嬉しいなと思っています。

5-2. 記事執筆でアルゴリズムや競プロの知見と楽しさを届けたい

しかし、イベント開催だけでは多くの知見を届けられない他、初心者や未経験者にもアルゴリズムやプログラミングコンテストの楽しさを伝えられないといった欠点もあります。そこで、2020 年 1 月に Qiita での記事執筆を始めてみました。

もし読者にとって記事が分かりにくい場合「大半の読者が理解できる記事」にならないと思い、言葉選びや図のデザインなど細かいところまで気を遣いました。その結果、予想を遥かに超える反響が得られ、現在 7600 Contribution（競プロタグ内／アルゴリズムタグ内 2 位）を獲得し、ついには本記事の寄稿までさせていただく状況になりました。

コロナ禍となってしまった今、イベント開催が難しくなっている現状があります。そんな状況下でも、私の書いた記事によって少しでも競プロの知見や面白さが届けられればと思い、今後もこのような活動を続けようかと考えています。

5-3. それでも自分の練習と両立させねばならない

一方、レッドコーダーとしてコンテストで良い成績を取らなければ恥ずかしいです。また、ある程度強くなければ上のような活動は難しくなってしまうと思います。一方、競プロの実力を上げていくためには、かなりの時間を自身の練習に割かなければなりません。

そこで、競プロをやる時間の 4 割を記事執筆や作問活動など他の人に貢献できる活動に割き、残りの 6 割を自らの練習に割くことにしました。だが、6 割では練習できる日数が少し減ってしまうので、効率と時間を少しでも捻出しようと思い、「10 時間バチャ（10 時間ぶっ通しのバーチャルコンテスト）」などで本格的な練習を行いました*16。特に、JOI 春合宿や IOI の 1 カ月前からは、学校で 6 時間授業を受けた後に 10 時間バチャをやることも珍しくありませんでした。

その結果、IOI では 3 回連続で金メダルを獲得することができました。今後もそのような時間配分で自身の実力を上げていきながら、様々な形で競プロのコミュニティや社会に貢献できたらと思います。

6. おわりに

本記事では、競技プログラミング・アルゴリズムの面白さや上達のテクニックなどについて、自身のこれまでの AtCoder・情報オリンピックにおける経験をベースとして書いていきました。この記事が読者の皆さんに少しでも役立っているのであれば、とても嬉しいです。

競技プログラミングは、すぐに思いつく単純なプログラムによる問題解決ではダメで、効率的に動くアルゴリズムを自力で考えなければならないという点に面白さがあります。パズル的な感覚で問題を解くことができて楽しいほか、高度なプログラミング言語関連の知識を必要とせず、初心者向けコンテンツも充実していることから、始める敷居が年々低くなっています。皆さん是非 AtCoder に登録し、競プロを始めてみましょう！

最後に、

競技プログラミングに興味を持ちました！
既に競プロは始めていますが、この記事を読んで、もっと上達したいと思いました！

など感じた方は、[7 章：関連記事・参考書]をお読みください。

これで記事は以上です。（執筆当時）高校生が書いた記事ですので、文章の分かりにくい部分があったかと思いますが、最後までお読みいただきありがとうございました。

7. 関連記事・参考書

競技プログラミングやアルゴリズムの実力アップを目指したいという方のために、参考になりそうな記事や書籍をリストアップしておきます。

競プロ実力アップのための書籍

問題解決力を鍛える！アルゴリズムとデータ構造（通称：けんちょん本）
- AtCoder で出題されるようなアルゴリズム・データ構造が総整理されています
- Qiita 競プロタグ内 1 位のけんちょんさんが執筆した、初学者でも非常に分かりやすい本です
- ただし、高校数学の履修を前提としているため、中学生には理解が難しいかもしれません
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造（通称：螺旋本）
- AIZU ONLINE JUDGE (AOJ) 管理者の渡部有隆教授により執筆されました
- 私がアルゴリズム学習のために最初に用いた書籍です
- ほぼすべての例題が AOJ でジャッジできるため、問題演習がしやすいメリットがあります
プログラミングコンテストチャレンジブック（通称：蟻本）
- 10 年前の競技プログラミング界のレジェンド、秋葉拓哉さんなどにより執筆されました
- 内容が非常に濃密であるため、AtCoder だけでなく ICPC などに出題される高度なアルゴリズムまでカバーしています
- ここで紹介されている 4 つの書籍のうち最も難易度が高いです
アルゴリズム実技検定公式テキスト
- 非常に最近出版された本で、岩下真也さんなどにより執筆されました
- Python の基本文法などから扱っており、初学者でもついていきやすい内容になっています
- ほとんどのアルゴリズム関連本は C++ の知識をベースとしていますが、この書籍では Python のサンプルコードを扱っているため、「Python で競プロをやりたい！」という方におすすめです

アルゴリズムやデータ構造などを学習できるネット上の記事*17

アルゴリズムの概要
- 国立情報学研究所｜アルゴリズムってなんでしょか
- Qiita｜アルゴリズムとは何か？　～文系理系問わず楽しめる精選 6 問～
探索アルゴリズム（全探索、二分探索など）
動的計画法（DP）
グラフ探索（深さ優先探索、幅優先探索など）
- Qiita｜DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜
- Qiita｜BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜
最短経路問題（ダイクストラ法など）
- Qiita｜最短経路問題総特集！！！～BFSから拡張ダイクストラまで～
- Paiza 開発日誌｜最短経路問題で頻出の「ダイクストラ法」とは？練習問題で徹底解説（Java での解説です）
べき乗と逆元の求め方
- Qiita｜「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜
畳み込み・高速フーリエ変換について
- Qiita｜高速フーリエ変換を完全に理解する話
- Qiita｜高速フーリエ変換の実装を難しそうかなと思っている方が、なんだ簡単じゃないですか！！となるための実装講座です

競プロ実力アップのための記事

アルゴリズム記事などをまとめたサイト
- yukicoder｜競技プロ的なアルゴリズムのスライドのまとめ
- AtCoder Clans
競プロ始めたての方のための記事
標準ライブラリで使えるアルゴリズムに関する解説
- Qiita｜厳選！C++ アルゴリズム実装に使える 25 の STL 機能
- AtCoder Library（日本語訳）
AtCoder 特有の数え上げ問題対策
- DEGwer 数え上げテクニック集
情報オリンピックに参加したい人向けの記事
- Qiita｜情報オリンピックへのいざない　～日本一の競技プログラマーを決める戦い～
- JOI 公式教材｜Introduction to JOI（C++ 始めたての参加者用です）
競プロ実力アップのための練習方法について
解くべき演習問題について

*1:そのうち 2018 年は開催国特別参加選手として参加したため、金メダル相当。

*2:正確には $N^{3}$ に比例する回数です。ランダウの {O} 記法を用いて $O(N^{3})$ と書きます。

*3:正確には $N^{2}$ に比例する回数です。ランダウの {O} 記法を用いて $O(N^{2})$ と書きます。

*4:例えば、World Tour Finals 2019 E - e という問題が挙げられます。問題名が 1 文字ですが、コンテスト本番で誰も解けなかった超難問です。

*5:出典はこちらです。

*6:多くの人は C++ を使っています。

*7:例えば AtCoder Programming Guide for Beginners (APG4b) などが挙げられます。

*8:例えば AtCoder Jobs というサイトでは、AtCoder のレーティングに応じて選考が有利になるようなシステムが採用されています。

*9:競技プログラミングにおける実装力に関しては、こちらの記事が参考になると思います。

*10: こちらに公開されています。その時点では相当な実装力が身についていたため、作成にかかった時間は僅か 4 時間程度でした。しかし、中学 1 年の頃は 1 つ作るのに 20 時間以上かかっています。

*11:アルゴリズムを習得した現在ではそうは思っていません。作成のために高度なアルゴリズムが必要となるゲームもあって、例えば AI 対戦のゲームの場合、「AI をどれほど強くできるか」はゲーム作成者のアルゴリズム構築能力に懸かっています。

*12:彼は中学 1 年の時は本選敗退だったが、現在は国際情報オリンピックで銀メダルを 2 度獲得している。数学オリンピックでも優秀賞を獲得している。

*13:レッドコーダーになった後は、橙コーダーの半分が解くレベルの問題は早解きしなければならないため、もう少し時間を短くしています。

*14:2021 年 3 月時点での値です。国内参加者に絞って計算すると、上位約 0.1% となります。

*15:200 行以上の実装を要する問題の具体例としては、[JOI 2017 春合宿 4 日目 - Dragon 2]
(https://atcoder.jp/contests/joisc2017/tasks/joisc2017_l)、[JOI 2021 春合宿 1 日目 - IOI Fever] などが挙げられます。

*16:「決死の十時間バチャ」という題名のついたバーチャルコンテストを行ったことがあります。
例えばリンク 1 ・リンク 2 ・リンク 3 などです。

*17:[1-3. 節]で紹介されている 15 個のアルゴリズム・データ構造のほか、AtCoder Contest Library (ACL) の登場によって重要になりつつあるアルゴリズムに絞っています。