はじめに
最初はそんな真面目に参加記を書くつもりはなかったんですが、配信を見た時にあまりにウチがどうなっているか分からなかったので、起きたことを書いておこうと思います。
メンバー:
ひらきち = sheyasutaka AJO出場、非常に強い。
自分 = physics0523 各国のサイトで暴れている、まぁまぁ強い。
自分は他の 2 人よりは難問に弱く、奇問に強いという認識をしている。
謝罪
Registration を 14 時から 15 時と勘違いしていて ( 正しくは 13-14 ) 、大阪駅で勘違いを修正しました
大巻きしたんですが結果 13 時 58 分くらいの到着になってしまいました ネッコアラとコーチの moririn さん、スタッフの皆さん、本当に申し訳ございませんでした
ひらきちも 2 時間 30 分くらい遅刻しました 本当に申し訳ないです
これ以上謝ってもしょうがないので、ここからは競技の話をします
開始直後
横浜の開始布陣は基本固定で、自分が簡単枠を (考察から実装まで) やってひらきちにCから、ネッコアラに後ろから見てもらうという流れです (自分の難問力は 2 人に劣っていると思うので、分かっている簡単な問題でこの 2 人を消化するのは勿体ないので)
なので、まず A を見る。 $O(N)$ を一発で合わせる自信があまりにもなかったので $O(N \times A_i)$ で戦略的 AC (7min) 。次に B を見る。数分考えて解法が思い浮かんだが、怖かったので愚直解もパッと書いて比較。この時点でさっさとマシンを開ける意味がそんなにないので、 20 分のペナを回避するために 2, 3 分使うのはまぁやってもいいだろうと簡単なストレステストをした上で AC (15min) 。この時点で 5 位、悪くない開幕でしょう。
出火
基本的には、この後自分も問題を読み始めて AC の多い、かつ(原則)今誰も取り組んでいない問題から遊撃するが、今回はこの時点で順位表情報がない。まぁ他の問題をちらほら読み始める。この時点で F がさぶたんableかつ地雷なので実装 queue の奥底に沈めるべきということは 2 秒くらいで悟っていた。
この時点でネッコアラが K を解けていたので実装をしてもらう。しかし、その実装過程で出火。いったんひらきちにマシンを明け渡し、 E を AC (47min) 。その後、ネッコアラが K を sub し 1 被弾。その間、自分は I を見て「あぁ、 Mo やるだけだなぁ ぶつを」という気持ちになっていた。そしてマシンを貰ってぱぱっと Mo を書いて Ac......... TL と言われてしまった。はい、 I も出火です。 Penguin Feeders が 24min で通してるのを見て、「絶対解法は単純なはずなんだよな…」という気持ちがこの後1時間半くらい自分を縛り付けていました。
ここでネッコアラにマシンを明け渡し、なんとか K を AC (78min) 。ここまでで 2 つ火柱が上がっており K が通る直前に一時 16 位だったらしい。普通にシンガポール旅行キャンセル覚悟してました。
その後、自分とひらきちが見て混乱していた C をネッコアラに相談すると「最短経路木やるだけ」と言われてしまい、そのまま AC (95min) 。天才か?
その後、ひらきちが G の考察 / 実装を始めたが、これがまた非常に重く、まぁ出火。他のチームを見た感じ、この出火は経費。このへんまで Reharsal に間に合わないレベルの遅刻をカマしたひらきちが G の local tester の usage を知らず、「遅刻って本当に不利益生むんだなぁ ぶつを」になりました。
中盤
この辺の時間帯、 3 人が独立に異なる 3 問でハマってて本当にヒヤヒヤしました。競技画面の Home に常に 2, 3 個赤い四角が並んでるようなもんです。強心臓じゃないと耐えられませんよこんなもん。
ネッコアラが L の実装を始めたが、 1 被弾。その間、自分が隣接する $d$ の倍数のみを着目する感じの平面走査 (+枝刈り) に切り替えた I を実装。計算量が $O(Nd(A_i) \log N)$ だったのでま～～ぁ頭抱えましたよ。いくら 4 秒でも信用できるかよこんな額面計算量。定数倍に滅茶苦茶気を遣いながらなんとか実装して AC (155min) 。直後、ネッコアラも L を修正して AC (161min) 。一気に 5 位まで浮上。(まぁこの時点でもここから何も通らなかったらシンガポール旅行は没収だなぁと思っていました)
ここで、 D が通りまくっていることを念頭に D をネッコアラと自分の 2 人がかりで取り組むことになる。ネッコアラは「マージ過程の木」方向で、自分は「対応する括弧を区間に帰着する」方向で考察。その間ひらきちは G の実装で 200min 頃に最初の attempt 、 WA。
ひらきちが実装で激ハマりしている中、自分とネッコアラは D に弄ばれていた。自分は「ネッコアラと(一瞬くらいは取り組んでいるであろう)ひらきちとをもってしても刺さる数え上げ… この 2 人、 AtCoder で max2800+ と 2700+ が解けてない数え上げが俺に回ってくるのは非常にまずい！！！！！！！！終わった！！！！！！！！！」くらいの気持ちでした。順位表で通りまくる D 。数え上げ強豪ふたりが苦しんでいるかもしれない恐怖。血の気が引きました。
ここで、天啓が降ってきます。 $[l,r]$ に対応する括弧は $[l,r]$ だけを見た時に木を成すことを示唆することには気づいていたので、全ての $[l,r]$ をビジュアライズした図と生成される共通の木とを頭に浮かべながらそれっぽい予想を捻り出します。
最初、こんな感じの謎の図を書いてみたところ、これがサンプルで棄却されませんでした。ネッコアラにこれを話したところ「全く分かりませんw」と言われてしまった。そうですよね、これほぼ陰謀論ですよね。これを Attempt して WA 。
この時点で、 7 完 11 位、 DG が赤いまま凍結を迎える。
ラスト1時間
時は少し戻って 220min 頃、さっきの予想を棄却した方がいいと言われながらも「サンプル全部通るし(ネッコアラに指摘された)木が1つの場合もだいたい通りそうなので、これに近い何かがあるはずだ」と思いながら、先ほどの予想に反例を発見。 ((11)(11)) にて現状の予想だと $3$ になってしまう。
しかし、先ほどの予想を少し修正して、「各赤線から緑と青の各数字への『距離』のようなものの積の総積」と修正すると、このケースを含め予想が生き残ることが判明。「この制約で解けるなら積の法則くらいしかないでしょう」と思いながらもダメ元で sub 。結果は... AC (249min) 。ここで 8 完。京大他チームに優勝されなければシンガポールには行けそう。良かった。
続いて、ひらきちが large ケースを生成してローカルテスタを試していた G をデバッグ、なんとか AC (262min) 。順位表や他のチームの様子からして見るからにヤバい問題だったので、本当に助かった。ここで 9 完、良かった良かった。
ここまで来て残っているのは FHJ 。 HJ は絶望感ヤバかったのでやるのは F 一択だった。自分が D を通した直後に、ネッコアラに要求を話す。
始点を原点に取った時に、上面のある点 $(x,y,c)$ について最短経路長を $\rm{min}$ や $\rm{max}$ を使ってもいいので手計算か何かで求めてくれ。これが $f(x,y)$ にできれば、あとは任せてくれ。
「あとは任せてくれ」と言った部分は、 $x$ 軸 $\rightarrow$ $y$ 軸の二重の三分探索。自分がだらだら YouTube でも見てた時に冒頭に乗せた Youtube Shorts を発見しそこでこのアニメーションが紹介されており、これが頭にあったので「こんなものが三分探索出来ないわけがない」という確信があった。その上、脳内の Wolframalpha に $f$ を 3D 描画させても三分探索できる形をしていると言ってくれたので、信じることにした。自分の大胆予想なら間違ってる可能性はあるけど頭の中の Wolframalpha 君がそう言ってるなら行けるんでしょう。
一番遠い点は反対側の頂点ではないのか！
— ａｐｕ (@apu_yokai) 2022年5月21日
面白いな https://t.co/szscpalJYo pic.twitter.com/j7InEsG6O1
そして、恐怖！手計算男集団！が結成。ひらきちも G の AC 後にこの計算に合流。
この時、自分が三分探索の形を書いてあとは $f$ を入れるだけの状態に持って行くと同時にネッコアラとひらきちがガリガリ手計算するというプログラミングコンテストとは思えない異様な光景に発展。選手カメラが遠くて事件現場を捉えられていないのが本当に心惜しい。
その後、サンプルを試すが値が合わない。慌てて printfile する。ネッコアラとひらきちにもコードと計算結果とを確認してもらいつつ、三分探索の誤りの指摘をネッコアラから受ける。
その誤りを修正すると、サンプルが合う。もう祈るしかない。コード中の三分探索の反復回数を変えたコードを何度か投げる。結果は...
AC!!! (291min)
10完 + 1500min 、凍結後に 3 つも通っちゃったよ...
J は手を出すだけヤバいという共通認識があり H もネッコアラが取り組んだくらいでほぼ何も進まなかったので、万策尽き果てている状態にはなった。そして、そのまま終了。さすがに 9 分では何もできなかったのでマシンに Minesweeper がないか探したが、なかった。来年は入れといてください、お願いします (まぁ今年 WF 使い切る予定なので恩恵はないと思いますが...) 。
謝罪2 凍結時点でだいぶヤバかったので、腹いせに 7 完のふりをすることにしました。ほんまごめん。
7完です😭😭😭😭😭😭😭😭
— 物理好き (@butsurizuki) 2024年12月22日
やらかした〜〜〜〜〜〜〜〜〜〜😭😭😭😭😭😭😭😭😭😭😭😭
おまけ 順位推移
まとめ
結果、唯一の 10 完で準優勝できた。 ( 実は 10 完がもう 1 チーム出てうちが銅だと読んでいたが、意外にも 9 完ばかりだった )
反省点 : 開始 3 時間半くらいまで本当にグダグダだった。本来 4 時間時点で 9 完くらいの地力はあったはずなのに 7 完で甘んじたのはかなり反省。あと、遅刻は disqualified に繋がりかねないので、やめよう！
褒めるべき点 : 最後に帳尻が合ったところ。いや良く帳尻あったな本当に...
次はシンガポールで playoff 。かかってこいや！！！もう一回金メダル取ったるぞ！！！！！！
( よく考えたら playoff 金って絶対 WF ( 同一大学にふたつメダルが授与されることはなく、順位の良い方にのみ授与される ) なので、 2 回取ったら理論値なのか、わくわくしてきたな )
