木の同型判定問題
- 木についてDFSでハッシュを求め、その比較によって同型判定をする
- snukeさんの記事にrng_58さんのやり方の和訳が書いてある
問題
メモ
ACM-ICPC 2016 国内予選 F: 文字解読
図形を木にした時に頂点数がそんなに多くならないので、多項式ベースのハッシュじゃなくても、文字列でハッシュを作っても全然間に合う。
https://kimiyuki.net/blog/2016/06/27/icpc-2016-domestic-f/
ここが詳しい。
図形を木に変換する問題としてカゴメカゴメがある(同型判定と関係無いけど)。
http://yukicoder.me/problems/no/348
HackerRank Tree Isomorphism
部分木のハッシュ値を一意にするために木の中心を探して、それを根としてハッシュを取る。
複数の中心がある場合はハッシュをとって小さい方を採用するとよい。
Codechef IOPC Techkriti 2012 - IIT Kanpur : Hardware upgrade
写像の組合せを問うものだが、木の同型判定ができればそれを利用して写像を作ることができる。
そのため、木の同型判定が大事になる。
以下の解説が分かりやすい。
http://d.hatena.ne.jp/komiyam/20120115/1326632089
TopCoderOpen 2015 Round2B Medium Balance
kmjpさんの解説がある。
http://kmjp.hatenablog.jp/entry/2015/06/21/0930
これも上の文字解読のように図形を木にして、同型判定する問題らしい。(やってない)
Codeforces Round #395 (Div. 1) D. Timofey and a flat tree
http://codeforces.com/contest/763/problem/D
この前出たやつ。ムズすぎて、まだ復習できてない。
考えても分からん。