読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける木の同型判定問題まとめ

競技プログラミング

この前のコドフォで木の同型判定に関連した問題が出ており、この辺りの理解が微妙だったのと、rng_58さんがハッシュアルゴリズムを提唱してたりして、色々あったので、色々まとめました。

木の同型判定について

木についてDFSでハッシュを求め、その比較によって同型判定をする。
snukeさんの記事にrng_58さんのやり方の和訳が書いてある。
http://snuke.hatenablog.com/entry/2017/02/03/054210

問題

ACM-ICPC 2016 国内予選 F: 文字解読

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp
図形を木にした時に頂点数がそんなに多くならないので、多項式ベースのハッシュじゃなくても、文字列でハッシュを作っても全然間に合う。
https://kimiyuki.net/blog/2016/06/27/icpc-2016-domestic-f/
ここが詳しい。
図形を木に変換する問題としてカゴメカゴメがある(同型判定と関係無いけど)。
http://yukicoder.me/problems/no/348

Codechef IOPC Techkriti 2012 - IIT Kanpur : Hardware upgrade

https://www.codechef.com/problems/IOPC1200
写像の組合せを問うものだが、木の同型判定ができればそれを利用して写像を作ることができる。
そのため、木の同型判定が大事になる。
以下の解説が分かりやすい。
http://d.hatena.ne.jp/komiyam/20120115/1326632089

TopCoderOpen 2015 Round2B Medium Balance

https://community.topcoder.com/stat?c=problem_statement&pm=13841
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
この前出たやつ。ムズすぎて、まだ復習できてない。
考えても分からん。