セミファイナルまでいくには？ JOI2025/2026参加記
セミファイナルまでいくには？ JOI2025/2026 参加記
この度は...この度は？
今回は、情報オリンピックに参加した参加記を書きます。
他の参加者が書いていたので流れで急遽書きます
基本的にその場その場のノリで書くので、適当な点が多いと思いますが...
JOI参加記とは言ったものの、今回のJOIで競プロに関しては、一つの区切りということでついでに今までの私の競技プログラミング人生(6か月)を振り返っておこうと思います。
どのように勉強すれば、JOIの二次予選を突破できるかの参考になれば幸いです。
ちなみに、記事の一番最後の布教が書きたくてやっているのでぜひ見てほしいです。
競プロには全く関係ないです。
自己紹介
ドルトン東京学園 高校2年
競プロ歴としては、2025年の8月に始めたので、約半年となります。
現在緑コーダー。なんか10月から1mmも成長してない気がするんですよね...
競プロを始めたわけ
競技プログラミングを始めた...というより、プログラミング自体はかなり古く、幼少期から親の影響で行っていました。そのためある程度プログラミング言語に親しめていたこと、アルゴリズムに対しても多少理解があったためかなり最初のスタートダッシュはよかったとは思います
...????
そう言い切っていいのかはわからなさそうですね...まあ、初回だし...
でもまあ、そのあとは少しずつ成長していきました。
成長過程
とりあえず、最初のほうはモチベがあったのでいろいろやっていました。以下に簡潔にやっていたことをまとめます。
1.とにかくいろいろ解く
典型90問とか、普通に過去問を解いたりしていました
典型90問に関しては、難易度順とかじゃなくてなぜか番号順でやっていました。問題の解き方を身に着けるというより、典型知識を身に着けるためにやっていました。
2.蟻本を読む
この時期の学ぶ際、特に道標はこれでした。いろいろなアルゴリズムを学んだりしていって、1~2か月で最後まで何とか読み切りました。
3.バチャしまくる
形式に慣れるため、ついでに問題を解くのに毎日ABCのバーチャル参加をしてました。今思えばどこにそのモチベがあったんですかね...
4.毎日日記をつける
その日解いた問題についてとか、今後のモチベとかを書き連ねていました。ほかにもアルゴリズムをメモしたり、典型90問も解くたびにまとめていました。Obsidianは良い。
正直言って、典型90問は最初のうちは緑~水程度までやれば問題ないと思います。ここで、灰色であろうが何だろうがそのくらいは最低でもやってもいいと思います。典型は問題を解けるか、というよりそのレベルの人ならわかるアルゴリズム！っていうのを学ぶものだと思っています。実際、黄色まで全部やっていましたし意外と記憶に残っています。
日記に関しても、続くうちは後で見返して自分の頑張りを認められたりと、メリットは大きいと思います(途中でめっきり書かなくなりましたが...)
典型90問に関しては、1次予選が始まる前に一応全部の問題を理解して、自分なりの解説を書くまではしました。
正直、ここにあることをただひたすら繰り返して、1次予選は余裕でいける程度になったのだと思います。
それから、テンプレート？の整理も行いました。いろいろな簡単なことを一発でできるマクロとかをまとめてあげることにしました。
おかげさまで現在では2万byteくらいが標準の提出コードです。ですが、利点もあってこのおかげでかなり提出速度が速いと感じています。実際速度ではABCのスコア予測で最初のほうは青が出ます(でも、水diff~青diffが全然解けない...)
全く参考になるとは思いませんが、一応これを載せておきます。template.cppのmain関数にメインのコードを書き、ライブラリなどは下の貼り付けスペースに持ってくるという形式です。もともとライブラリなんてフォルダはなくて、すべてのデータ構造がtemplate.cppに収まっていたのですが、さすがに量が多くてごちゃついてきたのでこのような形式に落ち着きました。
個人的にこだわった点としては、超有能なdebug君と#include __FILE__でmain()を上で記述できるようにしたことです。謎のブログとChatGPTに感謝を表します。
ChatGPTといろいろ相談しながら、自分だけのこういうテンプレートを作ると意外と楽しいですし、コード記述の速度もだいぶ上がります(可読性は地に落ちますが)
JOI1次予選
特にいうことがないですね...まあ、最初に比べて成長はしていたので嬉しかったです。
2次予選までの精進
えっと、ほとんどさぼっていました...たまにJOI二次予選~本選の過去問を見たり、定期的にABCの問題を見たりしていました。でも、ABCには毎回欠かさずに参加していました。特にこれといって気にしたことはないですね...むしろ1次予選前が一番頑張っていた気がします。日記も途切れているし...
それと、確かこのあたりで初めてAHCに参加しました。正直なところAHCに参加して一番思ったのは、AIすごいな～です。
JOI2次予選
そんな感じでグダグダしているうちに、二次予選になってしまいました...とりあえず、当日どのような所感だったのか、振り返りも含めてまとめておきます。
A問題はさらっと解きました。ABCのB~Cくらいのイメージでしたね。結構問題そのままで実装したイメージがあります。
B問題は...なぜか知りませんが、ずっと問題を誤読して、2マス先まで取れると勘違いして30分以上溶かしました。誤読に気づいた後は5分程度で実装が終わりました...
C問題は、問題を見てすぐにああ、そういう...って感じになったので10分程度で終わりました。まあ、結構そのまま圧縮とかすればうまくいった印象があります...
D問題は、何とかしてクーポンの枚数kに対しての最小値を出す関数を思いつけたためにうまくいきました。max(0,a[i])どこかで出会っていたために、解けました。
しかしながら...なんですかねこれは。二分探索が苦手だからってコードがひどすぎる。
まあ、解ければいいんです！！！
E問題は、そのまま雑にグラフを構築してBFSしてあげれば、部分点は問題なさそうという感じで解きました。でも、そのあと少し考察すれば満点だったのが悔しい...(偶奇でグラフを分けていたから、これをあと少し改良するだけ)
F問題は、なぜか知りませんが美しさを最小化する問題と誤読したらしいです。そりゃ常に1でいいやん...
全体的に終わった後に思ったこととしては、誤読がひどいということですね。また、二分探索に関してはこりゃだめだと思い、そのあと評価関数を入れたらそれを満たす最大のxを返す関数をテンプレートとして用意しました。今ではかなり重宝しています。
セミファイナルまでの精進
えっと...正直これもまたさぼっていました。とはいっても、さすがにセミファイナルに出れたということで意外と頑張ってはいました。いろいろなJOI本選の過去問、特に難易度7~9を解いていました。
ABCにも継続的に出たり、でもリアルでも忙しいことがいろいろとあったのでほどほどに競プロに取り組んでおりました。
セミファイナル
そうこうして適当に過ごしているうちに、セミファイナル当日となってしまいました。ここ半年で頑張った成果を出し切る時、ということでかなり緊張しておりました。
結果からいいますと、
パッとしない成績でした笑
A問題、問題を見て、とりあえずいろいろと悩む。少しの観察で、あるマス一つを固定してもう一マスを固定してあげれば問題はなさそう、という結論を得る。しかしながら、もう一マスをクエリ的に高速に処理する方法に悩まされる。適当な考察で、あり得る範囲のうち端の隣のマスだけは無理！という適当な考察のまま突っ走ってしまい、30分程度犠牲に。1次予選から何も反省していない...何とか適当なケースを突っ込むことで間違いに気づく。気づいた後は早く、適当に偶数ごとと奇数ごとでまとめてセグ木で殴る。累積とかの考察は嫌い...
B問題、トイレに行ったら考察が下りてきて、5分程度で実装が終了。適当な客の区間の左側がクエリの区間より右にあれば追加されず、逆に左にいることが必要条件。そして、客の区間の右側が、クエリの区間が来るより前に来ていたら追加されない。つまりは、クエリの区間の右側より左にある客の区間の左側をすべて足して、そのあとクエリの区間の左側より左にある客の区間の右側をすべて足す、で十分行けるという考察にたどり着く。そしたら後は、またセグ木でぶん殴る。適当に2本はやしたが、条件などには最大限注意を払って実装した。
C問題、何も思いつかなかったので、とりあえずN=3くらいは全探索。
D~E問題、ずっと見ていたのに何も思いつかなくて結局部分点すら取れない。Dの小課題、これで通ると思ったのだが...
A問題に関しては、本当に中途半端なところで実装し始めるのが悪癖と痛感しました。
B問題に関しては...よく思いついたって感じです。
C問題に関しては、競技終了後めちゃくちゃ悔しかったですね。でもbitsetによる部分和問題解決に関してあまり詳しくなかったので多分厳しかったです。ずっとInverse Problem on Subset sumsで調べてたんですが、難しい論文しか出てこなかった...
確かに63に引っかかるところはあったんですが、そもそも1 2 4 8...の発想が出てこなかったので負けですね。普通にこれは思いつくべきでした...
D問題に関しては、まったくもって方針が思いつきませんでした。小課題3(スターグラフの場合)については、上記のコードで行けると思ったんですがね...結局わからずじまいであきらめてしまいました。
E問題に関しては、操作がプリム法で、常にMSTになるからその辺以外は無視していいまではわかりましたが、そのあと部分点の取り方すらわからなかった。Q=1に固執しすぎたのが敗因かな...
競プロ人生の振り返り(途中経過)
競プロを通して、とりあえずアルゴリズムの奥深さやAHCを通じて最適化問題の面白さについて学び、やはり将来はIT系の仕事を行いたいという風に思うようになりました。そういった意味で、競プロというのは私の人生に今後大きな影響を与えるものだと思います。とても興味深いものでしたし、同じコミュニティの人々はみなすごい人や頭いい人ばかりでいろいろな刺激を受けられたことも楽しかったです。
ただ、正直もっと時間をかけて競プロに取り組んでおけばもしかしたら、ファイナルまでいけたんじゃないかなという思いもあります。ですが、少しでも競プロに触れて、JOIセミファイナルまでいけたことはとても貴重な経験でした。
終わりに
最後に、私が言いたいのは、もしもあなたが競プロを始めたいな～？と思っている人であればとりあえずなんか手を動かそうぜ！ってことです。人間って不思議なもので、思っている以上に手を動かさないとやる気が出ないですし、逆に手を動かしたら思っている以上にやる気が出てくるんです。それを証明するのがこの記事で、書き始めたら1時間で5000字くらい書いていました。
これらが同時に、かつハイレベルに要求されるこの競プロというものは実に奥が深いと思います。私はそこまで言えるほど強くはないですが、興味がある人はぜひこの世界に足を踏み入れてほしいです。そして、もう踏み入れている人はこれからも手を動かし続けましょう！私もまだ、競プロは続けていきたいと思っています。
話がずいぶん大きくなったようにも感じますし、そこまで言えた立場ではないのは承知の上で、まあ適度にこの記事を楽しんでいただけたのなら幸いです。いつかどこかでまた会いましょう。
その他雑多
急に見出しの意味が分からなくなりましたが、以下は参加記というにはあまりにも似つかないが、でも書きたいことを書きまくるスペースとします。
競プロについての少し小話
日記をもっと続けておくべきだった...と思いますね。Obsidian君はタグ付けされたメモ同士をつなげて可視化してくれる機能とかあって、自分の頑張りを可視化してくれるんですよね。一度あれが途切れたから、モチベも次第に薄れてしまったのではないかな～と思います...
ぜひとも、競プロに足を踏み入れる際はObsidianの環境を整備して毎日今日学んだことを日記にまとめることをしてみてほしいです。メリットは絶対に大きいです。
セミファイナル進出したときは、わ～ってかんじである程度はうれしかったですが、志望校の総合型入試にはセミファイナルAランクが書類免除条件であったために、まだまだだな～と結構軽視していました。でも、よく考えてみれば200/5000くらいではあって、実は意外とすごいのでは？と気づきました。スポーツとかでいえば、全国大会とかインターハイレベル？らしいですね。
セミファイナル行けたけど、ファイナル落ちた...で落ち込む必要は全く持ってないと思います。これは自分に向けても、同じ参加者すべての人に対しても言っていることです。十分頑張ってます。
布教したいこと
セミファイナルの5日前くらいから、とあるアニメ映画に目をつけていて、セミファイナルの終わった夜に打ち上げ的な感じで、一人でじっくり鑑賞する予定を立てていました。超かぐや姫！っていうやつです。
ポップコーンもしっかりと購入して、家でじっくりと映画館気分で鑑賞した結果...
👉結論から言うね。これ、普通にめちゃくちゃ神作品。
...内なるChatGPTがあふれ出てしまいました。
いや本当に、これ神作品がすぎるんですよね。ぜひともNetflixを持っている方は見ていただきたい...いや、持っていなくてもすぐさまNetflixを1か月分契約する価値が大いにあります。これのためだけに契約しても十分おつりが来ますし、今は呪術廻戦とかフリーレンとか、いろいろやっているのでめちゃくちゃおすすめです。
あ、まだ本編を見ていないなら一度いくつかのオリジナル曲とかを歌詞までよく聞いてきてほしいです。見終わった後の感動を少し増やすスパイスです。
「Ex-Otogibanashi」と「Remember」と「星降る海」がおすすめです。
え、せっかくなのでちょっとだけ語ってもよろしいですね...?ネタバレでしかないので、本編を見に行きたい方はここでNetflixを開きに行ってください。逆に、もう見た人はここから先で私とこの感動を分かち合ってほしいです。
