Hello, World!
こんにちは。Un_titledです。
JOIGのファイナルに出場してきたので、記事にいろいろ残していこうと思います。
最後まで読んでいただけると嬉しいです。
この記事は競技内容を中心に書いていきます。
その他の全体の記録は以下のnoteの記事にまとめました。こちらも見ていただけると、中の人が非常に喜びます。
目次
セミファイナルまでの話
セミファイナル参加記録 でQiitaにまとめると言いながら、日々の忙しさによって、まだ例の記事は下書きで発酵しています。期待しないでください。多分その記事は一生下書きにいます。
なんなら二次予選の記事もまだ下書きにいます。インフルの時に書いてるから脈絡も何もないので、こちらも出す予定がありません。
本題に戻ります。
二次予選までにやったこととしては、難易度6を埋めていました。
同時期に出した 入緑記事 を見ていただくと、何をやっていたかの詳細がつかめると思います。
セミファイナルまでには、難易度7を埋めていました。が、これでもかというくらい本番で緊張して頭が回りませんでした。精進の効果なし。
落ちたな、終わったなと思って呆然としていたのですが、部分点を死に物狂いで獲得していたらボーダーでした。そうだとしても、1完+部分点という無残すぎる感じで相当ショックでした。
この辺の絶望感はセミファイナルの記事の方でさらに触れているのでよかったらぜひ。
ファイナルに向けてやったこと
入水記事 の内容とわりとかぶっている部分があるので、入水以降にやっていたことについて言及します。
難易度8を埋めていました。それだけ？それだけなんです...
言い訳にはなるのですが、期末考査の期間がばっちりかぶっていて、あまり進捗は良くないです。
JOI埋めの進捗はこのような感じです。
備考程度に、春合宿時点のレートはAlgoが1231です。水色ですが、露骨にわかりやすい典型以外が全て弱いです。
例の忌まわしき考査の影響で、3月初旬の2週間くらいはまともに精進ができていませんでした。しかも打率はだいたい3割くらいで、ただ不安要素が増えました。
ファイナルの前の週の土日に初めて仮想マシンを触ってみました。 いろいろ見てみて、普通にやらせる気がないのではないかと思いました。
同じ日に初めてoutput onlyにも手を出しています。なんという計画性のなさ。
プラクティス
プラクティスは真剣にやることを推奨します。少なくとも初めて出る人は真面目にやりましょう。
キーボードを持参していない人は特に要注意です。私は苦戦しています。テンキーの扱いに慣れておらず、insertキーを押してしまうミスが多発しています。地味にストレスなので、そのような点を気を付けましょう。
communicationのデバッグについてもここで慣れておくのが一番良いと思います。batch型はもちろんですが、communication型の課題が手元でデバッグできないとなるとかなり不安が大きくなると思われます。
競技1日目
ここから先、問題のネタバレが100%です。
時間が書かれているのは開始からの時刻です。
競技時間は300分、5時間。
Macaron
chminをやるだけです。
マクロなどをとりあえず書いていたのもあり、13分で100点。
Sports Festival
二分探索っぽい形が見えながらも、有効な手段を見つけられず、とりあえず小課題1の12点を確保（37分）。
この問題の提出について、これが最初で最後になったのはかなりの痛手でした。
考察ができなかったというより、ある程度の考察は詰められたものの、よい実装方法がわからなかったという感じです。普通に実力不足。
Cake 4
JOIってケーキの問題多いよな～と思いました。
問題を読んでみて、それぞれのケーキのパーツを頂点として、ともに選べないものを辺でつなぎ、二部グラフのように色分けすることを考えました。
部分和DP的なことを木でやろうとしたものの、じゃあどこから始めればいいんだ...というところで考察が詰まりました。
とりあえず小課題1をbit全探索で通します。7点（52分）
小課題2を見たときに意図が分からず、一回とばしました。
この後、Casinoを見てから、これはできないと勝手に決めつけ、こちらに戻ってきました。
がりがり考察していたのですが、ようやく小課題3を通しました。18点で合計25点。（203分。遅すぎる）
そしてここから残りの約100分を小課題2のバグ取りに費やし、結局一点もとれませんでした...
結論から言うと、考察の詰めの甘さが原因です。
同じ大きさのケーキについては、差が0であり、$1 \leq D$ が保証されている以上、すべて選択するのが最善手だと思いました。この方針は根本としては正しいのですが、 同じ大きさを2つ足して $S$ になるケースを除く必要があります 。
つまり、ケーキの大きさごとにまとめて座標圧縮的なことを行ったわけですが、更新がすべて和をとればいいというわけではなく、 $\dfrac S 2$ の大きさのケーキについては最大値をとる必要があったというわけです...
解説を聞いて文字通り頭を抱えていました。天井を仰ぐ時間が最も長かったかもしれません。
この落とし穴に気づけず、競技中に特に改善もしていない書き直したコードを10回以上提出しました。ごめんなさい。
Casino
問題は読みました。ただ最大ケースの大きさにとらわれすぎて、解くことをあきらめてしまいました...
$8 \times 8$ の計64マスに51桁を詰め込むことばかり考え、パリティビット的なことを13マスでどう表すんだ？！となっていました。
対角線の形でパリティビットを置くことばかりを考えていたもので、わからなくなって捨てました。あとから昼食の時間にいろいろな方と話して、これがこの日最大のミスだったことに気が付きます。部分点への認識の甘さが浮き彫りになった一問です。
1日目の昼食・解析
昼食を呆然としながら食べていました。最初の方は順位がまだわからなかったため、さらに不安が大きかったです。昼食はおいしかったです。
途中でsquare1001さんが目の前に座ってきて、例のCasinoの話を聞いていました。30点くらいはかなり簡単に取れる問題だったと聞き、衝撃を受けたのもこのときです。
隣に座っていた方がCasinoでかなりの高得点を取っていたので戦略を聞いていました。
マス目を斜めに敷き詰めることばかりを考えていましたが、確かに部分点の観点から考えれば極論1文字の場合だけだとしても得点を得るべきだというわけです。（実際、1文字だけの場合でも得点がもらえるようです。なぜそれすら取らなかった...）
順位をまとめられた紙が途中で配られました。9位。
反応に困る順位でした。悪いことに変わりはないものの、上位陣（レベチな神々を除く）とは100点も離れていないような感じです。
うえこさんと話していて、EGOIの選考くらいのレベルになってくると、満点を取るのはそうとう難しく（実際、Cake 4 は確かに木DPではあるものの、満点をとるのは相当実装が重いようです）、いかにあきらめずに部分点を獲得するか、という勝負だと身をもって体感しました。
これについては文字でどれだけ読んでも、体感するのとは別物だと思います。
解析が昼食の後にありました。異議申し立て兼解説のコーナーです。
macaronは特筆することもなさそうですが、Sports Festivalについては、最後の満点解法が尺取り以外の二つが明らかに難易度が高すぎて怖いといった感じでしょうか。誰がセグ木上の二分探索を覚えているのでしょうか？ACL以外で遭遇したことがありません...
Casinoについては、これはまたいろいろな考え方があって驚きの連続でした。
みつばちさんは何を食べたらあんなにたくさんの解法というかアイデアを発想できるのでしょう...
はちみつを食べようと思います。
全体として、このころにはわりと絶望というより、競プロおもしろ～が勝っていました。結果として大失敗を喫したものの、メンタル面のコントロールはわりとうまくいったのかもしれません。はたから見たら特に事故を起こしたことに変わりありませんが。
競技1日目の反省まとめ
- デバッグを何回してもだめだったら考察漏れを疑いましょう
- 問題設定が難しかったとしても、たった3点だとしても取る気持ちで、超小さい場合の部分点でも取りましょう。そこから始まる物語が確かに存在します
- プラクティスでコマンドラインとVSCodeをどう使うかをある程度考えながらやっていたのは効果的でした。競技中に困ることが一つ少なかったのはいいことです
競技2日目
雨でした。
始まる前にラムネを確保しようと思ったら、まさかのラムネの在庫が0で危うく飢えるところでした。
友達がラムネを一袋わけてくれたのと、JOI側に残っていたらしいごく僅かなラムネをチューターさんが持ってきていただいたおかげで助かりました
Railway Trip 4
いつも通りマクロを書いたりしていました。
見てびっくり。普通にDP難しすぎてできない！となりました。
とりあえず小課題1、2を順番に通しました。（小課題1 8点20分、小課題2 11点33分）
ペナ無しで通したのはよかったのですが、この後二分探索をして全てを壊すなどをして、この問題の得点は19点でした。
Zoo
小課題1、2どちらについてもビット全探索をしました。
が、どうやら実装をばぐらせていたようで、3回ほど不正解を叩き出しました。
他の問題をやってから戻ってきてから小課題1と2の分を通しました。13点。（247分）
インタラクティブの形式自体には慣れました。普通にアルゴリズムができません…
Scarecrows 2
かかしって英語あったんだーと思っていましたが、そんな悠長なことを言う暇があったのでしょうか、りうるさん…？
小課題1と2をやりました。
尺取り的な動きをする愚直です。これも一旦不正解を叩き出した（107分）ので、他をやってから戻ってきました。12点。（261分）
Collecting Stamps 5
グラフ探索だ！と思って嬉しくなったのはいいのですが、一番難しい問題なので詰んでいます。満点は期待できません。期待するものではありません。
これはかなり実装をバグらせ続けていました。117分あたりから提出を投げ始めたのですが、タイポ的なミスを見つけるのに50分近くかけたようです…
小課題1で5点（174分）、小課題2、3で26点（146分）
実はこの問題だけならJOIG内でも割と上のほうだったんです。この問題だけなら。
2日目の昼食・解析
ゆっくり食べてたら自分のテーブルの最後の一人になりました。JOIGみんな同じテーブルだったんだけどな…笑
順位は9位のままです。耐えてる…
この日は1完もできてなく、得点が2桁とかいう惨劇だったので、もう失うものはなくなったかと思っていました。
本当にみなさん優しくて、自分が解けなかった課題を通している人にどんなふうに考えたのかなどを教えてもらっていました。
つよくなりたいです。
また、チューターさんとはかなり話せるようになって嬉しいです。
やっといろんな人と話せるようになってきたと思ったらもう折り返しなんですね。
解説を聞いてると、各問題についてあと何個かとれたなーという気持ちでいっぱいになります。
何も言うことはないです。ただの力不足。
共通問題ですらJOIGの方が制約などが簡単になっているってのが恐ろしいところです。同じ人類ですか？同世代って本当ですか？
blackyukiさんがアメリカからzoomで解説してくださっている状況が面白かったです。
競技2日目の反省まとめ
- フォルダとファイルをやっと使い分けられるようになってえらい。ABCの時とかは、常に同じファイルで毎回全消しして書き直してたので、小課題をうまく扱うためにファイルを分けるという技術をやっと手に入れました。いつから競プロやってんだろうという発言です
- これについては補足があって、CMSは得点の計算がそれぞれの 合計 であり、AtCoderとは違うという点が大きいです。実際、私は小課題2のコードは小課題1が通らない、みたいなのが多いです
- ミスって違う問題のコードを提出しないようにしましょう。方針からミスってるのかな…などいらないところに気を使うことになります
競技3日目（最終日）
宿泊場所から移動する間で危うく迷子になりかけました。
前日のラムネ不足を受けて自分でも調達を行いましたが、入荷していたので1つもらいました。
Cheese and Mice
いつも通りマクロなどを整備しました。
だいぶ自分の中で何をするかのルーチンができたと思います。最終日に？という感じですが。
とりあえず小課題1の11点を獲得（16分）。
難しかったのでここで他の問題に一旦移りました。
帰ってきたのは120分あたりです。ぐっと睨んだら、区間最小値取得のセグ木を使う解法を思いつきました。これは小課題2を想定してやったものなのですが、想定外にも実行時間制限にひっかかり、挫けかけました。
捨てて他の問題をやってた中で、小課題3を先ほどのセグ木解放で通すことを思いつき、追加で35点を獲得しました。（257分）
Curry and Rice
小課題1〜3は順番にすんなり通せました。
特筆することも特にないですね。
（小課題1 22分6点、小課題2 29分7点、小課題3 37分12点）
120分あたりで戻ってきて、小課題5 20点獲得（208分）、小課題4 14点獲得（221分）
小課題6は優先度付きキューか…？実装方法がわからない…と思っていたら本当にそうだったらしくて笑うしかないですね。弱い。
Packing Snacks
簡単な貪欲を書いて小課題1 12点（45分）
春で毎日書いてるビット全探索をいとも簡単にバグらせて不正解を獲得した後、小課題2 17点（80分）
ふと小課題3をみるとびっくりするくらい簡単でした。9点（83分）
Voltage 2
ごめんなさいカスでした。
小課題1の4点だけです。
終わりがけに「小課題2はパスグラフだし、後ろから見ていけばいいのでは？！」となったのですが間に合いませんでした。
後ろなら特定できたんだけどなー、そこからの実装が間に合いませんでした。がっかり。
3日目の昼食・解析
お手洗いに行って帰ってきたらすでに順位表が配られていました（？！）
ドキドキする間もなく、目に入りました。9位。耐えたけど上がらなかった…
OIに弱いということかなと思ったけど、どちらかというと考察に弱そうです。明らかに見える典型しか解けないのが弱すぎる。これをどうしたらできるようになるのかがわかりません。教えてください。
お昼ご飯は今日も美味しかったです。
松阪さんのぬいぐるみを初めてもちもちしました。もちもち癒しでした。
Cheese and Miceについて、終了20分前くらいに「何かしらの規則性で、分割してその中をどうにか加工すればいけるか？」のように思っていたのですが、本当にそうだったようです。悲しい。
手元での実験の重要性をつきつけられました。
Packing Snacksは葵とビ太郎の不仲説が浮上する1問となりました。来年はどうなるんでしょう。
OIのcommunicationは二分探索です。今度からcommunicationを見かけたら真っ先に二分探索を疑います。これは今回の春合宿の学びの一つです。
最終日にしてようやく小課題のいい点の取り方をわかった気がします。全部遅かった。
競技最終日の反省まとめ
- 初めて問題ごとにターミナルをつくりました。その方がいいです
- 手元で実験をしましょう
JOIG初めてのファイナルを終えて
決して短くはなかったけど、終わってしまうのが惜しい5日間でした。
結果としては 137 + 75 + 147 の計 359 点でした。 およそ1200点満点とは想像も難しい点数です。
3日間9位をキープし続け、変動することはありませんでした。1日目に戦略をミスったことを大事故と称しましたが、単なる実力不足でしかありません。言い訳は通用しません。
よく考えてみれば、5時間連続の競技を何日も続けてやったのは初めてだなと思います。率直な感想ですが、5時間はそんなにつらくなかったです。それよりも、数日に分けて順位が変動するため、もしかしたら今日もっと順位が落ちてしまうんじゃないかという心配の方が大きかったです。
春合宿を経て、自分にとってはオンサイトの存在がやっぱり大きいんだなということを実感しました。お昼の間で近くにいる人と、どんな風に考察・実装を行ったかを話したりするのはもちろん、なんでもない雑談で盛り上がったり、ふざけあって騒げる競プロの友達を見つけられたことが一番嬉しかったです。
間違いなく、この5日間は競技を含めずっと楽しかったです。
競プロを初めた昨年度のJOIは、なぜだかうまくいきすぎてJOIG本選に進出したものの、案の定何もわからず太刀打ちできず敢闘賞をもらいました。
来年は春合宿に行ってみたいな、そんなことを言っていた去年の3月でした。
いざ1年後。セミファイナルへの選抜の人数（つまり二次予選通過人数）が減ったことを受けて、大きな衝撃を受け、一つも進んでいない勉強を一旦止めて競プロに打ち込みました。初めてここまで詰めて精進をしたし、AtCoderの成績としてはレートをあげることができました。
自分はまだやれたなと思うことだらけでしたが、ずっと楽しかったです！
最後になりますが、JOIの運営をしてくださった事務局の皆様、5日間にわたって競技全般を近くで支えてくださったチューターの方々、そしてともに戦った参加者の皆様、5日間大変お世話になりました！
話してくださった皆様、本当に嬉しかったです。今後も機会があったらぜひ声をかけてください。
来年もJOIG春に来ます。これは決定事項でないと困ります。
そして来年こそは自分も花束を貰えるよう、止まっている勉強をなんとか消費しつつ競プロも頑張ろうと思います。ぜひアドバイスをください。
お会いした皆様はまた次回のオンサイトでお会いしましょう！
もっと強くなって帰ってくることを誓います。ではまた！