情報オリンピックへのいざない　～日本一の競技プログラマーを決める戦い～

こんにちは、高校 3 年生の E869120 です。
私は[競技プログラミング](https://qiita.com/sifue/items/d582f3af426f524e5394)が趣味で、[AtCoder](https://atcoder.jp/) や[日本情報オリンピック](https://www.ioi-jp.org/)などに出場しています。ちなみに、2020 年 8 月 2 日現在、AtCoder では日本で 33 人しかいない赤色ランク（レッドコーダー）です。

さて、私は「情報オリンピック」という大会に中学 1 年の頃から 5 年間参加し、青春を捧げてきました。

本記事では、その「情報オリンピック」の紹介、参加方法、そして予選突破までの上達手法について記します。「情報オリンピックとは何か」からサポートしますので、未経験者でも安心してお読みいただけると嬉しいです。


# 1. はじめに
皆さん、「情報オリンピック」という大会をご存知でしょうか。
これは、いわば「プログラミング界のオリンピック」と言って良いでしょう。
![1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/55d4997d-bf0b-374e-f5b2-2c3ce863b140.png)
情報オリンピックは、「プログラミングによる問題解決能力」の腕を競う小中学生・高校生向けの大会です。近年発展している[競技プログラミング](https://qiita.com/sifue/items/d582f3af426f524e5394)の大会の一種で、日本全国から毎年 1000 人以上が参加しています。一方、その大会の面白さやコツを知らずに終わってしまう人も多く、それどころか情報オリンピックという楽しい大会の存在すら知らずに高校生活を終えてしまう人も多いです。

そこで本記事では、

* 情報オリンピックがどのような大会か知ってもらう
* 情報オリンピックで上位に入るためのテクニックを知ってもらう
* 情報オリンピックの本当の面白さを知ってもらう

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

## 対象とする読者層
本記事の主なターゲットは、**プログラミングに興味のある小学生・中学生・高校生**です。情報オリンピックは主に高校生以下を対象としたコンテストであり、その大会の面白さと、上位に入るためのテクニックを知ってもらうのが本記事のゴールであるためです。

しかし、それ以外の方にも是非読んでいただきたいです。理由は、

* 情報オリンピックの面白さは、[AtCoder](https://atcoder.jp/) を含むプログラミングコンテストの面白さと共通するものも多い
* 本記事を読んで、中高生がどのような面白い大会に出場しているのかを知ることができる

と考えるからです。

## 目次
| 章 | 内容 | 備考 |
|:---|:---|:---|
| 1. | [はじめに](https://qiita.com/e869120/items/43181c2084e6e5337ca9#1-はじめに) | |
| 2. | [情報オリンピックとは](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-情報オリンピックとは) | ここからサポートしていきます |
| 3. | [情報オリンピックに参加するメリット](https://qiita.com/e869120/items/43181c2084e6e5337ca9#3-情報オリンピックに参加するメリット) | 大会の面白さを伝えます |
| 4. | [応募方法・参加方法](https://qiita.com/e869120/items/43181c2084e6e5337ca9#4-応募方法参加方法) |  |
| 5. | [情報オリンピックで上位を目指す方法](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-どのようにして高順位を目指すか) | |
| 6. | [自分が情報オリンピックに参加してよかったこと](https://qiita.com/e869120/items/43181c2084e6e5337ca9#6-自分が情報オリンピックに参加してよかったこと) | 本記事のメインです |
| 7. | [おわりに](https://qiita.com/e869120/items/43181c2084e6e5337ca9#7-おわりに) |  |

<br />

# 2. 情報オリンピックとは
まず、本記事で紹介する「情報オリンピック」が一体どのような大会であるか、知りたい方も多いと思います。本章ではそれについて、分かりやすく紹介していきます。

## 2-1. 一体「情報オリンピック」とは何か？
情報オリンピックとは、以下のような大会です。

> 日本情報オリンピック (JOI) は、高等学校 2 年生までの競技プログラマー日本一を決める大会である。（[日本情報オリンピック実施要項](https://www.ioi-jp.org/joi/2020/joi-2021-outline.pdf)から引用）

つまり、小中学生・高校生で誰が一番プログラミングスキルが高いか、競う大会です。もし日本一（正確には日本で 4 位以内）になったら、世界大会である「国際情報オリンピック (IOI)」に招待され、世界で一番を決める大会に出場することができます。

日本情報オリンピックは歴史が浅く、1994 年に始まったものです。しかしながら、2019 年の情報オリンピックには約 1300 人[^1]が参加し、近年急速に人気を伸ばしています。その背景として、科学技術の進歩による IT や人工知能、そしてプログラミング教育の世間からの注目が挙げられます。
![2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/c0ba2720-76d3-a00e-ad14-1b106c08ff40.jpeg)

具体的にはどのような大会なのでしょうか。

#### 情報オリンピックの形式
基本的には、[競技プログラミング](https://qiita.com/sifue/items/d582f3af426f524e5394)の能力を競う大会であり、「プログラミングで解ける問題が何問か出され、制限時間内にできるだけ多くの点数を取った方が勝ち」という**コンテスト形式**をとります。例えば、一次予選であれば 80 分 3 問、二次予選であれば 180 分 5 問、といった感じで時間が決められています。（詳しい話は [2-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-情報オリンピックの競技形式)で後述します。以下の画像はコンテストの例です）
![3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/bc591e74-6d0b-0a96-b1b6-a9b6decc3e88.png)
しかし、「プログラミングで解ける問題」といっても、どんな問題か、ピンと来ない方も多いと思います。そこで、次節ではいくつか例を紹介します。

<br />

## 2-2. まずは簡単な問題から
以下の問題を考えましょう。

> 3 つの整数 $A, B, C$ が与えられます。$A, B, C$ は $1$ または $2$ です。$1$ と $2$ のうち、どちらが多くあるでしょうか。
> 出典：[第 19 回日本情報オリンピック　一次予選 (第1回) 第1問](https://atcoder.jp/contests/joi2020yo1a/tasks/joi2020_yo1a_a)

これはとても簡単な問題で、

* 数値の入力・出力
* [if 文](https://ja.wikipedia.org/wiki/If%E6%96%87)などによる条件分岐

のみが要求されます。あり得る $(A, B, C)$ の組は高々 $8$ 通りしかないので、そのうちどのパターンであるかを条件分岐すれば良いだけです。実際にプログラムを書くと、以下のようになります。

#### C++ でのプログラム例
~~~cpp
#include <iostream>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A == 1 && B == 1 && C == 1) { cout << "1" << endl; }
    if (A == 1 && B == 1 && C == 2) { cout << "1" << endl; }
    if (A == 1 && B == 2 && C == 1) { cout << "1" << endl; }
    if (A == 1 && B == 2 && C == 2) { cout << "2" << endl; }
    if (A == 2 && B == 1 && C == 1) { cout << "1" << endl; }
    if (A == 2 && B == 1 && C == 2) { cout << "2" << endl; }
    if (A == 2 && B == 2 && C == 1) { cout << "2" << endl; }
    if (A == 2 && B == 2 && C == 2) { cout << "2" << endl; }
    return 0;
}
~~~

#### Python でのプログラム例
~~~python
A,B,C = map(int,input().split())
if A == 1 and B == 1 and C == 1: print(1)
if A == 1 and B == 1 and C == 2: print(1)
if A == 1 and B == 2 and C == 1: print(1)
if A == 1 and B == 2 and C == 2: print(2)
if A == 2 and B == 1 and C == 1: print(1)
if A == 2 and B == 1 and C == 2: print(2)
if A == 2 and B == 2 and C == 1: print(2)
if A == 2 and B == 2 and C == 2: print(2)
~~~

しかし、情報オリンピックでは、

* 作問者側の用意したすべてのテストケース

に対して正しい出力をするプログラムを書かなければ点数が入りません。例えば以下のようなコードを書いた場合、$(A, B, C) = (2, 1, 2)$ の場合に正解が $2$ のところを間違って $1$ と出力してしまうので、<font color="red">**不正解**</font>となってしまいます。

~~~cpp
(前略)
if (A == 2 && B == 1 && C == 2) cout << "1" << endl;
(後略)
~~~

このように、情報オリンピックでは**コーディングの正確性**が問われます。

<br />

## 2-3. 少し難しい問題
さて、情報オリンピックでどんな問題が出されるか、分かりましたでしょうか？
では少し問題のレベルを上げていきます。以下の問題を考えましょう。

> $n$ 個の整数 $a_1, a_2, ..., a_n$ が入力として与えられます。
> 
> * $a_1 + a_2 + ... + a_k$
> * $a_2 + a_3 + ... + a_{k+1}$
> * $a_3 + a_4 + ... + a_{k+2}$
> * :
> * $a_{n-k+1} + a_{n-k+2} + ... + a_n$
> 
> の中の最大の値はいくつでしょうか？
> 制約： $1 \leq k \leq n \leq 300000$、$-10000 \leq a_i \leq 10000$
> 出典： [第 6 回日本情報オリンピック 本選第1問](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_a)　を一部改題

### 2-3-1. 単純な解法

* $a_1 + a_2 + ... + a_k$
* $a_2 + a_3 + ... + a_{k+1}$
* $a_3 + a_4 + ... + a_{k+2}$
* :
* $a_{n-k+1} + a_{n-k+2} + ... + a_n$

の値を [for 文](https://ja.wikipedia.org/wiki/For%E6%96%87)などの繰り返し処理を用いて全部そのまま計算してしまうことを考えます。しかし、計算に時間がかかってしまうため、満点が得られません。

基本的に、コンピューターでは 1 秒あたり $10^8$ ～ $10^9$ 回程度の計算を行うことができます。しかし、上述の手法では $n = 300000, k = 150000$ の場合、

$$150001 \times 150000 \fallingdotseq 2.25 \times 10^{10}$$

回程度の計算が必要となり、実行時間制限である 1 秒以内に計算を終えることができません。

### 2-3-2. 工夫した解法
そこで、計算を少し工夫することを考えます。例えば、$b_i = a_1 + a_2 + a_3 + ... + a_i$　とするとき、
$$a_l + a_{l+1} + a_{l+2} + ... + a_r = b_r - b_{l-1}$$
となります。例えば、下図のように　$a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]$ の場合は、$a_4 + a_5 + a_6 + a_7 = b_7 - b_3 = 17$ となります。
![4.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/5bbc861b-cb72-d35d-407d-f467ff49bf52.jpeg)
そうすると、$b_i$ を前計算することで $a_1 + a_2 + ... + a_k$ などの値がたった $2$ 回の計算で求められます。したがって、実行時間制限である 1 秒以内に計算を終えることができます。

一応、C++ でのプログラムの例を載せておきます。
※必ず読まなくても、本記事を読める構成になっております。

#### C++ でのプログラム例
~~~cpp
#include <iostream>
using namespace std;

int N, K;
int A[100009];
int B[100009];

int main() {
    // 入力
    cin >> N >> K;
    for (int i = 1; i <= N; i++) { cin >> A[i]; }
    for (int i = 1; i <= N; i++) { B[i] = B[i - 1] + A[i]; }

    // それぞれの値を計算
    int Answer = -1000000000;
    for (int i = K; i <= N; i++) {
        int L = i - K + 1, R = i;
        int val = B[R] - B[L - 1];
        Answer = max(Answer, val);
    }
    
    // 出力
    cout << Answer << endl;
    return 0;
}
~~~

このように、

* コーディングの正確性　　だけでなく、
* **現実的な実行時間に間に合わせるようなプログラムの書き方（アルゴリズム）を考える**

ということが、情報オリンピックの本質です。情報オリンピックの世界は広く、今回紹介した問題はまだ簡単な部類に入ります。例えば、[この問題](https://www.ioi-jp.org/camp/2018/2018-sp-tasks/day4/candies.pdf)のような更に難しい問題も出題されます。

<br />

## 2-4. 面白い問題が出題されることもある
情報オリンピックでは、算数パズルのような面白い問題も出題されることがあります。
例えば、以下の問題を考えましょう。

> 縦に $N$ 行、横に $N$ 列のマス目から成るタイルがある。あなたは、以下のような形式で、すべてのマスが埋め尽くされるまでタイルを塗る。
> 
> 1. 最も外側の周を<font color="#FF0000">**赤色**</font>で塗る。
> 2. 次に外側の周を<font color="#0000FF">**青色**</font>で塗る。
> 3. 次に外側の周を<font color="#CCCC00">**黄色**</font>で塗る。
> 4. 次に外側の周を<font color="#FF0000">**赤色**</font>で塗る。
> 5. 次に外側の周を<font color="#0000FF">**青色**</font>で塗る。
> 6. ...（以下略）
> 
> そのとき、上から $x$ 番目、左から $y$ 番目のマスはどの色で塗られるか？
> 制約：$1 \leq N \leq 10^{10}$、$1 \leq x, y \leq N$
> 出典：[第 10 回日本情報オリンピック 予選第3問](https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c) を一部改題

問題に関する補足ですが、例えば $N=11$ の場合は以下のようにタイルが塗られます。
![5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/73ed23c7-4569-baa6-748e-d493139b82c8.png)
この問題は面白いので、読者への課題としておきます。これを解けば予選で上位 30% に入れるくらいの難易度なので、解けなくても全く問題ありません。ご安心ください。（解法は脚注参照[^2]）

---

さて、[2-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-情報オリンピックの競技形式)以降では、情報オリンピックの試験形式と特徴について紹介します。ここまでに紹介した 3 問が全く分からなくても理解できる内容ですので、続きも是非お読みください。

<br />

## 2-5. 情報オリンピックの競技形式
[2-1. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-1-一体情報オリンピックとは何か)で紹介した通り、一次予選に応募した 1300 人の参加者から、国際情報オリンピック (IOI) に出場する 4 人を選出するのが、日本情報オリンピックの目的の一つです。そこで、以下の通りの選抜競技が行われます。

| 競技名 | 参加者数 | 競技日程 (2020) | 競技時間 | 問題数 |
|:---:|:---:|:---:|:---:|:---:|
| 一次予選 | 約 1300 名 | 第一回：2020/9/18 (土)<br /> 第二回：2020/10/17 (日) <br /> 第三回：2020/11/21 (土) | 80 分 | 3 問 |
| 二次予選 | 約 800 名 | 2020/12/13 | 3 時間 | 5 問 |
| 本選 | 約 90 名 | 2021/2/13、2/14 | 4 時間 | 5 問 |
| 春合宿 | 約 20 名 | 2021/3/19～3/24 | 5 時間 × 4 日 | 3 問 |
　
次に、各競技の形式・特徴について紹介します。

---

### 2-5-1. 一次予選
一次予選は、情報オリンピックの最初の段階です。[AtCoder 社](https://atcoder.jp/)のジャッジシステム（プログラムの正誤判定システム）を利用し、自宅や学校などで 1 人 1 台の PC を使って、オンラインで競技に参加する形式を取ります。Twitter などの SNS を用いて他人とやり取りすることはできませんが、**競技時間中にインターネットで記事を検索したり、本で調べたりすることは可能です。**

試験時間は 80 分で、問題は 3 問です。問題は概ね難易度順に並べられており、2 問正解すれば二次予選に進めます。約 40% の選手がこの段階で落とされますが、以下の技能があれば二次予選に進出できるので、決して難しいことではありません。（[2-3. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-3-少し難しい問題)、[2-4. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-4-面白い問題が出題されることもある)で紹介したような難問を解く必要はありません）

* if 文などの条件分岐を含む基本的なプログラムを書くことができる
* for 文などの単純な繰り返し処理を含む基本的なプログラムを書くことができる
* 問題文の通りにシミュレーションを行うことができる

---

### 2-5-2. 二次予選
二次予選も一次予選と同様に、[AtCoder 社](https://atcoder.jp)のジャッジシステムを利用し、オンラインで競技に参加する形式を取ります。また、競技時間中にインターネットで記事を検索したりすることは可能です。

試験時間は 180 分で、問題は 5 問です。問題は概ね難易度順に並べられていますが、一次予選とは異なり**相対評価**で本選進出者が決まります。一次予選より難しい問題が出題され、例えば [2-3. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-3-少し難しい問題)や [2-4. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-4-面白い問題が出題されることもある)で紹介した問題が、二次予選の 1～2 問目に相当します。したがって、正確にコーディングする能力だけでなく、**高速に答えを求められる効率的なプログラムを書く能力（アルゴリズム構築能力）**が求められます。

二次予選は難関で、一次予選を通過した選手の約 90% がこの段階で落とされます。しかし、二次予選を通過すれば「高度なアルゴリズムが扱える人材」として認められ、[情報科学の達人](https://www.nii.ac.jp/news/2020/0114.html)などの研究プログラムに参加できるなどの大きな利点があります。

---

### 2-5-3. 本選
予選とは異なり、首都圏（例年は[つくば市](https://ja.wikipedia.org/wiki/%E3%81%A4%E3%81%8F%E3%81%B0%E5%B8%82)）の会場で 1 泊 2 日の合宿形式で競技が行われます。90 人が同じ会場で競技を行うので、本番ならではの緊張感を感じることができます。また、同じ目標を目指す選手達と交流することができるので、とても楽しいです。

試験時間は 4 時間で、5 問が概ね難易度順に並べられています。難関であった[二次予選](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-2-二次予選)よりも遥かに難しい問題が出題されます。上位約 20 名が春季トレーニング合宿に進出できますが、そのためには<font color="#CCCC00">**黄色コーダー**</font>相当（AtCoder で上位 1%[^3]）またはそれ以上のレベルが必要です。
![6.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/cde8989d-310e-ecbd-77c1-4209a8be15c0.png)
（[情報オリンピックのページ](https://www.ioi-jp.org/joi/2020/index.html)より引用）

---

### 2-5-4. 春季トレーニング合宿（春合宿）
[国際情報オリンピック](https://ja.wikipedia.org/wiki/%E5%9B%BD%E9%9A%9B%E6%83%85%E5%A0%B1%E3%82%AA%E3%83%AA%E3%83%B3%E3%83%94%E3%83%83%E3%82%AF)日本代表を決めるための最終選抜です。首都圏の会場で、1 週間程度の合宿形式で行われます。

1 日 5 時間 3 問の試験を 4 日間行うことで、上位 4 名を選抜します。出題される問題は超難問揃いです。20 人中 4 人、つまり約 20% が国際情報オリンピックに進出するので、一見[二次予選](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-2-二次予選)より楽に見えますが、実際は競プロに青春を捧げてきた実力者ばかりが参加するので、通過は限りなく厳しいです。筆者もこの段階で 3 度落とされ、4 度目にしてようやく国際情報オリンピック日本代表に選出されました。

---

このような選考フローで、国際情報オリンピックの代表選手が選ばれます。

<br />

## 2-6. 情報オリンピックの 5 つの特徴
本章の最後に、他の科学オリンピック（[数学オリンピック](https://ja.wikipedia.org/wiki/%E6%97%A5%E6%9C%AC%E6%95%B0%E5%AD%A6%E3%82%AA%E3%83%AA%E3%83%B3%E3%83%94%E3%83%83%E3%82%AF)など）や [AtCoder](https://atcoder.jp/) などとは違った、情報オリンピックならではの特徴を紹介します。

### 2-6-1. 自動採点
数学オリンピックや大学受験などでは、競技が終わった後に採点が行われます。一方、情報オリンピックでは「プログラムを提出するとすぐに正誤が採点される」という、**自動採点システム**が取られます。

プログラムをジャッジシステムに提出すると、**通常約 60 秒以内に正解か不正解かが分かります。**これも情報オリンピックの競技としての面白さの 1 つです。[^4]
![8.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/e0c7f755-5fee-1706-da0a-18867cbfd739.jpeg)

### 2-6-2. 部分点の存在
情報オリンピックは [AtCoder](https://atcoder.jp/) などのプログラミングコンテストとは異なり、各問題に対して「正解か不正解か」だけでは判定されません。[二次予選](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-2-二次予選)以降では、プログラムの実行速度などを考慮して、各問題について $0$ 点から $100$ 点までの間で点数が付けられるのです。

たとえば、$n \leq 100000$ という制約が付いた問題があったとしましょう。この場合は $n^2$ 回程度の計算回数を要するプログラムは実行時間制限である 1 秒に間に合わず、<font color="red">不正解</font>となってしまいます。しかし、$0$ 点になるとは限りません。

> $n \leq 1000$ を満たすテストケース全てに正解した場合、$30$ 点が与えられる。

という部分点があった場合は、そのプログラムは $30$ 点となります。（$n=1000$ でも $10^6$ 回程度の計算回数となり、PC では 1 秒あたり $10^8$ ～ $10^9$ 回程度の計算ができるので、十分余裕を持って間に合います）

### 2-6-3. 戦略の重要性
[2-6-2. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-6-2-部分点の存在)では、情報オリンピックに部分点システムがあることを記しました。これが主な理由で、情報オリンピックを戦うにあたっては「アルゴリズム構築能力」だけでなく「戦略要素」も重要になってきます。

たとえば、

* 制限時間内に部分点を狙うか、それともリスクを取って満点を狙うか
* 次の問題にいつ進むか

などといった場面で、正しい戦略の選択が求められます。

### 2-6-4. 実用的な問題が多く出される
基本的に、情報オリンピックで出題される問題は、実用的なものが多いです。過去には、

* できるだけ疲労度が少なくなるように、サッカーの片付けをする方法を組む問題
* できるだけ金がかからないように、新型ウイルスの治療計画を組む問題

などが出題されました。このような問題では、解けた時に「プログラムを使えばこんな実社会の問題も解けるのか」と思い、世界が広がります。これも情報オリンピックの面白さの 1 つです。

### 2-6-5. 現地で行われるコンテストがある
情報オリンピックの[本選](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-3-本選)、[春季トレーニング合宿](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-4-春季トレーニング合宿春合宿)では、全選手が一箇所に集まり、同じ会場で競技を行います。したがって、

* 同じ目標を持つ選手と交流できる
* 普段はオンライン上の活動がほとんどである「プログラミングコンテスト」に対するモチベーションの維持、あるいはモチベーションの向上に繋がる

という側面があり、とても楽しいです。

---

以上で 2 章は終わりです。この章は長かったですが、お疲れさまでした。
3 章以降では、情報オリンピックに参加する利点、そして参加方法と上達方法についての話を展開します。

<br />

# 3. 情報オリンピックに参加するメリット
情報オリンピックについて知っていただいたところで、その大会が如何に面白いかを紹介します。情報オリンピックという大会は、とても面白く、青春をかけるに値するものなのです。

## 3-1. プログラミング能力を磨くきっかけになる！
情報オリンピックでは、

* 自分が扱うプログラミング言語を使えること
* プログラムを早く正確に書くこと

が求められます。したがって、情報オリンピックで上位を目指すのであれば、プログラミングスキルを磨くために過去問を解いたり、沢山のソースコードを書いたりしなければなりません。

しかし、その過程で自然とプログラミング能力が磨かれ、2020 年に約 37 万人が不足すると予測される中[^5]、社会の求める人材に近づいていくことができます。

実際に、情報オリンピックで入賞するような人は、[2-2. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-2-まずは簡単な問題から)で紹介した簡単な例題を解くプログラムを 30 秒以内、[2-3. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-3-少し難しい問題)や [2-4. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-4-面白い問題が出題されることもある)で紹介した難しい例題を解くプログラムを 2 分以内で書ける人も多いです。練習すれば、その程度までプログラミング能力が上がるのです。


## 3-2. アルゴリズムを学ぶきっかけになる！
[2 章](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-情報オリンピックとは)で述べた通り、情報オリンピックでは

* 「ただコードを速く正確に書く能力」　　だけでなく、
* 「実行時間に間に合うような、効率的に動くプログラムを書く」

ことも求められます。そこで、様々な[アルゴリズム](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)を学習すると、効率的に動くプログラムが書きやすくなり、上位に入れます。したがって、情報オリンピックへの参加は、アルゴリズムの学習・復習をする良い機会になるのです。


## 3-3. 「実績」が作れる！
情報オリンピックに参加すると、

> 第 19 回日本情報オリンピック　本選出場

などといった実績が付きます。**二次予選進出以上**で賞状も獲得できるので、比較的簡単に実績が作れます。そのため、[大学受験の推薦入試](https://shingaku.mynavi.jp/cnt/etc/column/step6/recommendation/)や[就職活動](https://ja.wikipedia.org/wiki/%E5%B0%B1%E8%81%B7%E6%B4%BB%E5%8B%95)などに有利に働くことがあります。


## 3-4. 無料で参加できてお得！
情報オリンピックは、多くのスポーツ大会や、[数学オリンピック](https://ja.wikipedia.org/wiki/%E6%97%A5%E6%9C%AC%E6%95%B0%E5%AD%A6%E3%82%AA%E3%83%AA%E3%83%B3%E3%83%94%E3%83%83%E3%82%AF)などの他の競技科学の大会とは異なり、**無料**で参加できます。以下の表の通り、予選・本選などすべての段階で無料です。（交通費等も支給されます）

| 大会 | 料金 |
|:---:|:---:|
| 一次予選 | 0 円 |
| 二次予選 | 0 円 |
| 本選 | 0 円 |
| 春季トレーニング合宿 | 0 円 |
| 国際情報オリンピック | 0 円 |

したがって、もし成績上位者にランクインできた場合、無料で本選会場へ行けたり、無料で他のライバルと戦えたり、無料で講義を受けたりすることができ、とてもお得です。

## 3-5. 競技として楽しめる！
情報オリンピックは、[運動オリンピック](https://ja.wikipedia.org/wiki/%E8%BF%91%E4%BB%A3%E3%82%AA%E3%83%AA%E3%83%B3%E3%83%94%E3%83%83%E3%82%AF)と同じく競技です。そのため、競技が好き、あるいは人と競争することが好きな小中学生や高校生には特にお勧めです。

また、競技では共に戦うライバルと一緒に、練習では切磋琢磨して実力を伸ばしていく場合も多いです。したがって、情報オリンピックの競技で勝つと相当な達成感が得られます。
![10.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/406ff49e-5e04-8c47-b44f-e076ce3795a5.png)


## 3-6. 世界観が広がる！
情報オリンピックの本選などに参加することによって、青春をその大会にかけてきた「実力者」たちと交流する機会が作れます。そこで強い人と知り合うことで、実力者の存在を身近に感じることができ、「自分は本選行ったから強いと思ってたけど、中には大変な実力者もいるのか…」などと痛感させられます。そうすると、「そのような実力者に一歩近づく」という新たな目標ができ、世界観が広がります。

現地で会わなくても、オンラインでそのような体験をする場合もあります。例えば、情報オリンピック参加者の多くは [Twitter](https://twitter.com) という SNS を利用しており、

* 初学者が分からないところを質問すると、実力者が丁寧に答えてくれる
* 実力者がコンテストの感想をツイートする

といった場面で、実力者の強さを痛感させられる場合もあります。

## 3-7. 実社会の問題が解けて面白い！
実社会に応用できる問題が解けた場合、「こういう場面で高度なアルゴリズムが使えるのか…」と心を動かされることもあります。例えば私の場合、[最短経路問題](https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C)（下図の Google Maps 経路検索のように、スタート地点から目的地までの最短経路を求める問題）の解法を理解したときは、かなり感動しました。

また、[2-6-4. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-6-4-実用的な問題が多く出される)で紹介した通り、情報オリンピックの問題は実用的なものが多いです。

したがって、競技問題や過去問を解いている時に、アルゴリズムが面白いと感じ、感動することも多いと思います。これが情報オリンピックに参加するメリットの 1 つです。
![9.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/73fcb176-d496-eeba-4455-99d0966008bd.png)

<br />

# 4. 応募方法・参加方法
情報オリンピックの楽しさ、面白さは分かりましたでしょうか？

では、今日から早速「日本情報オリンピック」に応募してみましょう。本章では、大会への応募方法、そして参加方法について記します。

なお、大学生以上で、情報オリンピックに参加する予定のない読者は本章を読み飛ばし、[5 章](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-%E3%81%A9%E3%81%AE%E3%82%88%E3%81%86%E3%81%AB%E3%81%97%E3%81%A6%E9%AB%98%E9%A0%86%E4%BD%8D%E3%82%92%E7%9B%AE%E6%8C%87%E3%81%99%E3%81%8B)に進んでいただいて構いません。

## 4-1. 「一次予選」への応募方法
情報オリンピック参加への最初のステップは**一次予選に応募すること**です。本節では、応募方法について分かりやすく、ステップごとに解説したいと思います。

#### 1. 日本情報オリンピックのページへアクセスする
まず、[日本情報オリンピック公式ホームページ（https://www.ioi-jp.org/）](https://www.ioi-jp.org/) にアクセスしてみましょう。そうすると、以下の画面が表示されると思います。
![11.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/ff8d1b36-e4c9-dc0e-9e78-20f94e1e471e.png)

#### 2. 参加登録ボタンをクリックする
次に、画面を下に少しスクロールすると、「予選への参加登録」という赤いボタンが表示されます。そのボタンをクリックして、予選参加登録に進んでください。
![12.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/9c613fad-e050-2c43-d585-1eca25a5d05a.png)

#### 3. 「個人申込」をクリックする
ボタンをクリックすると、申込画面が表示されると思います。そこで「個人申込」「一括申込」の 2 つの選択肢が表示されますが、ほとんどの参加者は個人で申し込むと思うので、個人申込の「申込入力フォーム」をクリックしてください。
![13.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/f7bb73ba-8243-ab42-df34-f3ab09d91565.png)

#### 4. 事前承諾事項に同意する
次に、事前承諾事項のページが表示されるので、それをしっかり読んだうえで「同意する」にチェックを付け、「参加登録者のメールアドレス入力へ」ボタンをクリックしてください。そうすると、登録画面に進みます。

#### 5. メールアドレスを登録する
自分のメールアドレスを登録してください。入れる欄と確認用の欄があるので、同じメールアドレスを入れてください。その後、右下の「メールアドレスの登録」ボタンを押してください。
![14.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/b0f5dbe8-d7e8-ccce-4dca-8afe959e7516.png)

#### 6. メールアドレスを確認する
登録を終えると、「メールアドレス登録を受け付けました。」と表示されます。その後、1 分くらい経つと登録されたアドレスに以下のようなメールが届くと思うので、リンクをクリックして、残りの参加登録に進んでください。
![15.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/2df617da-cb87-f486-971e-ae5ed4ed245c.png)

#### 7. 参加申し込み情報を入力する
「参加申込者情報の入力」というページが表示されるので、以下の情報を入力してください。

* 氏名
* 生年月日
* 性別
* マイページログインパスワード

入力し終わったら、右下の「学校情報入力へ」ボタンを押し、次の段階に進んでください。
![16.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/057f229b-c15e-09bd-2270-7eb552b41a21.png)

#### 8. 学校情報を入力する
次に、「学校情報の入力」というページが表示されるので、指定された通りに入力してください。学校名については、「学校種別」を入力すると「学校検索」というボタンが出てくると思うので、それをクリックした上で入力してください。最後に「入力内容確認へ」というボタンがあるので、それを押してください。
![17.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/7103095c-adb4-0b45-33eb-56690b8727fe.png)

#### 9. 入力内容の確認
最後に、「入力内容の確認」というページが表示されます。入力内容がすべて一致しているかどうか確認し、問題ない場合は「上記、入力内容を確認しました」にチェックを入れ、「上記、入力内容で登録する」ボタンをクリックしてください。

#### 10. 登録完了
これで登録完了です。お疲れさまでした。登録したメールアドレスに、ログイン URL とログイン ID が書かれたメールが送られてくると思うので、確認してください。

また、**絶対に登録したパスワードを忘れてはいけません。**もし忘れてしまった場合、予選に参加できなくなる可能性があるので注意してください。

<br />

## 4-2. 「一次予選」への参加方法
皆さん、一次予選への登録は済みましたでしょうか？
次に、「一次予選」にどうやって参加すれば良いのかを解説します。

#### 1. 情報オリンピックのページにアクセスする
参加登録したときと同様に、[日本情報オリンピック公式ホームページ（https://www.ioi-jp.org/）](https://www.ioi-jp.org/)にアクセスしてください。

#### 2. 「マイページログイン」ボタンをクリックする
参加登録時と同様に、画面を少し下にスクロールしてください。そうすると、「マイページログイン」という黄色いボタンが表示されると思うので、それをクリックしてください。
![18.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/166ecec8-3925-0324-be9e-a4aca6238608.png)

#### 3. ログインをする
ログイン ID とパスワードを正確に入力して、ログインしてください。
なお、ログイン ID は参加登録完了時に届いたメールから確認することができます。

#### 4. 「予選競技システムの確認」をする
ログイン後、下図のような画面が表示されると思います。マイページメニューには、

* 申込内容の確認・変更
* 予選競技システムの確認

の 2 つのリンクがありますが、そのうち「予選競技システムの確認」の方をクリックしてください。
![19.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/0fd00fa9-a751-198e-dbb9-f4a1f3c26f9a.png)

#### 5. 競技 URL をクリックする
次に、「予選競技システム」という画面が表示されると思います。競技がかなり前の場合は URL などが空のままですが、2020 年の場合、

* 「プラクティス URL」は 2020/9/7 12:00 に
* 「競技 URL」は各競技が近くなったら

確認できるはずです。URL をクリックすると、コンテストページ（競技会場）へ行くことができます。
![20.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/f4eb702a-7a9d-8cd6-a96f-5e9d81dca8ff.png)

#### 6. 最後に AtCoder システムの使い方を確認しましょう
一次予選・二次予選は AtCoder のシステムを利用して行います。ですので、

* AtCoder でのソースコード提出方法
* AtCoder での提出結果（正誤／得点）の確認方法

などに慣れておく必要があります。AtCoder の使い方に慣れるためには、次の記事を読むと良いです。

* [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)

<br />

## 4-3. 「二次予選」以降の参加方法
次に、二次予選以降の参加方法について紹介します。これは一次予選の応募／参加に比べれば簡単です。

#### 二次予選
<font color="red">これ以降は、前の段階（例えば二次予選の場合一次予選）を通過していなければ競技に参加することができないので、ご注意ください。</font>
一次予選参加方法と同じような要領で、マイページにログインしてから「予選競技システム」ページにアクセスします。その後、二次予選の競技 URL をクリックすれば、コンテストページ（競技会場）に行くことができます。

#### 本選
晴れて二次予選を通過した場合、競技の数日後に「JOI 本選への招待状」というメールが来ると思います。そのメールに従って、参加申込書などを情報オリンピック事務局に郵送してください。

<br />

## 4-4. 諸注意
最後に、情報オリンピックへの応募・参加について、いくつか注意点があるので、まとめておきます。過去には「参加しようと思ったけど、以下の注意事項を守らなかったため参加できなかった」という選手もいるので、ご注意ください。

#### 注意点 1：期限内の登録が必要
参加登録期限は「最後の一次予選の 2 日前の 23:00」です。例えば 2020 年の場合、2020/11/19 23:00 が最終登録期限になります。それを過ぎると参加できません。ただし変更される場合もあるので、[情報オリンピックのページ](https://www.ioi-jp.org/)をよく確認するようにしてください。

#### 注意点 2：一次予選免除者も登録が必要
昨年の情報オリンピックで優秀な成績を残すなど、一次予選が免除になっている選手についても、二次予選参加のために登録が必要です。**登録期限は通常の場合と同じ**であり、例えば 2020 年の場合 2020/11/19 23:00 です。

#### 注意点 3：パスワードを忘れないこと
もしパスワードを忘れてしまった場合、一次予選／二次予選に参加することができません。
折角の機会が無駄になってしまうので、パスワードは絶対に忘れないようにしてください。

---

皆さん、情報オリンピック予選の応募方法／参加方法について分かりましたでしょうか。

情報オリンピックは、無料で参加できる、とても楽しい競技科学の大会です。IT やプログラミング教育の世間からの注目の伸びとともに、現在人気が増えている大会の一つでもあります。5 章では、そのような大会で高順位を目指し、本選進出を狙うためにやるべきことや、身に付けるべきテクニックを記します。

<br />

# 5. どのようにして高順位を目指すか？
情報オリンピックに参加する皆さんの多くは、ここまで読んで以下のような疑問を感じたと思います。

> 情報オリンピックの面白さ、そして参加方法は分かったが、どうやって情報オリンピックで良い成績が取れるようになるでしょうか。。。

そこで、5 章では**情報オリンピック本選進出までのガイドライン**を記します。

* どのような練習方法で一次予選／二次予選を突破できるか
* どのようなスキルや戦略を身に付ければ良いのか

を中心に、全部で 8 個のステップにまとめました。本章では、以下の通りに 1 ステップごとに解説します。なお、AtCoder など他のプログラミングコンテストでの戦い方と共通する部分もあるので、大学生以上で情報オリンピックに出場しない読者も是非お読みください。

| 節 | 内容 |
|:---:|:---:|
| 5-1. 節から 5-2. 節 | 一次予選突破の手法 |
| 5-3. 節から 5-8. 節 | 二次予選突破の手法 |

## 5-1. プログラミング言語を習得する！
情報オリンピックで戦うためには、プログラムを書けなければ何も始まりません。したがって、プログラミング始めたての人が最初にやるべきことは、**プログラミング言語の理解と習得**です。

### C++ のススメ
そこでお勧めするのが C++ というプログラミング言語です。これは理由があります。情報オリンピックの各選抜では、次表の通りのプログラミング言語が利用できます。

| 選抜 | 使える言語 |
|:---:|:---:|
| 一次予選 | たくさん（50 種類以上） |
| 二次予選 | たくさん（50 種類以上） |
| 本選 | C・C++ |
| 春季トレーニング合宿 | C・C++ |

**本選以降では、C か C++ しか使えないのです。**また、C++ は [5-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-5-精選-100-問で基本的なアルゴリズムを使えるようにする)で紹介する便利な「STL 機能（標準ライブラリ）」が存在するため、C 言語利用者より C++ 利用者の方が圧倒的に多いのです。これが、情報オリンピックを目指す初学者が C++ を勉強すべき理由です。

### 高度な知識まで身に付ける必要はない
さて、プログラミング言語に関する知識はどのレベルまで身に付ける必要があるのでしょうか。実は、それほど高度な知識は要求されません。基本的に、以下の 7 つを含むプログラムを書けるようになれば、情報オリンピック一次予選では十分です。（二次予選突破のためには [STL 機能](https://qiita.com/e869120/items/518297c6816adb67f9a5)を学習する必要がありますが、これは [5-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-5-精選-100-問で基本的なアルゴリズムを使えるようにする)で後述します。）

* 入力、出力
* 代入、単純な四則演算（<code>+</code>、<code>-</code>、<code>*</code>、<code>/</code>、<code>=</code> など）
* 条件分岐（if 文など）
* 繰り返し処理（for 文など）
* 文字列（string）
* 浮動小数点（double 型など）
* 配列（二次元配列を含む）

そのような知識を学ぶために、

* [AOJ の Introduction to Programming I](http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=ITP1)

というコースがあるので、それを利用して学習することを勧めます。全部で 44 問ありますが、ITP1-1_A から ITP1-10_D までの 40 問を解くことを推奨します。
![21.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/fedc9a30-ec12-c533-4fd9-e8abeafe131a.png)

<br />

## 5-2. AtCoder の過去問で基本的なスキルを習得する！
プログラミング言語の基礎を習得できた次は、**プログラムを正確に書けるようになること**が重要です。そのスキルを身に付けるためには、

* AtCoder の簡単な過去問を使って練習すること

をお勧めします。

### そもそも AtCoder って何？
AtCoder とは、毎週末にプログラミングコンテストを開催するジャッジシステムです。その中には 3000 以上の過去問が揃っており、簡単な問題も多く、初心者にとって始めやすい設計となっています。AtCoder の始め方について知りたい方は、

* [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)

をご覧ください。

### どの問題を解けば良いのか？
AtCoder には、基本的に 3 種類のコンテストがあります。

| コンテスト名 | 難易度 | 問題数 |
|:---:|:---:|:---:|
| AtCoder Beginner Contest (ABC) | 初心者・中級者向け | 6 問[^6] |
| AtCoder Regular Contest (ARC) | 上級者向け | 6 問 |
| AtCoder Grand Contest (AGC) | 最上級者向け | 6 問 |

その中で、AtCoder Beginner Contest の A, B 問題を 30 問ずつ解くことを目標にすると良いです。解いているうちに、自然と「プログラムを書くこと」に慣れてくると思います。なお、AtCoder の過去問は、

* [AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)

という便利なサイトがあるので、それを活用することを推奨します。過去問が表で整理されている、ユーザー ID を入力すると解いたかどうかの情報が簡単にわかる、などのメリットがあります。
![22.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/8d8ec683-3910-96d6-45d2-24eeb86eeac4.png)

---

ここまでやれば、一次予選は突破でき、次の段階に進めると思います。5-3. 節以降では、難関である二次予選をどう突破するか、ガイドラインを示したいと思います。

<br />

## 5-3. 情報オリンピックの過去問を解いてみる！
まずは難しいアルゴリズムの習得、と思うかもしれませんが、最初にやるべきことは**情報オリンピックの過去問を解くこと**です。

過去問には、簡単なものから非常に難しいものまでが並んでおり、非公式ですが 1 ～ 12 までの難易度が付いています。以下は難易度の目安ですが、5-2. 節で AtCoder Beginner Contest の A, B 問題を解けるようになったら、**難易度 1 ～ 3（余裕のある人は 1 ～ 4）を解いてみると良いです。**

| 選抜 | おおよその難易度 |
|:---:|:---:|
| 一次予選 | 1 ～ 3 |
| 二次予選 | 4 ～ 9 |
| 本選 | 5 ～ 11 |
| 春季トレーニング合宿 | 10 ～ 12 |

そこで、過去問を解くときに利用できる便利なサイトがあります。

* [AOJ/AtCoder-JOI](https://joi.goodbaton.com/)

過去問が難易度別に整理されている、ユーザー ID を入力すると解いたかどうかの情報が簡単にわかる、などのメリットがあるため、利用することを推奨します。
![23.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/7ca656c3-b3eb-2eac-9af0-01ba2c33659f.png)

<br />

## 5-4. コンテストに参加する！
情報オリンピックの過去問のうち簡単な問題が解けるようになったら、本番のコンテスト形式に慣れるために、**実際にコンテストに出場してみる**ことをお勧めします。

### AtCoder のススメ
世界には様々なプログラミングコンテストが存在しますが、お勧めするのは [5-2. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-2-atcoder-の過去問で基本的なスキルを習得する)で紹介した [AtCoder](https://atcoder.jp/) です。毎週末の 21:00 から定期的にコンテストが開催されています。

* 問題文が日本語なので、気軽に参加できる
* 毎週コンテストがあるため、モチベーションを保ちやすい

などといったメリットがあります。
![24.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/cabf4be1-0a89-bc8c-fcde-4ecb8c0ed67c.png)

### 夜遅くて参加できない人は
AtCoder のコンテスト終了時刻は 23:00 頃になることが多く、小中学生や高校生にとっては夜が遅すぎるかもしれません。そこで、コンテストに参加できない方は、**バーチャル参加システム**を利用することを推奨します。

競技終了後に AtCoder のコンテストページにアクセスすると、コンテストタイトルの下に「バーチャル参加」というボタンが追加されると思います。それをクリックすると設定画面に移りますが、時間を設定すると「バーチャル参加」をすることができます。開始時間になったら、過去問を解くのと同じような感じで問題を解いていってください。「バーチャル順位表」にあなたの結果がリアルタイムで表示されます。
![25.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/473da08b-0a1a-0f74-1b1b-d1e6e64b7eb2.png)

<br />

## 5-5. 「精選 100 問」で基本的なアルゴリズムを使えるようにする！
AtCoder のコンテスト形式に慣れたら、情報オリンピックで戦う武器になる[「アルゴリズム」](http://research.nii.ac.jp/~uno/algo_3.htm)を習得していきましょう。基本的に、情報オリンピック二次予選を突破するために必要なアルゴリズムは、以下の 11 個です。

| | | | |
|:----|:----|:----|:----|
| 全探索 | 二分探索 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
| 動的計画法 (DP) | ダイクストラ法 | ワーシャルフロイド法 | クラスカル法 |
| 高速な素数判定法[^7] | べき乗の高速計算手法[^7] | 累積和 |  |

この 11 個のアルゴリズムは、

* [レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 2-2-2. 節](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-2-2-12-%E5%80%8B%E3%81%AE%E5%9F%BA%E6%9C%AC%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E3%83%9E%E3%82%B9%E3%82%BF%E3%83%BC%E3%81%99%E3%82%8B)

で学習することができます。また、「精選 100 問」という、11 個のアルゴリズムが使えるようになるために最適な問題集が用意されているので、それを利用しても良いです。

* [「精選 100 問」のリンク](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)

また、アルゴリズムを C++ で実装するためには [queue](https://qiita.com/e869120/items/518297c6816adb67f9a5#3-13-queue) や [sort](https://qiita.com/e869120/items/518297c6816adb67f9a5#3-10-%E3%82%BD%E3%83%BC%E3%83%88-sort) などの「STL 機能（標準ライブラリ）」の習得が必要になることがありますが、以下の記事で学習することができます。

* [厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】](https://qiita.com/e869120/items/518297c6816adb67f9a5)
* [厳選！C++ アルゴリズム実装に使える 25 の STL 機能【後編】](https://qiita.com/e869120/items/702ca1c1ed6ff6770257)

<br />

## 5-6. 最後に情報オリンピックの高難易度に手を出す！
基本的なアルゴリズムを習得し、そしてこれを使いこなせるようになったら、情報オリンピックの問題に戻ってみるといいでしょう。その頃には、[5-3. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-3-情報オリンピックの過去問を解いてみる)で解いた難易度 3 は簡単に感じ、中には難易度 4 や 5 でも難しくないと感じる人もいるかもしれません。

ここまでたどり着いた人は、難易度 6 まで全部解くことをお勧めします。情報オリンピックには特有の傾向があり、過去問を解くことが一番の近道です。難易度 6 の問題のほとんどは [5-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#5-5-精選-100-問で基本的なアルゴリズムを使えるようにする)で紹介した 11 個のアルゴリズムとその応用で解くことができますが、各選抜の通過難易度は次表の通りで、その難易度の正解率を打率 7-8 割に上げるだけで二次予選を高確率で突破できるのです。

| 選抜名 | 通過目安 |
|:---:|:---:|
| 一次予選 | 難易度 2 が解ける |
| 二次予選 | 難易度 6 が 7-8 割解ける |
| 本選 | 難易度 8 が 7-8 割解ける |
| 春季トレーニング合宿 | 難易度 11 が 5 割解ける |

#### いつ解説を見るべきか
情報オリンピックの問題は教育的な良問が多いので、分からなくても長時間考えるのが重要です。考えても分からない場合、部分点が誘導になっている可能性もあるので、それをヒントにしても良いです。

ただ、あまり時間をかけすぎても効率が悪いので、以下の時間が経過しても解き方が分からない場合は解説を見ることをお勧めします。

| 難易度 | 3 | 4 | 5 | 6 | 7 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 時間 | 10 分 | 30 分 | 60 分 | 120 分 | 180 分 |

なお、解説は[こちらのページ](https://www.ioi-jp.org/problem_archive.php)から閲覧することができます。

<br />

## 5-7. 「情報オリンピック特有の戦略」を練る！
[2-6-3. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-6-3-戦略の重要性)で述べた通り、情報オリンピックで戦うにあたっては、戦略がとても重要になります。なぜなら**部分点**があるからです。例えば、

1. 最初の 3 問を速く解いたが、4 問目の満点解法に集中した結果時間内に解けず、300 点を取った人
2. 最初の 3 問を解くのは遅かったが、終了直前に満点解法を諦めて簡単な 4 問目の部分点を取り、320 点を取った人

で比べると、2. の方が順位が高くなるのです。したがって、**いつ部分点を取りに行くか**はとても重要になります。

### お勧めの戦略
「解法を思いつくのが苦手」「プログラムを実装するのが苦手」など、人それぞれ傾向が違うので、最適な戦略はコンテストに出たり過去問を解いたりすることによって自分で見つけるのが一番ですが、多くの選手に通用する「お勧め戦略」の例を一つ示しておきます。（以下、二次予選の場合の戦略です）

* 基本的に、前から順番に問題を解く。
* 後ろの問題の方が簡単な場合[^8]もあるので、ある問題が分からなくても、一応すべての問題を読んでおく。
* 終了 1 時間 15 分前までは、満点解法に集中する。
* その時点で解法が思いついていない場合は、部分点を集めることに集中する。
* 解法が思いついて解けそうな場合は終了 30 分前まで粘るが、「自分の考えている解法が間違っている」「実装が非常に長くなってしまう」などの可能性もあるので、終了 30 分前になったら部分点を集めることに集中する。

<br />

## 5-8. その他読んでおくべき資料
本章の最後に、情報オリンピックで本選出場、あるいはそれ以上の成績を目指している人にとってお勧めの書籍や記事を紹介します。

#### 書籍（1 つ目）
最初に紹介するのは、会津大学の准教授[^9]である渡部先生によって書かれた本です。内容が比較的易しく、初心者でも楽しんで読める内容になっています。例題が [AIZU ONLINE JUDGE](http://judge.u-aizu.ac.jp/onlinejudge/index.jsp) に載っているので、安心感があります。

* [プログラミングコンテスト攻略のためのアルゴリズムとデータ構造](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86-ebook/dp/B00U5MVXZO)

#### 書籍（2 つ目）
次に紹介するのは、「競技プログラミング界のバイブル」とも言われている、以下の書籍です。最初に紹介した本より難易度が高いですが、2012 年に秋葉さん・岩田さん・北川さんによって執筆されました。現在は競技プログラミングや情報オリンピックで戦うための参考書という域を超え、世界的なアルゴリズム教科書の 1 つと言える立ち位置までになっています。

* [プログラミングコンテストチャレンジブック（通称：蟻本）](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068)

#### インターネット上の記事
最後に紹介するのは、アルゴリズム解説がとても詳しくまとめられている記事たちです。全部で約 50 個の記事が存在し、色々なアルゴリズムが丁寧に学習できます。本を買う必要がないので、無料で学習できるのも利点の一つです。

* [drken さんの記事](https://qiita.com/drken)

---

ここまでしっかりやれば、少なくとも「二次予選に通過できるかどうかのボーダー付近」には達すると思います。[2-5. 節](https://qiita.com/e869120/items/43181c2084e6e5337ca9#2-5-情報オリンピックの競技形式)で述べた通り二次予選は難関ですが、それゆえ突破したときの達成感はとてつもなく大きいです。また、本選に進出した場合は大きな実績となり、「高度なアルゴリズムを扱える人材」として認められます。この記事を読んで「情報オリンピックに参加したい！」と思ったら、本選進出を目指して練習するのも良いでしょう。
![26.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/6a9b0282-b351-3fa2-74d1-f62fbc6ae136.png)

<br />

# 6. 自分が情報オリンピックに参加してよかったこと
私は中学 1 年の頃から 5 年間、情報オリンピックで戦うことに青春を捧げてきました。その結果、[第 31 回国際情報オリンピック（アゼルバイジャン大会）](https://ioi2019.az/)で金メダルを獲得することができましたが、その中には多くの努力と挫折がありました。

最終章では、自分が情報オリンピックに参加して良かったこと、そして本記事で最も伝えたかったことを 3 点に分けて記します。

## 6-1. 実力者を身近に感じたこと
中学 1 年の時の、情報オリンピック本選での話です。情報オリンピックに向けた練習はオンラインでの活動が中心であり、その時初めて「同じ会場に集まって戦う」という体験をしました。

本選では、当時は雲の上の存在だと思っていた、レッドコーダーを含む実力者と交流する機会がありました。そこで私は実力者の強さを痛感した一方で、今まで狭いと思っていた世界が一気に広がりました。その結果として、ライバルに近づくといった目標や、具体的な将来の夢がはっきりしました。これが情報オリンピックに参加して良かったなと思ったことの一つです。

<br />

## 6-2. 「挫折から学ぶこと」の重要性を知ったこと
中学 3 年の時の、情報オリンピック春合宿での話です。私は中学 1 年の頃から春季トレーニング合宿（上位 20 名）に出場していたこともあり、流石に 4 位以内は大丈夫だろうと過信していましたが、

* 以前に比べて、最上位層のレベルが上がったこと

などの背景があり、<font color="blue">5 位（次点）</font>で落選しました。これが情報オリンピックで戦ってきた中で味わった「最大の挫折」でした。一時は「永遠に代表になれずに終わるのではないか」と思いましたが、そこで考え方を変えて、「なぜ失敗したのか」分析してみることにしました。

その結果、自分は「解法は思いつくけど、200 行を超えるような長いプログラムの実装に慣れていない」「高度な典型知識を問う問題に弱い」ことがわかりました。その後、失敗したコンテストを分析し、弱点を克服する練習を積み重ねた結果、高校 1 年の時に初めて 4 位以内に入り、高校 2 年の時は国際情報オリンピックで金メダルを獲得しました。

このように、情報オリンピックで戦うことで、「挫折から学ぶことの重要性」を知りました。人生において挫折は辛いですが、失敗こそ今後の自分を成長させてくれる材料になると思っています。また、この考え方は人生の様々な場面に通用すると思うので、情報オリンピックに参加して良かったなと思いました。
<br />

## 6-3. 「最後まで諦めないこと」の重要性を知ったこと
高校 2 年の時の、世界大会（国際情報オリンピック）での話です。私はずっと、<font color="#CCCC00">**金メダル**</font>（参加者約 300 人中 30 人弱しか取れない）を目標にして練習してきました。

世界大会の競技は 2 日間かけて行われ、その合計点で順位が決まるのですが、1 日目では少し失敗し、金メダルを取れるかどうかのボーダー付近にいました。2 日目の前半は好調だったのですが、最後に取り掛かった 1 問でプログラムをバグらせ、正解がなかなか出ませんでした。

しかし競技終了 3 分前、最後まで諦めずバグを探し続けた結果、ついにバグの原因が分かりました。急いでソースコードを修正し、終了 1 分前に再びプログラムを提出したところ、その点数のお陰で金メダルを獲得することができました。そして同時に、最後まで自分の可能性を信じてめげずに戦うことの大切さを痛感させられました。

このように、情報オリンピックで戦うことで、「最後まで諦めないことの重要性」を知りました。この考え方は競技に限らず、試験や就職など人生の様々な場面で通用すると思うので、情報オリンピックを経験して学べた重要なことの一つだったと思います。
![27.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/09787b4b-df78-31fb-78a0-48e81150a972.png)

<br />

# 7. おわりに
情報オリンピックは、青春をかける価値のある面白い大会です。始めるのはとても簡単ですが、「日本一の競技プログラマー」になるのはとても難しいことです。しかし、上に向かって努力していく過程はそれ自体とても楽しく、将来役に立つものでもあるのです。

最後に、興味を持った方は、楽しい「情報オリンピック」に是非参加しましょう。

本記事によって、少しでも「情報オリンピックが面白い！」「小中学生・高校生に情報オリンピックを勧めたい！」と感じる人が増えてくれれば、とても嬉しい気持ちです。

これで記事は以上です。高校生が書いた記事ですので、文章が分かりづらかったかもしれませんが、最後までお読みいただきありがとうございました。


[^1]: 詳しくは[こちらのページ](https://www.ioi-jp.org/joi.php)をご覧ください。
[^2]: $D = min(x, y, N+1-x, N+1-y)$ とすると、$D$ 回目でマス $(x, y)$ が塗られることがわかるので、$D$ の値が $3$ で割って $1$ 余るなら赤色、$2$ 余るなら青色、$0$ 余るなら黄色で塗られます。
[^3]: 2020 年 8 月 2 日時点で、日本国内の全参加者に対する黄色コーダー以上の割合です。
[^4]: [AtCoder](https://atcoder.jp/) を含む、多くのプログラミングコンテストを行うサイトでは、このような形式が取られています。
[^5]: 詳しくは[こちらの記事](https://xtech.nikkei.com/it/atcl/news/16/061101700/)をご覧ください
[^6]: 2019 年 4 月までは 4 問でした。
[^7]: 現時点で、予選問題にこのようなアルゴリズムを利用する問題は出題されていませんが、近年予選問題の傾向が変化しつつあり、出題される可能性も十分に考えられます。
[^8]: 「難易度逆転」という現象です。過去には、[第 17 回日本情報オリンピック予選](https://www.ioi-jp.org/joi/2017/2018-yo/index.html)などで発生しています。
[^9]: 2020 年 8 月 2 日時点です。