JOI本選参加記
JOI本選参加記
JOI本選に関する詳しい内容とかは他の人が書いているのでそっちを読んでください。 公開元が鍵垢なので、JOI参加者ぐらいしか読まないと思って書いています。
Day0
米澤穂信の『ボトルネック』を読んでいたら就寝時間が2時くらいになってしまった。 バッドエンドだがめっちゃ面白かった。かなりおすすめ。
Day1
起床が12時だった。睡眠時間は十分取れたので、これで最悪Day1夜に眠れなくても本番はある程度大丈夫だろうと思う。 去年はJAXAにcapra314cabraと行ってJMOをしていたから睡眠時間があまりとれていなかったので今年はとった。
エントリー終了25分前くらいにつけば十分だろうと思っていたらTXを逃し絶望していたが、意外と時間が大丈夫なことが分かり安心した。 つくば駅で、Day1朝に読んでいた眠気覚ましにチョコがいいという記事を信じ込んで、チョコレートと空腹時用に赤飯の握り飯を買う。 大丈夫(開幕ダッシュ前提)だったので、駅についてすぐ走り始める。15:58くらいに会場についてぎりぎりAC。安心した。
今年はトロフィーがもらえないのが残念だったが、mercariノートのほうが有用なのでありがたかった。 メルカリから大量の物資が来ているらしく、圧力をすごく感じた。(Jobsに求人出すほうがいいのでは?)
プラクティス開始後割と早くに全完、全列挙を煽りに行く。IOIOIで無限にWAを出しているのが面白かった。
「は?デバッグ出力消してなかった!カス!」
「は?5に出してたわ!カス!」
その後はいつもの勢といつものな感じでだべっていた。渾身の懇親って言っても結局いつものとしか懇親しないの良くないんだよな…
夕食会で夕食を食べた。去年はSegtreeと、ケーキがすぐなくなると予想し、人間性を捨ててケーキを確保していたが、ケーキあまり減らなくて人間性を失った人だけが完成していたので、今年は人間性をきちんと確保した。
gotoloopさんが「チューターはケーキとスープだけを食べる生き物」とか言ってたのを聞いた。チューターになると人間性を完全に失うっぽい。気をつける。
自己紹介はいつもの勢がいつもののようなネタ紹介をしていて面白かった。 誕生念1年ネタはなぜかは知らないが受けがいい上に、年齢が4桁の人は一意に定まるので自己紹介としても優秀で、とても重宝している。
運営の人が自己紹介で「私を拉致すれば解法が分かります」といっていた。来年は検討しようと思う。
バスの説明を聞き逃して間違えたバスに乗った。来年は気を付ける。
渾身の懇親を捨てて早く寝ようとするが、その前に凸包のアルゴリズムだけ見ておこうと思っていたところにSegtreeが到着、部屋のドアをガンガンやってきて普通に怖かった。(なんで部屋分かったんだ) ドワコンの結果聞いても「ドワコンすごかったよ」としか言ってなくて何があったと思っていたが、順位表見たらやべーのしかいなくてそりゃそうなるなと思った。
その後また寝ようとするが、夕食会でウーロン茶飲みすぎたことが発覚、電気消してから5回くらいトイレに行った。 まあこれがなくてもあまり眠れなさそうだった。遠足を前にした小学生か、という感じ。(次はもっと対策を練る) 就寝時刻結局0:40くらい
Day2
前日のプラクティスで2問目を通し忘れていたので、これが夢に出た。そしてそのまま5時に目が覚め、睡眠時間4:30、普通にまずいんじゃないかと思った。 6時まで結局眠れなかったのですぐにシャワールームに行き目を覚まそうとする。もう少し脱衣スペースとかがあるものを想像していたがなにもなくてビビった。本当にシャワーのあるルームでしかなかった。
部屋に戻り、朝食に向かう途中で廊下に布状の物体が落ちているのを発見。なんだ?と思ったら(…検閲により削除されました。
筑駒の内輪とかだったら何も気にしなかったが、普通に外部の人その他いるんだよな…(なんだかんだこれが本選最悪の出来事だった説がある) 朝食を食べ、部屋に戻るが暑すぎて眠くなるだけと判断、エントランスでライブラリチェックを始める。目を覚ます方法を調べた。
去年の朝のバスと同じくTAISA_が隣だった。去年はそのあと普通に落ちたので若干のトラウマ。 直前にトイレに行き持ってきた長めのタオルを濡らし首にかける。これで目が覚めるはず。
本選開始直後は普通に良かった。template.cppを作ってそこにいつものマクロを書いて、それをコピペして解いた。
1問目
問題文を読み、条件を理解し、1問目だしどうせソートするだけ、と思って適当に実装したら通った。若干実装に手間取ったがそれでも好調。
2問目
問題文を読み、考えたら真ん中のOは絶対に3の操作しか使えないことが分かる。 ここから、JとOの句切れ目を全探索、そのあとOが条件を満たす最も左の点を累積和+尺取りで見つけ、最後に前計算でdpした、ある点から先何回3をしたらIが条件を満たすかを求めた値を全部足し合わせる。 尺取りパートが混乱を誘ったが、じっくり整理すれば素直に解ける問題。
3問目
とりあえず考えたが、N<=200の苦手系列の問題で、しかもChinese(解いていない)の気配を感じたので、やめだやめ、って感じで飛ばす。
4問目
グラフは得意なので、解きます。 ここら辺が一番眠くて、眠気覚ましのぬれタオルを首にかけるのが苦痛だったので外した。 そうしたら余計眠くなって、去年の落ちたときと同程度の集中力になった。今思うとここら辺が一番まずかった(多分ここでこのままだったら落ちていた) stを反転させた場合、tsを使う最短路と1Nの最短路のminなのはそうと思ったが、1Nの最短路で反転させた道を通っていた場合でどう処理すればいいのかが分からなかった。40分考えたが何もわからず、飛ばす。
3問目
ここで5に行かなかったのは英断。 ちなみにこの時点で4回くらいトイレに行っている。後半はトイレに行くたびに毎回顔を洗って目を覚ましていた。 眠け覚ましと称して買った綾鷹をかなり飲んでいたので、そのせいもあって間隔が短かった。 トイレに行く間隔が短すぎやしないか、チューターに迷惑が掛からないかと思い、20分以下とかで再び行くようなことは避けた。
どうせN3乗DPなので、dp[i][?][?]で、iにいて、?で?な時の状態を示す、と考え始めた。 時間Tiがどうしても必要だったが、これは添え字に入れないでと強く主張していたので、入れ替えをすればよいと思いつく。 次に、次の遷移は今の区間をまたがるか次に進むだけかの2択だと気が付いたので、それで添え字が埋まり、解けそうだったので、dp[i][j][k]=iにいて、反対側の端っこがjで、今までにスタンプをk個おした時の最小の時間として再帰関数に突っ込む。 混乱して、ループじゃないとできないことに気が付く。 ループに書き直し、100行くらいの面倒くさい遷移を書いた。サンプルが合わずバグ埋め小宮になってしまった。
ここらへんでタオルを首にかけた状態でたまに顔に当てたりすると良いことが分かり、それを定期的にし始める。居酒屋によくいるおやじみたいだ。
バグの原因が、0を跨がない区間の存在だと気が付きそれを修正したコードを書く。
ここらへんでタオルを頭にのせているといい感じに目が覚めることに気が付いたので、本選会場に狂人が出現する。 パソコンを触っているにもかかわらず頭に謎の白い布をかぶっていた妖怪がいましたね?あれは僕です。
バグった。0が端の場合にどっち側の区間だかわからない。0の時だけ特殊処理すればいいかとも思ったが、面倒だったのでどっちにいるかをつけ足してコードを修正する。 これでサンプルが合い、投げたら1発ACしてフィーバーし、本選通過を確信。 とはいえ、一昨年の本選みたいに自明を取らずに落ちるのは悲しすぎるので、4の部分点を取り始める。
5点は2回ダイクストラ、11点はベルマンフォードやるだけだったので11のほうが簡単と思いそっちをやったが、添え字をバグらせて(fs.fsとsc.fsの区別つきますか?つきませんねありがとうございます)、ついでに「高々1回」を見逃して、ans初期値がinfだったので時間をだいぶ溶かした。KCLCをするところだったの、冷や汗。
これを直して投げて11点が来たのが終了5~6分前とかだった気がする。本番はあまり思ってなかったがかなり危なかった。(まあバグの原因には何となく想像ついてたし、投げれば通るという確信はあったからそんなに危ないわけでもなかった) これでダイクストラを書く時間がなく終了、311で通過を確信。
naoki2016が襲来、3完部分点仲間で70からは暫定二人と思っていたところにdefineとkaageが襲来、3完したーとか言っていてついでに点数で負けていたので、「あ、これ落ちたのでは?」と思い始める。
全列挙のところに行くと2完部分点といっていたので、一緒に葬式を開催した。
うなぎのところにいったら3完は通るといっていたが、5分5分で落ちると思っていたのでお通夜を開催した。
昼食の時間。前のほうで人々が集まっていたが、3完が25とかいたら落ちるのが確定なので、結果を知るのは後にしようと思っていかなかった。 物理好きが死んでいるのが意外だった。 交流をする体力が尽きていたのもあり、naoki2016と競プロとほぼ関係のない話をしていた。
ほうじ茶が熱すぎて、飲もうとしたらこぼした。あれは闇討ち。
机と弁当箱(外だけ)とズボンが結構濡れて、あーこれはやっちゃったやつですねぇ、とか思ったが、疲れていたのと、放っておいたら乾くと思ったので放置した。
解説の時間。 123は分かっていたので半分くらい聞き流し、大量の「人」の中から特定のフォントの者を見つけるというゲー無をしていた。 4は聞こうと思ったが集中力絶滅であまり聞けず、5は話は面白かったが問題読んですらいないので聞き流すようにした。 3の解説で3完23人、300301305を知っていたので通過を確信した。 この辺りが疲れ果てのピークで、通過してもうれしさよりも疲労感のほうが強くて、少し意外だった(もう少し嬉しくなると思っていた)
帰る。 前のほうを全列挙うなぎが歩いていたが、疲れて追いつく気力がなかったので見なかったことにして(途中で合流したがすぐ離れた)駅まで行き、そこでTAISAsinatoriと遭遇、TAISAが336ではい、sinatoriが本選落ち。難易度10で解けないの埋めたりしていてこれはやばいなーと思っていたので、かなり意外だった。すごく辛そうだったが、初めて1年で難易度10解いていて春視野に入っているのがそもそも異常なので、このまま頑張ってほしい。 その後いつものと合流、うなぎが3つ隣の席で古文単語をしているのをみて現実を思い出した。
総括
行った眠け覚ましは、①前日たっぷりねる②チョコ食べる③当日風呂入る④当日外散歩する⑤濡れタオル頭に置く⑥トイレで顔を洗い続ける
去年落ちた原因、とはいかないまでも2完もできない原因は眠気にあったと思っているので、その対策がばっちり…ではないが、通過レベルでできたのは成長を感じる。 成長ではなさそう。単に対策を練れただけっぽいが、去年の落ちを無駄にしなかったのは良かった。
三銃士+sinatoriのポスト異常勢が落ちていたのが意外過ぎた。
とはいえ、僕もぬれタオルとその他の運がなければ落ちていて、単に運が良かっただけなので人のことは全く言えない。 というかあれで落ちていて僕が落ちていないのが不思議なので、通ったと慢心しないでしっかりと10梅をしていきたい。