Codeforces Round #397 ABCDE
- A. Neverending competitions
- 問題概要
- 解法
- B. Code obfuscation
- 問題概要
- 解法
- C. Table Tennis Game 2
- D. Artsem and Saunders
- E. Tree Folding
Codeforces Round #396 (Div. 2) A,B,D,E
C 問題は読めなかったので省略します。
http://codeforces.com/contest/766
- A. Mahmoud and Longest Uncommon Subsequence
- B. Mahmoud and a Triangle
- D. Mahmoud and a Dictionary
- E. Mahmoud and a xor trip
Codeforces Round #395 (Div. 1) D. Timofey and a flat tree
http://codeforces.com/contest/763/problem/D
問題概要
木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるということである。
解法
以下を大いに参考にする。
基本的にハッシュなんて適当に作っても(悪意がなければ)衝突しないのだが、ちゃんとしたハッシュというのがあるらしいので利用した。
基本的に全方位木 DP である。高さが絡むおかげで実装が面倒になっている。まあ、そんなに面倒かといわれると面倒でもないのだが…。
逆元を使わない実装にしたけど、逆元が使えない確率は小さいので使ってもいいと思う。