siro53, suta, kiyoshi0205の3人のメンバーでチームUHISHIROとして出ました。
結果は 全体17位 / 学内1位 で国内予選突破、アジア予選進出です! 模擬国内では予選落ちの結果だったので、とても嬉しいです!
以下参加記です。
本番前
緊張で全く眠れず深夜4:30頃に就寝したためかなり睡眠不足を感じる。
12:30頃に大学に到着し、チームメイトとともにリハーサルを済ませる。
リハーサル全完したら昼飯を食うことになっていたが、kiyoshi0205が鎖中経路を通すのに苦労していて遅めの昼食になった(通していてすごい)。
勝利祈願🙏🙏🙏 pic.twitter.com/tFlNhDBLty
— shiro (@shiro537) 2020年11月6日
本番前に再度必要なものが足りてるかどうかチェックをし、序盤担当することになっていたA問題を高速に通すイメトレをしながら、ついにICPC2020国内予選スタート...!
本番
F5を叩きコンテストページをリロードすると、
no status information for team 459743 in contest are found (database broken or not initialized?)
というメッセージが出る。え?え?え????なになになになにこれこれこれこれ
チームメイト3人とも問題が見れないようで、激焦りする。これが原因で予選敗退はかなり嫌なので、本部にメールを送信したり電話をかけたりしたが、繋がらない。どうやら全チームトラブってるらしい?
依然として混乱するが、kiyoshiが突然「(コンテストページ)開けた!!!」と言うので急いでF5を押すとなんかリハーサルの問題が表示されている(???)
ワクワクがすぎるが、とりあえずチームのうち1人がページの更新を確認しつつ僕がメールを確認し続けていたりもう一度電話したりしているとついに問題が見れるようになっているので急いで取り掛かる。
Aを見る、やるだけなので僕が通す
Bも簡単らしい、sutaがササッと通す
Dを読んでいると、Cを取り組んでいるkiyoshiから「え、ポラド・ロー?」とか聞こえてくる。不穏なので一旦kiyoshiに問題と解法を説明してもらうと途中で
「あ、にぶたんでいいじゃん」
と言い始める なんかよく分からんけど解けたらしい...
kiyoshiがめちゃくちゃ緊張してて手が震えており、バグらせていて傍から見ても精神状態がヤバそうなので、急いで駆けつけて後ろからコードを見て一緒にデバッグすると、幸いすぐに自明なバグが見つかりCが通る
このタイミングで順位表を見ると僅差で他の弊大学のライバルチーム(Ramen as a Service, Give us sociability...)に勝てており、D、Eが早く通せるかの勝負になると思ったので全力でD、Eに取り組むことにする。
Dは読むと構文解析で、とりあえず$n!$通り愚直に調べれば答えは出せるが、$n\leq 16$なので当然間に合わないのでどうしようとなる。構文解析が本質ではない問題っぽい
Eは数え上げ、ICPC国内予選で数え上げって珍しくないか?こういう問題は絶対kiyoshiにやってもらった方がいいんですね~とか思う
Eの問題概要をチームメイト2人に伝える。kiyoshiがパッと解法を出していたがオーダーがヤバいらしいのでダメそうとなる
Dはとりあえず変数の関係を書き出すとトーナメント表(木)になってるね~と言うけど特に進展はない。kiyoshiが「これは分配法則が成り立つ」とか言ってたけどその方針で突っ走るとどう考えてもヤバそうなので、別の解法があるんじゃないかと疑う
ここから暫く、Eをkiyoshiが1人で考察し、Dをsutaと2人で考察する流れになった
Eはkiyoshiがうんうん悩んでいて、Dを僕とsutaで取り掛かるも、本当に何も糸口が見えない このままD、Eをみんなに通されて終わってしまうのか・・・
かなり暗い雰囲気になりかけていたが、ここでsutaが「完全に煮詰まったからトイレ行ってくるわ」と言う
どうやら国内模擬の会津大学のbeetさんのチームの参加記のことを言ってるらしい(バグで完全にハマってしまったチームメイトに対しトイレに行ってもらって一旦リフレッシュしてもらうことで、思考がリセットされてバグが取れたという記述があった)
確かに今完全に煮詰まってるし俺も後でトイレ行こ~とか思う 結局構文解析しながらdpするのはつらいし、やっぱりSとTに対して最終的な結果を固定したいよね~とか考えてウンウン唸る
暫くするとトイレから帰ってきたsutaがトイレしてる間に考えてたことを伝えてくれるも、う~んとなる
次は僕がトイレに行く番なので、トイレに行く。(最終的な状態を固定した時、そいつの後ろにあるやつと前にあるやつはそれぞれ自由に並べ替えても結果は変わらなくね?それ構文解析しながら前と後ろにいなきゃおかしい文字を調べられないか?みたいなお気持ちをsutaに伝えると「え、かなりそれじゃないか?」みたいな話になる
ここから2人のテンションバク上がり
どのタイミングかは忘れてしまったが、kiyoshiもEの解法が思いついたらしい(実装が大変らしい)
ただ、なんか微妙に最後の数え上げパートで2人の意見が食い違う 色々話すがどうしても噛み合わない
(よくわからんけどこういう時はレートの高い方の意見が正しいやろ!w)と思い、sutaに実装をお願いすることにする 僕はどうして話が噛み合わなかったのかを再度考察し直す
暫く考えると、自分の考えてたことが微妙に嘘であり、bit全探索が必要であることに気づく 急いでsutaにそれを伝えると
「え、最初からそういう話じゃなかったの?」
どうやら自分の解法の伝え方が下手すぎて、逆に正しい解法としてsutaに解釈されてたらしい
なんだこのチーム 解法伝達が上手すぎるだろ・・・
完全にsutaの意見が正しかったしやっぱりratismなんだよなとか思う 少しバグるが、Dのサンプルが合う。発狂 Dが通る 最高
めちゃくちゃテンションが上っていると、Eの実装がかなりお通夜になってるっぽい
まだ逆転される可能性があるので油断はできない。解法は出てるしEを通せばほぼ勝ち確だと思い、3人全力でEのデバッグをする
Eの解法の説明を受けるが、僕もsutaもDで興奮しすぎて何も頭に入ってこない 何もわからないのでsutaと一緒に1行1行「これは正しい?」と質問攻めにする
kiyoshiは僕たちに説明してるうちに思考が整理されたらしく、落ち着いてゆっくりコードを修正する
全ての修正が終わってサンプルを試すと、サンプルが全て合う(!!!)
1ケース目が通った時は3人かなりうるさかった気がする。2ケース目も通り、無事5完! 3人でめちゃくちゃ喜びました
Fを3人で読むと、1010ならすぐ解ける問題っぽい?Fがめちゃくちゃ通されてるのはそれかな~とお話ししたり、Fの愚直の実装をしたりしているとコンテストが終了しました
感想
振り返ると、かなりチーム連携が上手くいったなと思いました。模擬国内の結果を見て通過できるかどうかかなり不安でしたが、チームメイトが心強くて本当に助かりました。
現状かなり自分のレートが停滞していて、チームメイトにすごくレートを離されているので、アジアまでにはなんとかしたいです。切実に・・・
アジアで恥ずかしい成績を取らないように、より一層精進したいと思います。