JOI2020本選参加記
1日目
午前
午前中はエクスカーションを楽しむと決めていたので、あまり競技の事は考えなかった。
同期の人々と9時に秋葉原で待ち合わせ予定だったが、みんな早く来たので早く電車に乗れた。
TXには何度か乗ったことがあるが、やはり速い。スピードを上げる時の浮遊感(?)が心地よかった。
40分弱くらいでつくば駅に到着。が、目的地のJaxaまでは徒歩40分と長い。
少し早く着いたので、見学ツアーに含まれないスペースドームに行った。
月の探査機が想像よりもはるかに大きくて驚いた。小さいロボットみたいなのを想像していた。
改めて、恋アスの絵が忠実ですごいなぁと思った。
ツアーの最初は映像を見るのだが、案内の人が「(札が)水色の方どうぞ〜」と言ったらみんな笑っていた(AtCoder)。
宇宙飛行士養成施設で、ガイドさんが「宇宙飛行士に最も必要な事は協調性です。」と言ったらTK生だけ笑っていた(協調性がない)。
宇宙飛行士候補は、集団で、10日間密閉された空間で過ごすらしい。
kaageが「物理好きさんとか厳しいだろうなぁ。◯すから」とか言っていて、個人的には面白かった(最悪)。
隣りにいたおじさんが「みんな同じような顔してるねぇw 将来、東大行くんでしょ」とか言っていた。実際、みんなメガネ+マスクだったので無理はないと思う。
見学が終わった後はJaxaの社員食堂で昼食を取る予定だったのだが、当日になって土曜日は社員食堂がない事に気づき、しばらくさまよった後、国際会議場近くのリンガーハットで食べた。
ちゃんぽんを食べたのは修学旅行で長崎に行った時以来だったと思う。
午後
国際会議場のホールに行ったら、TMJNさんとhairaさんに会った。hairaさんに会ったのは久しぶりだったが、やっぱりかわいいなぁ...
受付を済ませ、Practiceまでの時間は本選に来た人と色々話していた...というのは嘘で、実際はTwitterしかしていなかった。
一応電脳を3冊配ったが、結構無愛想だったかもしれない。渾身の懇親に失敗...
Practiceでは、Eclipseのプロジェクトの作り方などを確認して、後ろで人々と交流をした。
とは言っても、パ研合宿に来ていたようないつもの人としか基本喋っていなかったと思う。いや、立ち歩いているのがいつものメンバーしかいなかったという方が正しいかもしれない。
暫くして、スタッフ5人くらいに呼び出された。
席を離れる時にWin+Lで画面ロックをしておいたのだが、どうやらこれでWindowsが開かれてしまうらしく、これは不正行為になるという。
仕様だと思っていたのだが、本選では席を離れる時はパソコンを閉じるように、万が一やってしまった場合は相談するよう言われた。ひょえー
Practiceが終わると夕食会だった。食べる前に予選満点賞の表彰があるのだが、食事前に紙を渡されてもチョット困る...。
結局、グラスを間違えないためにコースターとして使うことにした。
夕食会の途中に会った自己紹介では「茨城県にある筑波大附属駒場中2年の〜」などと言い、みんな笑っていたが本当に茨城にあると思った人もいるかもしれない(?)。
夕食会が終わると、宿舎に移動した。ベッドメイキングやお風呂などを済ませ、早めに寝ようと思ったのだが、全く眠れなかった。
一番の原因は、心拍数である。明日が本選であると考えると、それだけで心拍数が上がり、これでは睡眠不足になってしまうと考え、また心拍数が上がり...を繰り返していた。
また、独房が暑かったのもあると思う。寒いよりはマシだが...
結局、目を閉じたまま深い眠りにつくことはできないままだった。最初は3:34に起き、その後は1時間おきに起きてしまった。
2日目
朝
朝食は鮭の切り身で、おいしかった。結構ご飯の量が多かったので、食べ切るのは大変だった。
この後バスで会場に移動するのだが、絶起erがいたらしくちょっと遅れた。
その間も、もうすぐ本選競技がはじまる...という緊張で心拍数がヤバかった。
本選競技
開始の合図とともに、まずは1問目を見た。
最大値の最小値...二分探索?と思ったがすぐに貪欲だと気づいた。
使わないネクタイを前から考えてしまい、分からなかったのでmultisetで殴ってしまった。
後ろから考えると、答えが単調増加になるので線形時間で解けるらしい。
提出すると、全部WA。確認すると、出力を全部改行区切りにしてたせいだった。
考察に一番時間がかかったのはこの問題だと思う。20分くらいで満点。
2問目を見ると、これも貪欲に見える。
要は、レベル K のJOI文字列を部分文字列に持つ長さの最小値を求めろということだと分かる。
J,O,Iそれぞれで i 番目までの個数を累積和して、スタートを決め打ちしてJ,O,Iの末尾を二分探索して解いた。
尺取りでもできるが、間違いなくバグるのでやめた。35分くらいで満点。
3問目の問題文を読むと、湖、制約が200ということで O(N3) の区間DPをすればいいことがすぐにわかった。
これは実家なので勝利を確信したが、割と典型なのでみんな解いてくるだろうなぁとも思った。
このタイプの問題は、実装が暫くバグるが結局ACできると知っていたので落ち着いて実装できた。
実際、初期化忘れや、簡単のための2倍処理をミスってかなり時間を溶かした。1時間半くらいで満点。
3問目を早めに通し、割と心に余裕があった状態で4問目を読んだ。何本も反転させてよいものと思っていたので、小課題1すら分からないまま20分が経過。
よく分からなかったので5問目に進んだ。5問目は、問題の見た目がセグ木で得意分野だったので嬉しかった。
小課題を見ると、意図が明らかなのでそれぞれすぐにわかった。
小課題1,3は素直にRange Max Query、小課題2は前処理をしてからなぜかRange Sum Queryを使った。なんで累積和を取らなかったのか...
小課題4は、火力が2になる時刻が分かればいいので、時系列順にBITで殴った。
小課題4のQueryのソートで、operatorにおいてQueryのタイプでbool型の比較をしており、そのせいでずっと小課題4だけREだった。
Queryのタイプをint型にしたら通った。終了45分前に20点。
5問目の小課題を全部取ったので4問目に戻り、小課題2の考察をした。
適当にdijkstraを書き、サンプルをテストするとWA。手計算でもWAだったので、問題文をよく読むと反転させるのは高々1つだった。
残り20分しかなかったので、とりあえず小課題1だけ取ることを考えた。
実装方針を間違え、終了5分前に小課題1の5点を取った。
小課題2は間に合わず、結局325点だった。多分、春合宿は通ったと思った。
解析
解析の時間、色んな人と話すとみんな三完していた。ボーダー300超えもあるかもしれないと思うレベルだった。
Kodamanにはギリギリ勝ち、blackyukiとは同点だったが、kaageは4問目の小課題2を取り、5問目の小課題4を取っていなかったので5点負けた。
多分、みんな最高パフォーマンスが出ていれば336点は取れているだろうなと思った。
どうやら、4問目で誤読をしたのは僕だけではなかったらしい。”高々一つ”は太字になっていたが、紙面の端にあったので気づかなかった。
昼食会場ではボーダー予想が行われていた。やはり、3問目が簡単だったのもあって300点前後だろうと言われていた。
3問目の解説で満点が23人と出ており、4問目の満点0、5問目の満点はhirakichiさんとQCFiumさんだけだったのでボーダーは300点以上が確定した。
300点が2人、301点が1人はいると聞いていたので、ボーダーは300か301か302の三択だろうと思った。
この時点で春合宿がほぼ確定したので、嬉しかった。
去年は予選Bランクで今まであんまり自信がなかったのだが、少しは認められる存在になったのかなと思えた(は?調子に乗るな)
しかし、中2は4人通過したと思われ、IOIに行くのは大変だなぁと思った。
帰り
つくばから守谷までは席がほとんど空いていなかった上に、誰も優先席の周りにいなかったので優先席に座っていたのだが(守谷で人が多そうなので立った)、傍から見たら社会性のかけらもないクズに見えたに違いない。
その途中でこたまねぎさん達に会ったので、かなりバツが悪かった。第一印象は最悪だったであろう。
守谷からは床にリュックサックを置いてみんなのデータ構造を読んでいたのだが、ほとんどの駅において開くドアが入れ替わり、リュックサックを持って毎回移動するのが面倒だった。
割とあっという間に秋葉原につき、家に帰った。
疲れていたので、ABCはサボった。
後日談
本選競技の翌日、JOIのホームページを見るとボーダーが301点になっていた。
5問目の小課題1の1点を取ったかどうかで運命を分けたと言えるだろう。
春合宿でも1点を大事にしようと思う。
さいごに
全体的にイキっててごめんなさい。