リハーサル
MLE を見ようとして大量にメモリを取ったら PC が落ちたりして面白かった。
本番
ある程度関わった問題を何となく時系列っぽく並べる
問題文と解説: Regional | ICPC 2023 Asia Yokohama Regional
B
親の顔より見た平均の式変形。 の小ささを利用しようかと考えたが数秒で思いつかなかったので却下した。
D
ほとんどやるだけ。連続部分列の高速な一致判定が欲しくなったので で LCP のテーブルを作っておいた。
H
potato と一緒に考察する。 しばらく悩んでいたが、potato が「最小カットじゃないか？」と発言したのでそこから数秒で解けた。 最小カットで非自明な問題を久々に見た気がするが、すぐに解けるべきだった。
K
線分の端点が正方形の内側にあるようなクエリのことが脳から抜け落ちていて、 軸と
軸のそれぞれに対して座標を特定しようとするとクエリがギリギリ溢れるななどと考えていた。
その結果アルゴリズムも複雑になり、実装に手間取ったうえにバグらせてしまった。
J
最初の方で potato から「min plus の畳み込みは高速になるか？」と聞かれ、いかにも担当っぽい問題だったので貰う。
木上の最小費用流になることはすぐに分かり既知のアルゴリズムを適用しようとしたのだが、頂点の湧き出しに対するコストが なので辺の本数が
乗になってしまう。
こういうときはアルゴリズムの動作を観察して適切に高速化すると (例えば等差数列加算とか) 上手く行くことが多いのだが、今回は等差数列の insert だったので解けそうで解けない。
得意分野のはずという気持ちでかなり時間を消費してしまったのだが、結局最後まで残ってしまう。
最小費用流なので多分何かしらの貪欲だろうということで potato Hemimor に任せているとそれっぽい貪欲が提案されたので実装してもらい、通った。
結局、等差数列の inset を愚直にやっても上手く計算量が抑えられていたらしい。 この分野に関連するアルゴリズムはかなり触っており自信があったので、ショックだった。
C
とりあえずポリアはする。
回転を同一視しない数え上げを考えると、カタラン数を少し弄ったようなものが出てくる。 ラグランジュ反転の思い出しに自身が無かったのと、最後の方まで畳み込みなしで押せる自信が無かったので FPS で書いておく。
周期が決まっている場合の数え上げだが、当初スタックに色を積んでいく方針で考えていたので 周期で全部消えるケースしかないんじゃないかと予想した。
この方針で実装するとサンプル
が合わないので見てみると、消えないケースがある。
サンプルすら合わない解法を実装し始めてしまうのは悪い癖なのだが直りそうもない。
しばらく考えると、隣り合う同じ色を消す方針を思いつき、奇数長回文が残る場合が必要十分と分かった。
これも FPS で立式できるので書いて出してみると TLE。
ここからの高速化の作業は悪夢だった。 まず FPS の立式を偶奇で分けることで長さを半分にする (TLE)。 FPS の inv を定数倍が良好な実装に変える (TLE)。 同じ列の DFT を繰り返し計算している部分を使いまわすようにする (TLE)。 その他あり得そうな部分をひたすら高速化して回る (TLE)。
結局この方針は十分に高速化された FFT でギリギリ通せるラインのものだったようだ。 SpeedStar にはどのみち負けていたのだが、食らいつけなくて残念。
総評
不調気味だった気がするが 位には落ちなかったし、
位は好調でも難しかっただろうと思うので、全完できなかったことだけが心残りになった。
海外に行くのが嫌いなので playoff 確定でげんなりしているが頑張りたい。
懇親会
例の大きい名札を付けてうろうろし、色々な人に話しかけてもらった。 初めて会う人もたくさんいたので嬉しい。
懇親会でアルゴリズムの話をする難しさをこの手のイベントの度に感じていて、「最近良い感じのアルゴリズムありましたか？」から切り出せる相手があまり多くない。 次の機会があれば、hotman さんに倣って懇親会で話せるアルゴリズムのお品書きを作っておくべきかもしれない。 fenwick tree の最悪計算量を半分にする方法や、競プロで使えそうにない最近のフローアルゴリズム群などについて話した。
終わりに
準備に携わったスタッフの皆様、ありがとうございました。
