情報オリンピック (JOI) に Scratch で参加しよう！

この記事では日本情報オリンピック (JOI) に Scratch で参加する方法をご紹介します．

なお，筆者は情報オリンピックのスタッフですが，この記事は情報オリンピックに認められたものではありません．

# 情報オリンピックとは

日本情報オリンピック (Japanese Olympiad in Informatics = JOI) は，日本の高校生以下が参加できる**プログラミングコンテスト**です．

名前からしてトップアスリートのようなイメージが湧くかもしれませんが，**完全に名前が悪いです！！！** 情報オリンピックでは裾野を広げることに注力しており，高校の情報Ⅰの授業 (プラス少し問題傾向に慣れておくぐらい) で表彰が受けられるように制度設計されています．

また，**参加料は無料です！！！** 予選では特定の会場がなく，自宅や学校から CBT で参加します．学校の先生が生徒を一括登録することもできます．そのため，参加のハードルがとても低くなっています．

腕試しや自信をつけるのためにぜひ多くの方に参加してもらえると嬉しいです．

https://www.ioi-jp.org/joi/2021/index.html

また，2021 年から「女性部門」(Japanese Olympiad in Informatics for Girls = JOIG) が新設されました．(女子生徒が JOI に申し込むと自動で JOIG にも申し込みが完了しています．一次予選は JOI/JOIG で共通です．)

https://www.ioi-jp.org/joig/2021/

ついでに，情報オリンピックではプログラミングを使わないコンテスト「ビーバーチャレンジ」も実施しています．こちらは授業内でも使ってもらえるようになっていますので，先生方はぜひご検討ください．

http://bebras.eplang.jp/

# Scratch を使うための準備

さて，情報オリンピック予選では Python, JavaScript, Visual Basic, C, C++, Java など 67 のプログラミング言語に対応しています (本記事作成時)．残念ながら Scratch には公式では対応しないのですが，有志による Google Chrome の拡張機能を使うことで，Scratch でも解答できるようになりますので，その方法を紹介します．

まず，下記サイトで拡張機能をインストールしてください．

https://chrome.google.com/webstore/detail/scratchers-atcoder/hackndbjgkehhjinjjoldifbhnfddklh

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/c89d4e4f-d8cf-494c-fc78-a914527cfad7.png)

次に，情報オリンピック予選が開催される Web サイト「AtCoder」にアクセスして，アカウントを作成してください．

注意：情報オリンピック予選は AtCoder 上で開催されるのですが，情報オリンピックに参加するには情報オリンピックに申し込んで与えられた専用アカウントが必要です．今作成するアカウントは Scratch の動作確認と過去問を事前に解く用です．

https://atcoder.jp/register?continue=https%3A%2F%2Fatcoder.jp%2Fcontests%2Farchive%3FratedType%3D0%26category%3D200%26keyword%3D%25E4%25B8%2580%25E6%25AC%25A1%25E4%25BA%2588%25E9%2581%25B8

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/0c2f5c6b-3762-3106-4f2d-fa200c88f41f.png)

(メール通知のチェックはすべて外しても構いません．)

登録が完了したら，そのアカウントでログインし，情報オリンピックの過去問を試しに解いてみましょう．

https://atcoder.jp/contests/archive?ratedType=0&category=200&keyword=%E4%B8%80%E6%AC%A1%E4%BA%88%E9%81%B8

本記事では「JOI 2021/2022 一次予選 (第1回) 過去問」を使います．

# 実際に問題を解いてみよう：問題 A (四則演算)

問題 A「余り (Remainder)」の問題文は次の通りです．

> 正の整数 $X$ が与えられる．$X$ を $21$ で割った余りを出力せよ．

例えば，入力として $50$ が与えられたら $8$ と表示します．どんな整数 $X$ ($1 \leqq X \leqq 100$) に対しても正しい答えを表示するプログラムを提出すれば正解となります．

では，さっそく解答を作成しましょう．画面をスクロールして「Scratch3.0オンラインエディタ」を開きます．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/91cca508-41ce-6b8c-501d-cdf0e184e94e.png)

ここで，Scratch で情報オリンピックの問題を解く場合のルールがいくつかあります．

- 解答ソースコードは Scratch キャットのスプライトの「イベント」内「旗が押されたとき」に実装します．
- 入力を受け取るには「調べる」内「～と聞いて待つ」を使い，更に「すべてのスプライト」の変数のどれかを「答え」にします．
- 問題の答えを出力するには「見た目」内「～と言う」を使います．

このルール通りに問題の解答を作成すると，例えば次のようになります (もちろん，$X$ を $21$ で割った余りを一旦別の変数に保存するなどしても，最終的に出力する答えが合っていれば大丈夫です)．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/e89c8c6c-3794-61b8-b674-38d1ccfc947f.png)


解答が完成したと思ったら，問題文の「入出力例」を使って事前テストをします．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/b29141f8-abc9-d29f-ff41-2e8294a22292.png)

試しに Scratch で旗を押して，入力例 1 の 50 を入力しましょう．すると，猫が 8 と言いましたので，この入出力例は OK です．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/2307e094-6143-27c1-6ce8-89bdd370b09d.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/de2caa52-0e8d-ffea-2972-51150a1b973d.png)

同様に，42 や 5 も入力して，答えが正しいことを確かめましょう．

すべての入出力例に正解して，作成したプログラムが合っていそうだという自信が持てたら，解答を提出します．Scratch で「ファイル」から「コンピュータに保存する」を選びます．適当な場所に一旦保存します．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/a9b7c8d2-de37-0694-e7da-3a636ec269f0.png)

AtCoder の画面に戻って，「Scratch3.0プロジェクトをロード」を押して，先ほど保存した Scratch のファイルを選びます．また，「言語」として「C++ (GCC 9.2.1)」を選びます[^cpp]．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/9c8e7785-2677-24c2-cccb-de2cb2e15ef5.png)

そして，「提出」ボタンを押します．システムが数十種類の入力を試して，自動で採点してくれます (入出力例以外に採点に使用される入力は見ることができません)．

提出結果の画面で少し待って，`AC` と表示されたら正解です．他にも `CE` (文法が間違っている)，`WA` (出力が間違っている)，`TLE` (無限ループ)，`RE` ($0$ で割るなど) が表示される可能性があります．その場合は，デバッグをして再提出しましょう．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/14c3c26e-85ce-e219-aea8-373d04802d94.png)

# 実際に問題を解いてみよう：問題 B (条件分岐)

問題 B「移動 (Moving)」の問題文は次の通りです．

> A 地点から B 地点に移動するのに $X$ 時間，B 地点から C 地点に移動するのに $Y$ 時間かかる．
> A 地点から B 地点を経由して C 地点に移動するとき，$Z$ 時間 $30$ 分以内に移動することができるか判定せよ．
> $Z$ 時間 $30$ 分以内に移動することができるならば $1$ を，そうでない場合は $0$ を出力せよ．

A 地点から B 地点を経由して C 地点に移動するのにかかる時間は $X + Y$ 時間なので，これが $Z$ より大きい ($Z < X + Y$) と時間内に移動できず，答えは $0$ になります．そうでないとき，移動が間に合うので答えは $1$ です．これを Scratch で実装すると次のようになります．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/013658b6-d2bd-9057-4a66-de8c11ddd361.png)

入出力例のテストですが，今回のように入力がいくつかある場合は，「2 をタイプしてエンター，3 をタイプしてエンター，4 をタイプしてエンター」と分けて入力してください．

# 実際に問題を解いてみよう：問題 C (文字列)

問題 C「複雑な文字列 (Complex String)」の問題文は次の通りです．

> 長さ $N$ の文字列 $S$ が与えられる．$S$ の各文字は `A`，`B`，`C`，`D`，`E` のいずれかである．
> $S$ に $3$ 種類以上の文字が出現する場合は `Yes` を，そうでない場合は `No` を出力せよ．

この辺りからどうやって問題を解くか少し頭をひねる必要が出てきます．

例えば，「`A` が出てきた？」「`B` が出てきた？」「`C` が出てきた？」「`D` が出てきた？」「`E` が出てきた？」という変数を作り，Scratch の「～に～が含まれる」の機能を使って各変数を $0$ (含まれない) か $1$ (含まれる) にしましょう．「`A` が出てきた？」+「`B` が出てきた？」+「`C` が出てきた？」+「`D` が出てきた？」+「`E` が出てきた？」が $3$ より小さいなら答えは `No` で，そうでないなら答えは `Yes` です．これを Scratch で実装すると次のようになります (A ~ E は半角で書きましょう)．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/3a67fe89-9065-5f4a-61cf-01f8b2b1c74c.png)

なお，**C 問題まで解いて合計 300 点取ることができれば，敢闘賞の表彰が受けられます！！！**

# 実際に問題を解いてみよう：問題 D (リスト)

問題 D「箱と鍵 (Boxes and Keys)」の問題文は次の通りです．

> ビーバーのビ太郎は，鍵のかかった $N$ 個の宝箱と $M$ 個の鍵を手に入れた．$N$ 個の宝箱には $1$ から $N$ までの番号が付けられており，宝箱 $i$ ($1 \leqq i \leqq N$) には整数 $A_i$ が書かれている．$M$ 個の鍵には $1$ から $M$ までの番号が付けられており，鍵 $j$ ($1 \leqq j \leqq M$) には整数 $B_j$ が書かれている．
> 宝箱 $i$ は整数 $A_i$ が書かれた鍵を使うことで解錠できる．同じ鍵を使って複数の宝箱を解錠してもよい．
> ビ太郎は，できるだけ多くの宝箱を解錠したい．ビ太郎が解錠できる宝箱の個数の最大値を求めよ．

数列 (リスト) が出てきて少しややこしくなりましたが，落ち着いて考えるとそれぞれの箱について対応する鍵が存在するか調べれば良いとわかります．これを Scratch で実装すると次のようになります．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/308246/cb5006e8-fc97-ac5c-1bcb-11a0606821aa.png)

# 当日に向けて

過去問を自分の力で解いてみましょう．JOI 2019/2020，2020/2021 の一次予選は 3 問で，

- 問題 A：条件分岐
- 問題 B：文字列
- 問題 C：リスト

となっていました．JOI 2021/2022 から簡単な方に問題数が増え，

- 問題 A：四則演算
- 問題 B：条件分岐
- 問題 C：文字列
- 問題 D：リスト

となっています．新しい方から問題を解くことをオススメします．

また，一次予選は毎年 3 回 (9 月，10 月，11 月) 実施されています．いずれか 1 度でも 300 点を取ることができれば敢闘賞となります．問題運もあるので，なるべくたくさん出られると良いです．

# 当日のコツ

- 入出力例はすべて試しましょう．
- 間違えてもペナルティは無く何度でも再提出できるので，ためらわず提出しましょう．
- 本の持ち込みだけでなく，インターネット上での検索も認められています．もちろんこのページをコンテストの最中に見返しても構いませんし，それ以外にもわからないことがあったら調べましょう．(誰かと相談することは禁止されています．)

# 便利リンク集

- [公式 情報オリンピックの勉強法](https://www.ioi-jp.org/howtolearn.php)
- [情報オリンピック公式テキスト Introduction to JOI (C++)](https://pro-ktmr.github.io/joig-course/text/)
- [マンガ紹介冊子 その 1](https://www.ioi-jp.org/documents/manga_Challenge_JOI_01v2.pdf)
- [マンガ紹介冊子 その 2](https://www.ioi-jp.org/documents/manga_Challenge_JOI_02.pdf)

# 参考文献

https://qiita.com/sifue/items/1a204e30dd65e88a0314

[^cpp]: 要するに，今回使った Google Chrome の拡張機能は，Scratch のファイルを C++ のソースコードに変換するものです．