titiaのノート: 第二回日本最強プログラマー学生選手権

2021年6月12日土曜日

　ABCDFで終了。Eはコンテスト後、自力で解けたもののかなり苦戦した。

G - Spanning Tree

　行列木定理を知らないとどうしようもない。

　これを知れたのは良かった。（証明は理解できてないけど）

　行列式の計算もはじめて書いたと思う。なるほど、掃き出し法を使うことで三乗に収めるんですね。

　ケイリーの公式といい、この行列木定理といい、知らないと思いつくのが難しい（が、競技プログラミングに出題される）定理が木の分野にはありますね。

　最近、SRMで類題を見たので、解説ACしました。

　公式解説の「ハッシュを使った解法」は凄いですね。サイクルの部分はSRMのものと同じですが、木の部分もこうやって処理できるとは。

　SRMのときはサイクルのところしか読まなかったので、木の部分はどうするんだろう、と考えていたのですが、LCAを使うしかないのかな……と思っていたところでした。しかしこれもLCAを使わずにハッシュで解けるんですね。

　とはいえ、このハッシュの使い方はこのFと同じか。

　いくつかの状態があって、そのうちの一つでも存在するかどうか調べたい……というときはこのハッシュ（Zobrist Hash）を検討しても良いのかもしれない。