今日解いた競プロの問題。

いろはちゃんコンテストDay1-I: リスの状態は(今いる木, 最後に通った枝の隙間の大きさ)で表される。これは$O(NM)$あるいは$O(N\max C)$になってしまいそうだが、ちょっと考えればわかる通りある木について考え得る状態数はその木の枝の数だけしかない。次数の総和は当然$2M$であり、状態数は$O(N+M)$で済む。

この問題では隙間の長さの同じ場所はノーコストで行き来できる。ということはこの辺の状態を同一視してしまって良くて、UnionFindでまとめてしまえる。具体的には各枝を頂点としたUnionFind木を作成して、各木について、その木から伸びている枝の中で同じ隙間のものをすべて結合する。一応補足すれば全ての組み合わせについて結合処理をやる必要はなく、UnionFindなので順番に並べて結合すれば全部くっつく。

これで各枝が「行き来できる島」のようにまとまった。あとは「島」と木を頂点としたグラフを作って「島」と木を適宜接続してBFSすればよい。これで頂点1から頂点Nまでの距離を計算すれば「島」を乗り換える回数(=休憩の回数)が分かる。あとはKをかけるだけだ。

解いてから思ったが、UnionFindを使わずとも01BFSで良かった。ライブラリ化してないから若干めんどいが、実装としてはその方がきれいな気がする。あと最後にKをかけるの、本当にどうでもいい要素すぎないか。

---

現実逃避と積みゲー消化を兼ねてRecursedを延々プレイしている。本格的なパズルゲームは本当に難しい。BABA IS YOUもInductionもHelltakerも随分前に詰まって放置してしまっている。