模擬地区予選2022
引退してるけどチームメイトと出ることに
コピぺや同時コーディングの禁止を完全に失念しており参加したことをかなり後悔
ワシも若い頃 2回程 ICPC に出たのじゃが、あの頃はコピペも同時コーディングもありだったんじゃ...
コンテスト
A
shakayami がすぐに通してた
B
se1ka2 が読むも英語に負けたので俺が読む
読解するとやるだけなので丁寧に実装して通した
C
中国人郵便配達問題であることはわかる
se1ka2 が郵便配達問題は最小重みマッチングだと言う
最小重み一般マッチングは人間が書くものでは無いと主張すると、se1ka2 が二部グラフにしてくれた
そのまま蟻本写経して MCF を含めて全て実装してくれた 偉すぎ賞授与
デバッグを手伝っていると se1ka2 が構造化束縛や emplace を知らない事が判明 偉すぎ賞剥奪
バグを治すと通った そこそこ偉い賞授与
D
の LIS をやればいいんだろうな〜とは思うが、詰めたくなくてしばらく放置
dp[k][j] : 長さ k の数列で一個前が j のもののうち二個前が一番小さいもの として vector< map<int,int> > dp(N+1) を作成
各 map が勝手に単調減少になると思っていたが、WA が出たので操作を付け足して AC
E
末尾2個だけ覚えれば良いので は思いつく
少し時間を置いてからもう一度見ると、ただの分割統治 FFT であることに気が付くが、FFT も書きたく無いし TL もそれなりに厳しそう
実装が空いたら書いても良いと思ったが最後まであかず
F
重複はロリハで簡単にチェック出来る
同型判定に悩んでいたが、天才のひらめきにより解説と同じ方針でロリハで判定出来ることに気づく
気合いで実装するも WA
hash の衝突であってくれ〜と叫びながら激ヤバ実装で hash を無理やり三つに増やすと通った
G
やばすぎて誰も手を付けず
そらそう
H
SCC しても DAG の処理どうするねんと思っていたが、se1ka2 が DAG はパスになると言って通す
パスになるの典型知識の見た目してるけどどうなんだろうな
と言うか見たことある気がする
I
色々悩んだけど俺は分からず
se1ka2 が解けたっぽいが K と実装を奪い合い結果的には両方通らず
J
shakayami がボロノイ図と言うが知らず
なんとなく強い人間はサクッと通しそうな見た目に見えたが 0AC らしい
K
shakayami が天才で、ロリハが出来ることを思いつく
二人で紙で実装を固めておき、I から実装を奪い書くもバグしまくり
コンテスト後も20分やり続けようやく sample が合うようになったので出すもジャッジは止まっていた
ただ書き上げたのは少なくともロリハの mod に 998244353 を使っている時点でダメっぽい
base をランダムに3つ使っている（mod は面倒だったので使い回し）から衝突はしないと思ったが、文字列長が 998244353 を越えるため、どんな base であろうと 998244353 を落とせるテストケースが入っているとのこと（他に有名 mod 二つ狙い撃ちされているらしい）
文字列長が mod を越えるケース初めて見たかも
L
重心を根にして部分木の同型判定をすれば良いことまでは分かる
適当に部分木の情報を使って数次元の hash 作れば良いだろうなと思い、実装が空いたら書こうと思っていたが最後まで空かず
ABCDFH の6完12位
感想
幾何以外きちんと（一部あっているか分からないのもあるが）解法が出ていたのはかなり成長を感じる
Modint が何回か活躍したので前半に書いておいたのが偉かった気がするが、たくさんの CE の原因にもなった
良問多くて、本当に問題枯渇しているのか？と言う感じ
ただ重実装多く無い？運営は同時コーディングやコピペを禁止したことを忘れているだろ
あと想定では無いのかもしれんが hash を取らせる問題が多い
簡単に複数次元 hash を作れる道具を持っておくと良さそう
昔に比べてだいぶ環境を整えたので、debug 関数やランダムケースハックなどが使えないのかなり辛かった
コンテスト後にやったカルカソンヌが面白かった
初見のボドゲは後から反省点が色々見つかるのでまたそのうちやりたい
