JOI'20本選敗退記

競プロ JOI 参加記

JOI'20本選に参加して245点でした。推定25位なので本選落ちです...

2/1~2/7

学校の課題の発表準備や塾の宿題で忙しくて精進の時間が取れず、結局この期間に通した問題は2問だけだった。1月に通したまともな難易度の問題も18問と圧倒的精進不足であった。

2/8 Day1

午前1時　コイン集めを解いて寝る

atcoder.jp

午前8時起床　適当に荷造りしてコンテスト用のドリンクとチョコレートを購入し出発

12時少し前に秋葉原に着くと物理好きとTKOがいるとの情報をもらったので合流　その後QCFiumとibukiと出会って昼食

料理が50分くらい来なかった

本選会場の途中にあったつくばカピオを見て懐かしい気持ちになる。(2017-2018の会場)

本選会場では交流代わりに人にパ研とパズ同部誌をばらまいた。10部くらい渡した

パズ同の部誌はここから見ることができるのでよろしくお願いします。

tsukukomapuzzle.blog.fc2.com

2年越しのプラクティスだが、環境も問題もほとんど変わってなかった。A~Cと最後のDartsは難なく通したが4問目のIOIOIで無限にバグらせた。バグ取りをしているとThistleが来て煽られた。Thistleと喋りながらデバッグをしていたため、4問目であるIOIOIのソースを5問目に提出するなど考えられないようなミスを連発した。結局全完に52分ほどを要した。

全完した後はチューターの方々に部分点の仕様を確認してもらったりREやMLEの種別を試すためにassert(0);を投げたりといろいろ実験していたが、それも終わると後ろの方で人々と交流しはじめた。なんだかんだでいつもの勢ばかりとしゃべっていた気がする。

夕食会の自己紹介する場所がビール箱の上から壇になっていて少し感動した。自分の番で何を話したかよく覚えていない(コンテストで連戦連敗した話だった気がする) 結局この場でもいつもの人々としか交流していなかった気がする。

独房に実家のような安心感を覚える。適当にTwitterをしたりMergersを考察したりしながら雑に人々と交流する。

TAISA_のスマホが割れたと教えられたので、その教えた人といっしょに煽りに行く。(Rhoは図の最右)

その後も人々と雑に交流する。結局寝ようとしたのは24:00だが、40分くらい寝付けなかった。

2/9 Day2

起床AC　朝食後はセグ木を見直してLCAの実装を練習した。起床TLE勢のおかげでバスが出発できない期間はMergersを考えていたが微塵もわからなかった。

本選会場に昨日の水と今朝買った午後の紅茶に会場でもらった水2本を合計して4本のペットボトルと、前々日に買ったチョコレート3枚を持ち込んだ。飲食に困らない状況を構築したところでコンテスト開始まで精神統一。

A 長いだけのネクタイ

1.cpp~5.cppのセッティングにヘッダの構築、PDFファイルのダウンロードなど諸々10分くらいかかった 1番だし昇順にマッチングだろうと思って貪欲を手元で試すとよさそうなことがわかる

同じ計算を何度もしていそうなので累積maxを書く。n+1をnと書いて10分くらい溶かす

B JJOOII2

Jの終点を決めるとOもIも貪欲に左から取ればいいことが分かる(少し飛ばしたところでよくなることはない)

そのコストは累積和なり二分探索なりを使えば求められる　JIOみたいなケースでハマってこれも結局30分くらいかかった

C スタンプラリー3

見るからに区間DP dp[左][右][時間][どっち側]を書くがバグらせて結局1時間くらいかけて15点を取る。どうにもわからないので先にDとEの部分点を回収することに決めた。

D オリンピックバス

グラフなので見た瞬間に飛ばした。 M=1000の部分点は自明だったが、実装が重かったのとCが解けると思って手を付けなかった。実際に部分点をとってもいいことはなかったので正しい選択なのかもしれなかった。

E 火事

小課題1は実装をさぼっても取れた。

小課題2は適当にセグ木を書いて累積和をとった。

小課題3もセグ木を流用した。

小課題4ではBITが必要なことが分かったが、とっさに書けなかったのでセグ木で書いた。

4つの小課題を合わせると微妙にMLEするので一部の配列を動的確保にしたら20点を得ることができた。(この時点で235点)

Dの部分点をとるかCに戻るかで迷うが、グラフを解きたくない一心からCへ戻ることにした。

C 再び

この時点で12:00、残り一時間ほどであった。

Cに戻ってくると、DPの添え字と中身を入れ替えるテクが適用できそうなことに気づく。先のコードをやや修正してテストケースを入力するとなんと全て合う。勝ちを確信して提出する。

提出から1分30秒ほどF5を連打していた。このときの心拍数は200~230に至っていたかもしれない。そして帰ってきた結果は...

不正解 0/100

実際に書くと、円環の更新順序がおかしなことになっていることに気づく。その場で円環を2周させるコードを書くも5点となる。ここで更新順序を解決するためにqueueでDPの添え字順を管理しようとするがうまく実装できない。

せめてもの部分点通過の祈りを込めて円環を3周させるコードと先にとった部分点15点を合わせて25点を出すコードを提出。結局25点しか取れなかった。

このケースでは本質部分はすべてわかっていてバグの原因も見抜いていたにもかかわらず通すことができず、結果春合宿進出を逃してしまった。大大大大反省しなければならない。

After Contest

すぐ近くに来たThistleに人々の状況を聞くと、どうやら大量に3完しているとの情報を得ることができた。救いを求めてmencottonに点数を聞きに行くと、なんと1点勝っていた。3問目のエッセンスだけはわかったと話したら、どうやら向こうは気づいていなかったらしく僅かな優越感を得る。

昼食会場で回りの会話を聞いていると、どうも3完が予想よりはるかに多くいることがわかる。https://twitter.com/Rho4913/status/1226361764167573504

引退ツイートをするついでに会場の机を接写して黒アイコンに変更する。そして持っていたTwitterのアカウントを2つほど消し飛ばす。

点数順にソートされた得点票を受け取るときに自分のすぐ次が300だったように見えたので、自分が2完界のtouristである可能性が出てきたが、何の慰めにもならなかった。

3問目の解説で出てきた得点分布で自分の敗退をはっきりと悟る。もうこれ以上の希望はないとわかり、かえって清々しくなった精神でつくばエクスプレスに搭乗して帰路へと着いた。

後日譚

本選落ち黄コーダー三銃士を名乗ることを決定する。

敗退をきっかけに心機一転する意味も込めてAtCoderのIDをRyo2016からRho17へと変更する。

この記事の初稿を20:00に投稿、そして大量のスターをつけたmencottonに敗退記を書くよう脅す。その結果...

mencotton.hatenablog.jp

このような記事が誕生し、それを皮切りに多くの人が本選参加記を投稿するようになった。(?)

もし因果関係があったとすればそれは大変嬉しいことだ。

総括

単純に実力が不足していたのが悪いので、実力を磨く必要がある。

最後の1時間まで通る可能性が残っていただけに非常に悔いの残る結果となってしまった。一体この先どうすればいいのだろう...