Give us sociability (Kattu, Hyado, hotman) で組んで出場しました。
全体18位/学内1位で、今年もアジア大会へ進出できることになりました。
当時の記憶が薄れてしまったので、順に書きながら思い出していこうと思います。
チームメンバー紹介
かっつ…研究に追われている。最近競プロに取り組めていない。
Hyado…院試対策/研究に追われている。最近競プロに取り組めていない。
hotman…学業に追われている。最近競プロに取り組めていない。
ICPC前流石にこれはマズいよね、みたいな空気感はチーム内で漂っていた。
模擬国内予選*1
確認したら現役内では17位で、学内3位だった。
ただでさえ弊チームは実装に苦手意識のある人間が多いの加え、競プロから離れて更に実装力が低下しているのが課題*2だなと改めて実感したのを覚えている。
完数が同じで時間差で同大学チームに負けるのはかなり想定内で、想定内だけど(良くないよね/でも3枠通過ラインには入ってるのは良いね)みたいな感想だった。
Hyado→A問題、かっつ→B問題、hotman→D以降得意そうなの特攻、というチーム方針はこの時から採用していた。
ICPC1週間前
流石に実装力の低下が著しいので、慣れを取り戻そうと、Hyado君と2人でICPC前にコソ練5hを何セットか回していた。あまり記憶なし。
僕が担当した問題で一番記憶に残ってるもの↓ 構文解析最高！！！
ICPC前日
give us 3人が誰も解いてない550~700ぐらいの問題を乱数で20問ぐらい詰めたセットを作った。明日まで埋めたり埋めなかったりします。
https://onlinejudge.u-aizu.ac.jp/services/room.html#give_us_virtual_20220707/info
並走歓迎です
かっつ「Infallibly Crack Perplexing Cryptarithmの実装に3億年かかってて明日がもう不安になってきた」
noimi「わてもです」
読んでみると分かるけど、考察要素0の本当にやるだけ構文解析なので不安が募った。
完全に僕の思いつきだったけど、チームメイトも2問ずつ参加してくれて良い話。
ICPC当日(朝)
直前特有の実装モチベの高まりを感じて、適当に1問解いて寝ようと思った。WA地獄で睡眠に失敗した。結局朝9時ぐらいに就寝。
ICPC本番
睡眠失敗したものの、昼過ぎには起きて16時頃大学に向かった。
僕の借りた部屋が51号館の8階でアクセスが悪い場所なのに、本番前にコーチのはてぃさんが差し入れを持ってきて下さって無限感謝編となった。
毎年恒例(？)の早稲田ICPCチーム同士でお菓子渡し合う文化*3、見てて笑顔になるから続いて欲しい(？)
俺も毒入りチョコ貰った pic.twitter.com/eOCSIF2Za0
— かっつ (@_KKT89) 2022年7月8日
毒入りチョコを身内に渡すなよ。どうせ16時半には始まらないだろと高を括ってたら、普通に始まったのでビックリした。ということで本番開始。
コンテスト
練習通り、HyadoがA、僕がB、hotmanがDという配置となった。
Bの問題文頭に入らなくて焦っているうちに、Hyado君がAの実装を終えていて助かる。僕も題意を理解し、やるだけなのを確認。
A問題 AC(2:40)
Bの概要は、1人2枚だけのカードを持ったババ抜きのシミュレーション。
最初から揃ってる場合を予め除いておけば、カードを受け取った時に揃ったかどうかを確認するだけで良い。計算量はあまり気にしなくて良さそうなので、基本的に愚直を書いて良さそう。
初めはstd::setで書いていたが、どうせ計算量気にしないならと2次元vectorでの実装に切り替えた。その後も軽微なミスを重ねたものの、無事通すことができた。
B問題 AC(11:17)
出遅れた自覚があったものの、いざ順位表をみると全体2番目でびっくりした。
先日のアジア地区予選の際、順位表観戦しながらスクショを残してくれていた友人が、今回は時計付きで順位表の録画を残してくれていた。出来る男すぎる。持つべきはICPCに理解のある彼くん。
この時点でCが多く解かれている。
A終わりのHyado君がCを読んでいたが、考えていた解法が嘘だったらしく僕にHELPを投げてきた。問題文を読むと、明らかに苦手そうなタイプの問題で嫌な気持ちになる。他の参加記を読んだら、C難しいって言ってるの誰もいなくて泣きました。
実験コードを書くが何も見えない。その間にもCは次々と通され焦る。
チームメイト何とかしてくれ！という気持ちを抱えつつ、話してみるとHyado君の頭がバグってそうなので(失礼)、自分が何とかしないといけないと覚悟を決めた。
冷静になると、練習日が連続する区間の数を決め打つと、休養日は均等に分けるのが最適となる。練習日に関しては1個に集中させるのが最適となるのが簡単に分かるので、後はこれを全探索すれば良かった。
C問題 AC(51:53)
順位表の途中経過見ると、本番当時の緊張感というか絶望が蘇ってきて良いな。
チームとしてはhotman先生がDで2ペナを生やしていて、その救援にHyadoが向かったという経緯があった。
僕もDに合流し、取り敢えず愚直解を書くことにした。愚直解が一致せず？？？になってhotman先生に確認しに行ったら、問題文の誤読が発覚。
愚直が完成し、このタイミングでhotman先生もミスに気が付いたらしくコードが完成する。2ペナしてるし、愚直と付き合わせてから提出しようということで僕のコードを渡すが、hotmanの環境で大量のエラーが出る。
modint周りの引数のエラーと聞いて納得するも、修正を加えてもまだ大量のエラーが出ててシンプルに何でやねんという気持ちなった。
もうそのまま出して良いなという気持ちになり、お願いしたら無事通った。通ったから良いものの、この辺が出来ないの、チームとしてはとても良くない。
D問題 AC(1:27:36) +2
MSBすごい。give usもかつては早解き逃げ切り型のチームだと思ってた(思ってただけ)のに、序盤のスピードはMSBに勝てなくなってしまった。
ペナが終わってるので勝ち筋が、+1完以上する or 早稲田他チームがとんでもなく冷える、のどちらかだなという気持ちに。
UH_ISSyがDで苦しんでいそうなのを見て、ワンチャンある？と思ったけどそう甘くはなかった。自力で+1完しないと敗退という状況にこの時点で追い込まれる。
Dが解決した後、僕はEを読んでいてフローっぽいけどフローじゃないなぁと考えていると、HyadoからF問題が阪大のGirigiri_yellowsに早い段階で通されてるので可能枠なのでは？(あと見た目がかっつ枠)と言われ、Fを見ることに。
と言っても構文解析パートはかなりおまけで、考察が本質っぽい。
辞書順が最小になるように毎回操作を行うのは流石に嘘っぽそうと思いつつ、サンプルを確認するとちゃんと嘘だった。
しかし、操作の方法に依らず得られる文字列の長さは一意に定まるので、次のように文字列を分解した場合(足し算と呼んでいた)それぞれ辞書順最小となる結果を足し合わせて良い、という考察をしていた。
?(bca)?(?(bca))a
→ ?(bca) + ?(?(bca)) + a
ここで詰まっているとhotman先生が、前後で何文字削ったか？を状態として持ったDPを考えれば良さそうと教えてくれて、天才？？となった。
あるvalidな区間について見る時、前後で何文字削るかさえ分かっていれば、上記の場合と同様に貪欲な操作に帰着させることができる。状態数も多分2乗オーダーで抑えられている。
文字列 $s$ に対して、前 $a$ 文字、後ろ $b$ 文字削る場合の、辞書順最小文字列を $f(s,a,b)$ とおくと、
s = ?(abc)b?(dc)
s1 = ?(abc), s2 = b, s3 = ?(dc)
f(s,1,1) = f(s1,1,0) + f(s2,0,0) + f(s3,0,1)
のように分解して考えることが出来る。括弧が来た時は2通り試して良い方を採用する。ここまで来れば構文解析をしながら、メモ化再帰を実装するだけ。
時間は十分残っているように思えた。これを通さなければ敗退。しかも自分が力を入れてきた構文解析の問題。通せなかった時の不安か、この状況に対するワクワク感か、フワフワした感覚で実装を進めていった。
終了30分前、一通りの実装が終わる。しかしサンプルの実行が終わらない。
チームメイトとコードを共有すると、Hyadoが無限ループとなっている箇所を指摘してくれた。本来は変数のインクリメントをしないといけない場所が欠けていた。
サンプルの実行が無事終わり、祈るような気持ちでテストケースを回し始める。1ケース目の実行で止まる、そんな…。
計算量的な問題か？と思って試すが、どうやら無限ループに陥ってるようだった。どこだ……という気持ちになり、1人で悩んでいるとコードを共有してくれと言われたので(そりゃそう)、状況を説明してコードを渡した。
時間が無くなってきた焦りでHyado君にキレ散らかしていて*4、もしこのまま終わってたら雰囲気最悪だったな。
hotman先生が僕のコードを読解して、メモ化再帰周りのバグを見つけてくれて感謝でしか無かった。メモ化に使う引数を関数の中でイジってバグってた。
これを修正すると、今度こそテストケースの実行が終わった。これで終わってくれと提出ボタンを押すが、
F問題 WA(2:42:12)
かなり絶望的だった。が、提出した実行結果を見ると空文字列があり明らかに怪しい雰囲気を感じる。これかなりマズくない？と話になるも、
かっつ&hotman「いや、文字列の結果が空になるのは普通に有り得るしな…」
Hyado「正しい出力は空文字列にならないことが保証される．」
かっつ&hotman「天才」
空文字列にならないものが、空文字列になっているということは、デバックの対象はかなり限られた範囲になる。それもhotman先生は分かっていたようで、遂にバグが見つかった。
それは文字数をカウントする際のミスだった。文字数から括弧の数を引いて求めていたのだが、例えば次のケースで墜落してしまう。
?(aaa?()?()?())
対策が分からず途方に暮れていると、hotman先生が実装方針を教えてくれて、というか俺書いてみるわと言って程なくコードを完成させてしまった。実行させてみると、空文字列が消えている。
文字通り、祈りながら提出画面を見ていた。
Correct Answer
この文字列が見えた時のホッとした気持ちは忘れられない。ただ、まだ歯茎を見せるな！という気持ちで2ケース目を見守る。見守っていると、Hyadoにかっつは出来ることやってて大丈夫と言われるが、何もやる宛がなかった。
F問題 AC(2:54:10) +1
競技プログラミングやってきて一番興奮した瞬間だったと思う。
達成感で何も考えられなかった。まだコンテストは終わってないが、これで予選敗退になるならば未練はない、そんな気持ちだった。
Fと格闘していた時はあれだけ早く感じた時間が、本当に長く感じた。
そのままコンテスト終了を向かえ、改めてチームメイトと喜びを分かち合った。
終わり
最終結果は全体18位。5完の中では最下位だった。ペナが終わってる。
+1完を拾わないといけない場面で拾えたのは、2年前のICPC国内予選の反省*5を生かせていて良かった。しかも最後のF問題はチーム3人で勝ち取った部分が大きく、満足いく結果だった。
特に実装に不安を抱えていたhotman先生が、並列実装を担当してくれたり、デバックを担当してくれたりしたのが本当に大きくて助かった。
何事も無ければ僕は今年でICPC引退なので、引退が長引いて嬉しい。次のアジア大会までまた頑張ります。
勢いそのままに書いたら滅茶苦茶長くなってしまったんですが、校正する気力が残ってないのでこのまま投稿します。人に読ませる文章、上手くなりたい…
*1:毎年参加記は絶対書いてたのに、研究忙しすぎて書けてなかった
*2:hotman先生が素因数分解を長時間バグらせててマジ？ってなった
*3:Hyado君はチョコ食べられず、hotman先生は持ち帰りにくそうな顔をしてたので僕が大量のお菓子を引き取ることに。ありがとうございました
*4:普通に実行終わったよって言われ嘘？？？となったらサンプルの話だった→テストケース1個目で落ちてるみたい→(ずっとデバックしてる関数について)ここで無限ループしてるみたい、と知ってる話を3連発でされて渡した時点でその段階だわとキレた
*5:僕がD、hotmanがE、Hyadoが余ってFを担当した結果、+1完出来ずに敗退した。Dの構文解析の考察パートをhotmanに、Eの考察後の実装パートを僕が担当するべきだったなという反省
