第 20 回日本情報オリンピック本選に参加しました。 300 点で逆ボーダーです…。
予選
なんとか時間ギリギリで満点を取れた。B と C が普通に難しくて焦った。
本当にぎりっぎり pic.twitter.com/40B4lloXMb
— Forested (@Forested_) 2020年12月13日
本選
過去問はある程度埋めておいた。 Twitter のガチプロ達がもっと埋めているのを見て恐怖を感じた。
JOI pic.twitter.com/1ARARPzINb
— Forested (@Forested_) 2021年2月13日
1 日目
自己紹介動画を観たりした。パ研合宿とかで知っている顔の人がたくさんいた。
今日は早く寝ろと言われたので 22 時に布団に入った。が、地震やら緊張やらで全く寝付けず、結局寝たのは 2 時半くらいだった。
2 日目
7 時前に起きた。 5 時間も寝ていないことになる。どうやら自身の影響で本選が 1 時間遅れるようなので、適当に Twitter で遊んでいた。しばらくして本選が始まった。
とりあえず 1 問目を読む。差を見ると解けて、まあ適当にやればよい。 10 分で正解。
2 問目を読む。全然わからなくて焦る。 とりあえず、ある雪玉が回収する雪の範囲は区間になる。隣り合う雪玉の相対的な距離が同じ時は同じ形になるから…とか考えていたら解けた。 30 分くらいかけた。
3 問目。こっちは 2 問目よりも方針が立ちやすかった。予め任意の人 [i, j) に対して転倒数 + α を求めておけば DP ができる。とりあえず前計算を適当に O(N^3 log N) かけて計算し、小課題 3 までをとる。 j を固定して i をずらしていけば O(N^2 log N) で求まることに気づき、書いて満点をとる。途中まで永続セグメント木が必要だと勘違いしてずっと TLE & MLE と戦っていた。
3 問目簡単だったし 300 点だと落ちるだろうな〜と思いながら 4, 5 問目を読む。どっちの小課題 1 も全くわからないまま終了。解説を聞いたら問題 5 は割と近いところにいた。悔しい…
解説や交流会などに界隈で有名な強い人がいっぱいいて、すごいなあという気持ちになった。（小学生並みの感想）
交流があまり得意ではないので、そんなに交流しなかった。 HTTF から何も成長していない。
終わりに
ところで気づいたら人生が破滅しかけています 助けて
