ICPC国内予選2020 参加記
チームUHISHIROとしてsuta, shiro, kiyoshiの3人で出場した。
コンテスト前
勝利祈願
アジア行くぞ!!!!! pic.twitter.com/CdX79tGo8n
— suta (@suta28407928) 2020年11月6日
模擬国内ではCで2時間バグを埋め込んでいたので、本番は炎上しないことを最優先にする意志を固めた。
15時くらいからコンテストまでの時間は幾何ライブラリの確認やFox observationの愚痴を言っていた。そんなこんなするうちに
コンテスト15分前くらいになっていたので、呼吸を整えて…コンテストのURLはリハと同じ…
コンテスト本番
F5を押すと謎の画面が出てくる。チームメイト全員そうらしくてかなり焦った。
運営にメールと電話をしてもダメで察したので、連絡担当 : shiro、リロード担当 : suta, kiyoshiに分かれた。これがチーム戦(?)
10分経つと問題が開けたので A : shiro, B : suta, C : kiyoshiで問題を読み始める。
Aをshiroがあっさり通し、Bは読解が終わると考察も実装も簡単でびっくりする。これ本当に国内Bか? すぐ書いてAC
kiyoshiがCの解法をすぐに思いついていてすごい。shiroからDの問題文概要を聞き、把握に苦戦しながらもなんとか理解する。
するとCの実装をしているkiyoshiが唸っている。二分探索のコードで
while(ok > ng){ ll mid = (ok+ng)<<1; if(f(mid)) mid = ok; else mid = ng; }
と書いていたらしい(どこが間違っているか探してみてね!)
これがICPCの恐ろしさか…(いいえ)
修正すると難なくAC。この時点で8,9位だった気がする。
順位表を見るとライバルチームのRamen as a ServiceとGive us sociabilityとほぼ同列で、DとEの勝負だねという話になる。
(コーチyamadさんのツイートから引っ張ってきました)
Dが階乗はまずいので、多分bitDPなんだろうと思って考察するが全然遷移が思いつかない。きよしがE解けそうと言っていたが、計算量が厳しそう&TLE解法でも
実装が軽くないという感じですぐにはACは無さそうという感じだった。
30分くらいDとEを反復しても何も分からない。解法っぽいことを言う→1秒で棄却→「分からねえ~なんだこれ」を連呼するを繰り返していた(真面目にやりましょう)。
kiyoshiが分配法則が成り立つらしいことを発見したが、それから先も長そうに感じて気が遠くなる。
それからEをkiyoshi、Dをshiroとsutaで詰める。
Dの構文解析パート&階乗全探索をshiroに書いてもらい、ほどなくしてサンプルが合う(すごい)。
しかし全然解法が降りてこない。他のチームはもうDかE通してるのかなあ…と思いながら申し訳ない気持ちになる。
気分転換にトイレに行く。なんか頭がすっきりして解法っぽいものが生えた気がする。帰ってshiroに伝える。→嘘だった
すると次はshiroがトイレに行くらしいので、「アイデアよろしく~(他人任せ)」と言いながら見送る。
shiroが帰ってくると何か思いついたらしく、
shiro「文字決め打って、その前後の文字を上手く決められないかな」
と言い始める。これが大当たりで、
suta「それ各文字について、その決め打った文字より前か後ろかをbitで全探索できませんか」
shiro「え、それじゃないか???」
suta「天才!!!!!!!!!!!」
確かにある文字より前のもの同士演算されてもある文字より前に決まってるし、後ろも同様。勝ちました……… お通夜の雰囲気だったのが一気に明るくなり、即実装を始める
shiroが「ただ場合分けが必要そう」と話していた。が全くshiroの意図が理解できなかったのでとりあえず実装する(ごめん)。
実装している間にshiroが気付いたらしく、どうやらshiroが思っていたのとsutaが思っていた解法が違ったらしい。嘘解法を伝えたら正しい解法が伝わった最高のパターン。これがチーム戦(??)
すぐに実装が完了したがバグっていそう。と思いきやサンプル1の1通りの列挙が間違っていた。サンプルが合う。心臓バックバクの状態でsubmitして、AC。しばらく発狂してた。
Dでそんなこんながあったうちに、Eもオーダーが落ちたらしく、kiyoshiが書いていたがバグっているらしい。Eを絶対に通そうという話になり、全員でコードを見る。が何も分かりませんでした。ごめんなさい。
しかしshiroと共にkiyoshiに質問を投げると、自分で説明しながらミスに気付き、修正し始める。それを繰り返すうちに考察と全然違うコードを書いていたことに気付いたらしく、それを修正するとサンプルが合う。もうお祭り状態。submitしてAC。暫定14位で通過を確信していた。バグっている時に質問を投げるの、かなり大事かもしれない。
興奮で頭が働かない中、Fを読む。きよしがすぐに二乗解を生やしていて書いていたが、時間切れ(sちょうどと誤読していたらしいが、s未満でも二乗解なら時間があれば書けると言っていた)。Fの問題文をもっと早く読んでいれば解けていたかもしれないが、DとEで手一杯だった。
結果
5完で全体17位、早稲田内1位で予選通過!!!!!
勝ち目は薄いと思っていたので、本当に嬉しい。チームメイト、本当にありがとう…
おまけ
ya〇adさん(鍵)のツイートを見ると、DとEのACした時刻が分かる(鍵なので誰のツイートかは伏せます)
この他にもUHISHIROが言及されているツイートがたくさんあって嬉しかった。
コンテストのラスト、kiyoshiがFを書いている間に順位表を眺めていたんですが(おい)、順位表のUHISHIROの真下に「suta」が見えて一瞬びっくりしてしまった(tsutajさんの連続する部分文字列だったことを初めて知りました)。なおチームtsutajにtsutajさんは居ないらしい
今後
横浜大会は初めてなので、良い成績が残せるように精進を頑張る!!(学業さん…)
まずは黄色を安定して維持できるようにしたい。