JOI2021 参加記 - soraie's blog

JOI2021に参加し、本戦まで残ることができたのではてなブログでの初めてのブログを書くことにしました。

また、とても悲惨な体験をしたのでそれも併せてここに書いておきます。

一次予選

まあまあここは大丈夫ですね。C++を封印してPythonで参加しました。

舐めプしてごめんなさい。

二次予選

このブログは本戦終了後に書いているので具体的なムーブは忘れてしまいました！！！

なのでおおまかな流れだけをここに書いておきます。

スタート

絶対に通るぞという強い意志を持って開始しました。

A問題を解く

結構実装が面倒でした。一回オーバーフローしましたが、早めに気づき、修正してACした。

B,C問題を開く

なんか算数オリンピックとかで見たことがあるなあとか思いながら解きました。

あとで調べたら本当にありました。結構難しかったのでC問題も開き、交互に考えました。

Bの解法が分かる

前処理で条件を満たすパンケーキの並びを全部持っておいてBFSをするという解法を思いつきました。パンケーキの並び方は $3^N$ 通りなので、計算量を考えると前処理が $O(3^N)$ でクエリが一つ当たり $O(1)$ なので間に合います。

C,D,Eを考える

A,Bの200点では通らないだろうと考え、さっき考えていたCとD,Eを考えました。

しかし、なかなか分からず結局Dの小課題1(めっちゃ簡単なやつ)しか取れませんでした。

終了

コンテストが終わった瞬間は正直終わったと思いましたね

しかしtwitterとかで他の人の得点を見てみるとみんな意外と点数が低く、結果的に本戦に進出することができました。

本戦

正直強い人がいすぎて通る気が全くしませんでした。まあ結局通らなかったです。

だって黄コーダー以上が30人以上くらいいるっていくらなんでも異常（）でしょ。

競技前日

開会式の動画がすごかった。

みんなの顔が見れた。

とりあえずすごかった。

あもんぐあす楽しかった。

感想が小学生。

スタート

春合宿行けたら嬉しいくらいの気持ちでしたね.....

もっと気合をいれなければダメでした。

Aを解く

Aを見ます。小課題1も分かりませんでしたが実験をするとなんかいい感じに解法が降りてきました。小課題1を取った後満点解法を書いて通します。

Bを見る

まず愚直を書いて小課題1を通しました。満点解法を考えます。

風のデータをあらかじめ解析しておくと雪玉の間の幅を利用することで満点が取れると考えました。実際これは合ってたっぽいです。

しかし、実装して提出してみるとTLEが帰ってきました。コードをじっと睨んでみますがバグが見つかりません。

C,D,Eを見る

とりあえずCの小課題1を通しました。しかしそれ以降は全く分かりません。

終了

結果138点で終わりました。解説を聞いてもBのバグは分かりません。モヤモヤした気持ちで本戦を終えました。

交流

いろんな人と交流できてとても楽しかったです。やっぱりあもんぐあすは楽しいですね。

後日

ABC192に参加しました。このコンテストのE問題のダイクストラがなぜかTLEしました。このせいでパニックになってしまい、緑パフォを出し、レートが40ほど下がりました。

睨んでも分からないのでEのコードをみせたところ、

#define _GLIBCXX_DEBUG

ここの部分を指摘されました。上のコードは書くことでデバッグをしやすくしてくれるのですが、これを書くと実行が遅くなってしまうらしいのです。

この部分を抜いて提出したところ、ACしました。

え、これがなんで今回のJOI本戦と関係があるのかって？

僕はJOI本戦のB問題で計算量は間に合うはずなのにTLEをしました。そしてそのコードでは

#define _GLIBCXX_DEBUG

とlower_boundを使っていました。もう分かりますね？僕がJOIのBでTLEをしたのは多分

#define _GLIBCXX_DEBUG

のせいです。悲しくなりました。

おわりに

オプションをつけないと#define _GLIBCXX_DEBUG されないようにしました。

もうこんなことは絶対にあってはならないのでこれから自分のテンプレートにコードを書き足すときには十分注意したいと思います。

ここまで読んでくれてありがとうございました。またいつかブログを書くかもしれません。