beet's soil

競プロのことなど

ACM-ICPC 2018 国内予選 参加記

9th 大学別4th うくさんが悪魔的行為でもしてなければ通過するはず。。

コンテスト前

僕がA解いてる間にうくさんがB、はじさんがCDを読むことにした。
E以降は全員読む 実装は基本僕がやる くらいを決めていた。

コンテスト中

A
やるだけだったぽい(すでに記憶にない)書いたら通った
B
うくさんが読むだけと言ったので読む
最近AGCをやっていたため逆から開いていく方針を立ててしまう
まあ橙コーダーなのでキレながら実装をする バグる
サンプルを見ると半分以上の位置でおることを想定してなかったことに気づく
いやな気持ちになったので一旦捨てる
はじさんに時間かけていいからバグらない方針を作ってと言って投げる
C
はじさんがやるだけと言っていたので読む やるだけ
式を立てるのが面倒だったのではじさんのメモをもらう
サンプルが合わない 式が間違っていた キレる 直す 通った
D
はじさんが「びーとくんがやるべき」と言ったので読む うーんこれはICPC!w
計算量に想いを馳せると国内予選なので間に合うことがわかる 書く 通る
B
はじさんがクールな解法を立ててくれたので書く
indexミスってサンプル合わなかったけど適当に+-1して I got a kotonaki. 通る

まあ4完速解き成功して通過でしょみたいな気持ちになる
priMe.caT に負けていてもう一問解きたい気分

EFGHを読む Hがフローっぽいらしくてうくさんが考えてた(フローではなかった)
後半に重いやつがまとまっていることにうくさんが文句を言ってておもしろかった

Eのサンプルの読解をはじさんに投げる
Fは二分探索+二点決めうちでO(N^3 log EPS^-1)を思いつくがさすがに無理なのでやめる
Gは無限時間あればできそうだねという気持ちになる

Eのサンプルの説明を聞く なんかわかってしまえばそんなめんどくさくなかった
適当に関数分けして書く 通った Bより実装軽いんですがそれは…

Gくらいしか解ける気がしなかったので考える 
明らかに剰余体でhashとってmap DPするしかなさそう
hashの関数を写経してもらってる間に実装を紙で詰める
全然サンプルが合わなくて焦りながら無理やり合わせる
残り1分切ってるなかデータダウンロードして提出したけどWA かなしいね

感想

今年は順当なICPCだった 大学別4thが安定していてWFが微妙…
(海外オンサイトで狙うか謎枠使うしかなさそう)
もっとグラフを出してくれないとうくさんが冷えてしまう