JOI参加記～予選落ち青コーダーから本選突破黄コーダーに進化した話～
これは先日行われた第21回情報オリンピック本選までのJOI参加記です。春合宿については後日書くかもしれないし、書かないかもしれません。
第19回情報オリンピック（2019/2020）
当時はまだ競プロ始めて3か月の中学生でした。若かったです。
1次予選は何事もなく通り、2次予選は何事もなく落ちました。まあグラフを知らない時代なので仕方ない。この時は灰色coderでした。
第20回情報オリンピック（2020/2021）
コロナ禍で増えた長期休暇に結構競プロしてたこともあり、この時は青色になってました。そこそこJOI埋めもしていて、何事もなければ本選に行けるかな、と思っていました。
盛大に事故って103点2次予選落ちでした。103点て……。みんな大好きパンケーキで詰まり、満点解法にこだわった挙句Ｂ以降の部分点をほぼ回収できずに終わりました。JOIにおいて部分点は大事です。この時の教訓が今年の本選に活きました。
第21回情報オリンピック（2021/2022）
1年前の大失敗を思い出して震えてましたが、本選枠が倍の160人になったし流石に落ちようがないだろ、と思って参加しました。4完+αで通ったけど、500点が大量にいて戦慄してました。undo可能UFTを知っていますか？僕は知りませんでした……。
さて、本選です。中3の夏に始め2年半弱、最初で最後の本選です。でも上位20人に入れるとは思っていませんでした。本選1日目のガイダンスで春合宿の枠が30人に増えたことを知ったけど、暖色coderが35人いることも知ってビビりました。
最後の本選なので悔いのないようにちゃんと難易度8とか9あたりを埋めて臨もうと思っていました。……思っていたんですが、結局は本選サイトのプラクティスで去年の本選の問題を解いただけでした。有言不実行の人と申します。言い訳はあって（は？）、地学オリンピック2次の対策とか数学オリンピック本選の対策とかしてました。特に数オリは2月11日なので仕方ないですね。もし本選落ちしていたらたぶん悔いていました。
ここから本選当日です。
1日目、開会式とかガイダンスとかがありました。自己紹介の謎掛けが滑らないか戦々恐々としてました。滑ってなかったようなので一安心です。それにしても、Zoomの画面共有は動画がカクカクしまくってて残念だった……（後から動画のリンクが公開されたので助かりましたが）。来年以降の本選参加者はぜひ面白いネタ枠を目指しましょう！
あと、本選の競技時間が2日目の9:00~13:00であることを知りました。知らされるまでは13:00~17:00だと思っていたので危なかったです。
among usをみんなやってましたが、僕は人狼が苦手なので参加できませんでした。や、among usがどれほど人狼に類似してるかは知らないんですが、人との会話が求められるゲームは困ってしまいます。
2日目、競技とか解説とか交流会とかがありました。
僕の学校は寮制で毎朝目覚まし代わりに音楽が大音量で流されるので、絶起の心配はなく、無事に本選競技に参加できました。以下競技中のダイジェストです。
- A問題で100点獲得（00:06:36）
- B問題で100点獲得（00:25:03）
- C問題で23点獲得（01:32:57）
- C問題で5点獲得（01:34:26）
- C問題で5点獲得（02:01:42）
- D問題で27点獲得（02:23:44）
- E問題で9点獲得（03:08:13）
- E問題で10点獲得（03:18:50）
- C問題で33点獲得（03:29:07）
こんな感じでABcde312点で非公式順位表20位でした。部分点の大事さを去年の2次予選で痛感していたので、25分でABを解いたあと、3時間半ずっと部分点回収に勤しんでいました。やっぱり部分点大事。
競技のあとは問題解説やチューター考案の交流会がありました。チューター企画、とても楽しかったです。3,4人チームの対抗戦形式だったのですが、チーム内最弱コードを担当していました。同じチームだった御三方、ごめんなさい……。
そんなこんなで、とっても楽しいJOI本選でした。他の競プロerとオフラインで会うイベントは多分初めてなので春合宿が楽しみです。某ウイルスのせいでオンラインになったら泣きます。
その他
定番のやつを貼ります。
HACK TO THE FUTURE 2021 本選に参加しました
HACK TO THE FUTURE 2021の本選にYouth枠で参加しました！
マラソンの経験/知識はほぼありませんが、8時間フルで頑張れました。上位には全然手が届かなかったですが、8時間＋懇親会はとても楽しかったです。運営してくださった方々、本当にありがとうございました。
予選（11月7日）
文化祭の前日でした。忙しいので参加を見送るつもりだったんですが、やっぱり思い直して参加しました。153,548点の199位で、Youth枠（の多分地方枠）を通過しました。
マラソンに参加するのは3回目（HTTF2020/ヒューリスティック）で、ちゃんと方針を立ててちゃんと正の得点をゲットできたのは初めてでした。
予選～本選
本選が色々な予定（期末試験/地理オリンピック/部活の大会）と被っていたので大変でした。特に期末試験が問題で、何とか公欠できないものか先生に相談してました。結局公欠は許可されなかったので通常の欠席という形で試験を休んで本選に参加しました。
この間にマラソンの勉強をしたほうがいいかな、とも思ったけど結局やらなかったです（そういえばJOI対策もあまり……）。
本選（12月12日）
試験を1科目受けたのちに美術室へ移動して本選に参加しました。その後の試験を欠席しているのでせめて何としてでも正の得点はとるぞ、という気持ちで本選に臨みました。
開始～5時間経過
7個くらいの方針を試しましたが手元/コードテスト環境で1度も正の得点が出なくて焦ります。次の方針も全然浮かばなかったのでとりあえずコードを投げてみます。すると、750,000点くらい貰えました。どの方針がヒットしたのかは分かりませんが、何はともあれ正の得点が出たので安心します。
～7時間経過
何度か提出してみましたが100,000点と少ししかでなかったです。Youtubeの実況を見てたら順位表が凍結する時間になりました。ちなみにこの時点でも手元/コードテスト環境で正の得点は1度も出ていません。
～終了
終了45分前、コードの中でminとmaxを間違えていた箇所を見つけたので直すとようやく正の得点が出ました。感激して投げると1,070,000点でした。やった！
この解法のパラメータをちょこちょこいじって1,670,000点以上まで持っていけました。この時点で残り10分です。
ビジュアライザのことを思い出したので動きを見てみると、貪欲でとれる場所を取り残していることに気が付きました。そこを回収するように直して30秒前に提出、1,920,000点をゲットしてコンテスト終了です。
感想
最終順位は1,927,674点で56人中37位でした。
前半は本当に何も出来なくて焦ったけど、後半は正の得点も出てマラソンを楽しめました。2,000,000点には届かなかったけど自分なりに健闘出来たと思うので満足です。
あと、ノベルティグッズとかご飯とかがとても良かったです。スウェットは着心地いいしマスクも生地がすべすべです。来年も挑戦するつもりですが、マラソンがRated化したらボーダーが跳ね上がりそうです。
最後に改めて、フューチャー及びAtCoderの方々、楽しいコンテストをありがとうございました！
AtCoderで青色になりました。
はじめに
こんにちは、十六夜龍（AtCoder IDは「Izayoi_R」）です。
タイトルのとおり、このたび目標としていたAtCoder青色を達成できたので記念記事を書きました。流れは上述の通りです。
（ところで、色変記事って本当に誰かの役に立っているの？とは少し疑問に思っています。まあ、僕はあくまで自己満足を主目的に書いていますが）
青色になりました
先日（2020/8/15）のABC175にて、念願の青コーダーになりました！
僕の競プロ初参加が2019年9月1日のABC139なので、ギリギリ1年以内に青コーダーになれました。高1の間に青色になりたかったので2重に嬉しいです。
苦節（もう少しで）1年、ついに青コーダーになりました！！！最高です！！！ pic.twitter.com/CgodgUCJD3
— 十六夜 龍 (@Izayoi_R_sakura) 2020年8月15日
ABC175の成績はこんな感じです。
DもEもペナを出さずにきちんと通せて嬉しかったです。
黄パフォをとったのは2回目で、普通のABCでは今回が初めてでした。
水パフォで冷えるレートになったのでまずは青パフォを安定させなければ……。
僕の精進
これこそ必要ない気もしますが、一応現時点での僕の精進具合を載せてみます。
2月末辺りから毎日欠かさず新規ACしているの、ずぼらな自分にしてはわりと頑張っているんじゃないかな、と思います。
僕は学校のある間は学校寮で生活していますが、寮ゆえの制限やこの1学期は新型コロナウイルスの対策の影響もあって競プロをしやすいとは言えない環境でした。深夜帯のCodeforcesは当然参加できず、普段のABCでも寮のスポーツ大会と被って出れないこともありました。
だから尚更「休みで家にいる間に競プロ頑張らなきゃ」という思いもあったので、今回で青色になれたのがとても嬉しいです。
それで精進に関してですが、実を言うとStreakだけ繋いであまり良い精進は出来ていなかったです。Streakの中身の大半は低難易度だし、新しいアルゴリズムやデータ構造も習得できていません（直近では全方位木DP/Rerootingで挫折していますし）。
それでもやっぱりStreakを繋ぐのは良い効果があると思います。精進がレートに現れるのにはタイムラグがある、というのはもうINF回言われていますし、レートが上がり始めたときの伸び幅には精進が関係していそうです。
他に精進に関して言うならば、「くじかつ」に参加しよう！ということです。
バーチャルコンテストに参加しよう！というのもINF回言われている気がします。
ついでにCodeforcesにもぜひ出てみましょう。時間帯は鬼ですがAtCoderよりもコンテスト頻度が高いです。
個人的にはABC埋めが（解説ACを含めて）実力向上の近道のような気はしますが個人差がありそうです。自分の現在の色の難易度帯のAC率をあげて時々1色上の問題に挑戦していれば良いんじゃないでしょうか？
これから
「青色になった！次は黄色目指すぞ！」というほどすぐ次の色を目指せるレベルではないような気がしています。だからレートに関しては現状維持、パフォは青パフォ安定がとりあえずの目標になりそうです。
一応ABCRated最高色に辿り着いたということもあり、ARC/AGCの打率も上げていきたいな、なんて思ったりしています。
自分に関してはこれくらいで、もうちょっと広い目標としては本校に競プロを根付かせたい、というのがあります。そのためにもパソコン甲子園や情報オリンピックで少しでも良い成績を残せるように頑張ります。
さいごに
思ったよりも中身のない記事になりました。もしかするともう二度と色変記事を書ける機会がないかもしれない、と思うと感慨深くなったりならなかったりです。
こどふぉ紫/AtCoder水になりました！
0.はじめに
こんにちは、十六夜 龍です。
5月2日にこどふぉで紫に、AtCoderで水色に色変したので記念に色変記事を書きます。（正直言えば1日に2回色変出来たのが嬉しいので書いています）
こどふぉを知らない/やっていないという人への宣伝も兼ねようと思うので是非読んでください。
1.目次
以下の流れで書いていきます。
2.こどふぉで紫になりました！
既に書くのは5回目となりましたが、先日のDashboard - Codeforces Round #638 (Div. 2) - Codeforcesで紫（candidate master）になりました！嬉しいです、こどふぉ最高です！
紫、素敵な色です。
Codeforces Performanceというスクリプトを用いることでこどふぉでもパフォーマンス推定値を確認できます。
僕のコンテストごとの結果は以下のようになっています。
実は紫パフォはとったことがありません。
直近2回が運よく相性の良い問題だったので紫になれましたが、まだ紫適正の実力を持っているとは言い切れません。
安定して紫パフォをとれるように精進します。
ここから少しこどふぉの宣伝に入ります。既にこどふぉをやっている方は読み飛ばしていただいても構いません。
以下、Q&A方式で説明します。
・「こどふぉ」とは？
Codeforcesというロシア発祥のコンテストサイトです。AtCoderよりも頻繁にコンテストが開催されています。
・どうしておすすめするの？
AtCoderよりも頻繁に、かつ平日にもコンテストがあるからです。やっぱりコンテストがあるとやる気が上がります。
・こどふぉの特徴は？
レートの変動が大きい、Hackやシステムテストというルールがある、Divという概念がある、などいくつかあります。次の記事が分かりやすくまとまっています。
・こどふぉの欠点は？
たまに問題文が難読の回があること、そして開催時間ががっつり深夜帯と厳しめなことです。これは慣れるか頑張るかしないといけないです。
・どうやって始めればいい？
AtCoderみたいに登録するだけです。いきなりコンテストに参加するのではなく、何問か過去問を解いてみて提出形式など慣れておいたほうが良いです。
とにもかくにもまずはCodeforcesにいってみましょう。
3.AtCoderで水色になりました！
AtCoder Beginner Contest 165 - AtCoderでAtCoder水色コーダーとなりました！
rated/unratedの協議の末、無事ratedになりました。AtCoder最高です！
ABC165は問題文不備で直前に開始時刻が延長されたり、E問題のテストケースに制約外の入力があったり、C問題に緑上位diffの問題が出たり、逆にD問題は茶下位diffだったりと色々ありました。
コンテスト終了後、コンテスト時間よりも長く調査・協議してくださったAtCoder社の方々お疲れさまでした、ありがとうございます。
簡単に問題を振り返ってみます。
ABC165の問題のネタバレが含まるので気を付けてください。
a以上b以下の範囲を調べたいときはa-1以下とb以下の範囲をそれぞれ調べて差をみてやると上手くことが多いです。累積和などもこの考え方です。
もちろん全探索でも調べられます。解法に貴賤はありませんが上記の考え方も知っておくと後々役に立ちます。
シミュレーションしていけば答えが出ます。制約が10^18と大きいですがサンプルに10^18があるので親切仕様です。
話題になったC問題です。やることはごくシンプルなDFSですが確かにいつものC問題よりは難しいです。
計算量の目安がつかずに諦めた人も多いそうですね。制約が小さいので頭の中で簡単にイメージしてやると案外候補が少ないことに気づきます。どうせ通るだろ、の気持ちで提出しました。
はい、まさかのO(１)解法かつ茶下位diffの問題です。……僕はCよりDのほうが難しく感じました。実際Dのほうが時間もかかったので。
どんなにヤバそうな問題でも小さい値で全探索/シミュレーションをしてみることが大切です。この問題も適当に値を決めて全部計算したら「B周期である」「周期内では広義単調増加（非減少）」であることが分かります。
unratedになりかけた原因のある問題です。
問題文通りにイメージすると数字がどんどん変わっていて頭がパンクします。（僕だけでしょうか？）
問題文を言い換え（同値変形）することはどんな時も大切です。その言いかえさえできればこの問題の半分は解けた気がします。
LIS（最長増加部分列）を求める問題です。CでもFでもDFSが出ましたね。
僕はAC出来ていませんがポイントは「ある頂点から先を見終わったときに、その頂点の直前の状態にDPテーブルを復元する」ことかな、と思います。
以上、問題の振り返りでした。
今回のABCで思ったのは「もっと全探索を重要視しよう」ということです。
コンピュータが真に人より優れているのは「計算」と「処理速度」です。その「処理速度」に頼る全探索は本来一番自然な考え方です。
そして単なる全探索だと間に合わないから効率化・高速化したのが累積和やDPだと思います。まずは基礎かつ本質たる全探索をおさえましょう。
4.最近の精進について
人によって向いている精進方法やペースは差異があるので一概にいうことは出来ませんが、「精進するほどレートが伸びやすくなる」くらいは言って良いと思います。
その上で参考までに僕の最近の精進をまとめました。
みんなお馴染みAtCoder Problemsです。（お馴染みじゃない、という方はぜひ試してみて下さい。とても便利です。）
もう少しで800ACかつ青色精進ですね。
続いてやはりお馴染みAtCoder Scoresの精進グラフです。
これを見ると2月の最後まで全然精進していないことがばれますね。確か200ACもしていなかったです。
（なぜ突然頑張りだしたのか、それは新型コロナウイルスによって不完全燃焼に終わった定期試験へのやる気をぶつけたからです）
精進を沢山してもすぐにはレートが上がらないことが多いです。
でもしばらくしたらブレイクスルーがやってきます。気長に競プロを続けましょう。
次に最近はやりの精進を紹介します。
AtCoder Problemsから参加できるヴァーチャルコンテストの「よるかつ」です。
参加者も多数おり、楽しく精進できます。
よるかつ終了後に考察を呟いている人もいるので解けなかった問題も復習しやすいです。
よるかつと似たヴァーチャルコンテストとして「あさかつ」もありますが、その時間帯は僕はまだ布団の中でスヤスヤ眠っているので参加したことはありません。
緑になるまでの精進内容はQiitaで書いた色変記事に載っているのでそちらも参考にしてみて下さい。
緑から水色になるまでの間の精進で思ったことを少し書きます。
1つはやはり典型アルゴリズムを知ることの大切さです。
緑までは考察が上手くいけば解ける問題も多かったですが、水色diffになるとあるアルゴリズムを扱えることが前提となることが多くなってきた印象です。
逆にアルゴリズムの知識があればそれを上手く適用して解ける問題が多いので知っているかどうかが分水嶺となりやすいです。
これは実際に水色diff以上の問題をいくつも解いて解説を読んで理解することが一番手っ取り早いでしょう。
もう1つは解く速さについてです。
水色になるには水色パフォーマンスを出す必要がありますが、水色パフォーマンスを出すには水色diffが必ず解ける必要はありません。
灰－茶、茶—緑に比べて緑—水の難易度傾斜は少しきつい気がします。
だから水diffを解くことと並行して緑以下diffを速めに解けるようになることも大切です。
あとはEducational DP Contest - AtCoderのような特化した問題を解いてアルゴリズムを身に着けることも有効そうです。
焦らず1つずつアルゴリズムをものにしていくことが大切です。
まあ、この章の冒頭で述べた通り人によって何が適しているかは千差万別なので各々が自分に必要な精進や知識を考えてみたらそれが一番です。
5.さいごに
「はじめに」があるから「さいごに」もあるだろ、という気持ちでこの章をつくりましたが正直書くことは無いです。
この文章を書いている今日（5月3日）は、このあとにABCとこどふぉがあります。その両方で色落ちして「1日に2回色落ちしました！」という記事を書くようなことにならないことを祈っています。
もし今日色落ちしたら追記でこの下に書き足します。追記が無ければ無事耐えたと思ってください。
それでは、ここまで読んでいただきありがとうございました。
