0. はじめに
この記事は 競プロ Advent Calendar 2023 の 8 日目の記事です
こんにちは、keisuke6 です。今週の日曜日にはいよいよ、日本情報オリンピック (JOI) の二次予選が開催されます。そこで少しですが、二次予選のチェックリストを作ってみました。本番前に読んでもらえると嬉しいです。
なお、この記事では「難易度」という言葉がたくさん出てきますが、 AOJ/AtCoder-JOI での難易度を指しています（これは非公式なもので、誰でも参加できる投票によって決まっています1）。
1. 部分点の意識を持つ
JOI 二次予選では、難易度 5, 6 付近の問題で満点を取ることが重要ということ2は多くの人が知っていると思います。そしてそれと同等に重要なことが、部分点を取るということです。
満点と比べると部分点の点数は小さいですが、本選ボーダーである上位 160 人に入るという意味では、この点数は大きな意味を持ちます。
例えば一昨年の二次予選、難易度は 2-5-7-7-9 、ボーダーは 217 点でした。3難易度 5 さえ解ければ残り 17 点で本選に行けます。この 17 点は bit 全探索や set 型など、いずれも難易度 4 程度のテクニックのみで取ることが可能です。
こう見ると、(実力的には) 難易度 5 を取った人は本選に行けたように思えます。しかし実際はそうではなく、難易度 5 を解いた人は 257 人いました。取れた部分点を取らなかった人が 100 人近くもいたということです。
同様のことは、去年の二次予選でも起こっています。難易度は 3-5-7-9-11 、ボーダーは 207 点です。4 難易度 5 さえ取れてしまえば、あとは第 3 問の一次予選レベルの部分点 9 点分を取って本選です。しかしこの回では、難易度 5 を解いた人は 196 人、36 人は部分点を取らずに落ちてしまったのです。
「勝負となる難易度」というのは難易度 5 ですが、最後に勝敗が分れるのは結局それ以降の部分点です。解けても気を抜かずに、最後の問題まで目を通して、取れる部分点をすべて取る意識を持つことを、忘れないでください。
2. 部分点は一つの提出でまとめて取る
JOI2023 二次予選-C の問題を例に説明します。
この問題の小課題 1,2 の解法が分かったとして、「小課題 1 を解くプログラム」と「小課題 2 を解くプログラム」を別々に提出したとします。このとき得られる得点は 9+33=42 点かと思いきや、 33 点しか得ることができません。
JOI 二次予選は AtCoder 上で行われます。そして AtCoder のシステムはそれぞれの問題の得点を、「その問題に出された提出の最大値」として計算します。5そのため、先ほどの場合だと小課題 2 を提出した 33 点の提出のみが見られて、最終得点が 33 点となるのです。
42 点を取る場合は、$H = 1$ であるかの場合分けをして、小課題の処理をまとめて一つのコードで行う必要があります。去年の二次予選で、この関係で点数を落としていた人を Twitter 上で 5 人くらい見かけた記憶があります。細心の注意を払ってください。
3. ライブラリ使用 / 検索は可能
JOI はライブラリや検索を使えないイメージを持っている人も多いかもしれませんが、二次予選では使用することができます。AtCoder Library も使用できます。
4. バーチャルコンテスト
ぶっつけ本番で二次予選に臨むと、当然ながら事故を起こす可能性が高くなります。一度は過去の回に参加して、自分の立てた戦略・ムーブなどを確認しましょう。
また、知っている人も多いと思いますが JOI 二次予選は一昨年の回から通過人数が 80→160 人に増えています。なので、それ以前の回のボーダー点はあまり参考になりません。
5. 諦め半分で臨まない
JOI 二次予選ということで、AtCoder のランキングで国名：日本、誕生年：2006-2011 で検索してみた人は多いと思います。そのランキングによると、レーティングが 800-900 が (あくまで AtCoder では) およそ 上位 160 人のボーダーであることが分かります。
では、茶色コーダーの人は通らないのかというと、そのようなことはありません。難易度 6 は AtCoder の difficulty に変換すると約 800 であると言われています。6そこから推測すると難易度 5 は 600 といったところ、全然解ける難易度です。
先ほども書きましたが、難易度 5 は 200 人程度の人数が通しています。そしてここから、「難易度 5 程度の部分点」を見分けて、取り切る、これができるかで本選に行けるかが決まります。実力的には茶色あれば戦えます。本選に行くという強い意志を持って、部分点を集めてください。
6. 紙を近くに置いておく
- 当日寝坊しないようにアラームなどをかけておく
- 紙を近くに置く
- 開始前にトイレに行ってくる
- 水など飲料を近くに置いておく
- ライブラリをすぐに開ける状態にしておく
- JOI アカウントで AtCoder にログインしていることを確認する
- 自分の精進を信じる
- などなど
7. オーバーフローに気をつける
- long long 型は約 $9 \times {10}^{18}$ までしか数値を管理できない
- 特にグリッドをグラフにするとき範囲外参照に気を付ける
- set 型が空のときに最大値を取るなどしない
- その貪欲、本当にあってますか？
- 全開区間と半開区間はどっちかに統一する
- 小課題の場合分けが合ってるか確認する
- などなど
8. ボーダーは意外と低くなる
例年、それぞれの参加者の人たちが自分の成績をスプレッドシートに書き込むものがあります。7
そこには「ボーダー予想点」という欄もあって、ここに上位 160 人のボーダー点数を予想するのですが、あの欄では 50-100 点程度実際より高い点数が予想されます。ここからも分かるように、人の直感から通らなかったと思うのはメンタルに悪いです。
おわりに
JOI に向けて頑張ってきた人たちが悔いのない結果を残すことの支えに、この記事がなれたら嬉しいです。そしてその人たち全員を自分は応援しています。頑張ってください！