AtCoder Grand Contest 013 B. Hamiltonish Path
頭が悪すぎて絶望したので反省に書いておく。
この問題の概要を読んだのは3週間前とかで、今まで普通に解けていなかったし、結局 さっきAcceptはしたものの嘘解法であることに気づいたし最悪。
500点問題もまともに解けないとかもはや、やってる意味はあるんだろうか.
問題概要
読んで: B - Hamiltonish Path
(嘘)解法
とりあえずDFS-treeか関節点辺りが大事なんじゃないかなと思える(まあ解説を読むとその時点で間違ってるんですけどね)。
特に、DFS-treeに関しては
- 任意の方向付けされた後退辺(u -> v)について、vはuの祖先
という結構良い性質があるわけなので、DFS-tree上の葉を端点として、rootを通るようなpathを考えれば、絶対に問題の条件を満たせることが分かって嬉しい。
ということで、初めの内は、本当に任意のDFS-tree上で解く方法を探していたんだけど、全くうまくいかなかった。
これもめちゃくちゃ頭が悪いポイントで、わざわざ任意の状態を考えて一般化しようとしなくても、constructiveな問題なのだから、恣意的に考えるDFS-treeを決めて良いわけだし、直感的に関節点が大事そうという気持ちになったのにその考えを捨ててしまっている...
DFS-treeの根vに関して以下は同値である。
- vは関節点
- 後退辺を除いた上で、vの次数が2以上
つまり、上の考察も合わせて考えると、与えられたグラフに関節点が含まれるならば、それを根としたDFS-treeを作れば、必ず根を通り葉同士を繋ぐようなpathをtree上から持ってこれて、それを回答すれば良い。
従って、後考えなければならないのはグラフが1つも関節点を含まない状態ということになる(つまり二重連結なグラフ)。
この状態においては、DFS-treeの根の、(DFS-tree上の)次数は1である。
当然、後退辺が引かれている可能性があるから、元のグラフ上においても次数が1とは限らない。
逆に元のグラフ上においても次数が1であれば、これは自明なケースとして処理できる。理由は、DFS-treeの適当な葉から根へのpathは全て条件を満たすから。
従って、これから考えるケースは、根への後退辺があるものとして仮定して良い。
ここで突然異常な嘘が発生するんだけど、何故か暗黙に以下を仮定してしまった。
- 必ず、根への後退辺を持つ葉が存在する
今思うと頭がおかしすぎるんだけど、この仮定の元では確かに以下のような構成で解ける。
- 上記の条件を満たす葉sを見つける。
- sの先祖であって、子を2つ以上持つ(すなわちDFS-tree上で次数が3以上の)頂点tが存在するか調べる。ただし、そのような頂点が複数存在する場合は、葉から最も近いものとする。
- tが存在しなければ、sから根へのpathが答え。
- tが存在するならば、tの子であってsの先祖であるような頂点u(これはs自身である可能性もある)を始点として、「u -> s -> 根 -> t -> sのt以外の子 -> 適当な葉」というpathが答え。
図示するとこんな感じ。
何故かこれで解けたつもりになって、実装を初めてしまった。
結果としてはバグりまくったけど、このままの方針でACしてしまった。
まあテストケースがそもそも16個で少ないし、問題の性質上、正直複数のヒューリスティクスを入れたコードとか、乱択とかを落とすのが大変そうだし、仕方ないかなという気はする。
ちなみにACしたコードは以下のようなグラフを与えると普通に落ちる。
まあ「根への後退辺を持ってる葉」が存在しないから当たり前ですね。
ただ、前述のように、根の選び方とか、DFS-treeの構築を乱択にすると、「根への後退辺を持ってる葉」が発生しそうな気もしている(逆にどのように構築しても、そのような葉が存在しない二重連結なグラフって存在しますか？)。
こればっかりは分からないし、本番でもしもっとテストケース強かったらペナルティ覚悟でそういう乱択試すとは思うけど、ちゃんと素直に解きたかったなあ...
想定解法は、めちゃくちゃシンプルなんだけど、正直思いつける気が今でもしていないし、ここまで頭が悪いと人生やめた方がいいですかという気持ちになる
