Codeforces Round #395 (Div. 1) D. Timofey and a flat tree
http://codeforces.com/contest/763/problem/D
問題概要
木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるということである。
解法
以下を大いに参考にする。
基本的にハッシュなんて適当に作っても(悪意がなければ)衝突しないのだが、ちゃんとしたハッシュというのがあるらしいので利用した。
基本的に全方位木 DP である。高さが絡むおかげで実装が面倒になっている。まあ、そんなに面倒かといわれると面倒でもないのだが…。
逆元を使わない実装にしたけど、逆元が使えない確率は小さいので使ってもいいと思う。
Codeforces Round #395 (Div. 1) E. Timofey and our friends animals
snuke さんの以下の記事を読んでいればやるだけ?
http://codeforces.com/contest/763/problem/E
問題概要
n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与えられるので順次処理せよ。
Codeforces Round #395 (Div. 1) C. Timofey and remoduling
http://codeforces.com/contest/763/problem/C
問題概要
n 個の数が与えられる。これを並び替えて mod m 上での等差数列にできるかどうか判定せよ。可能なら初項と公差を示せ。
Codeforces Round #395 (Div. 1) B. Timofey and rectangles
http://codeforces.com/contest/763/problem/B
問題概要
N 個の長方形が与えられる。長方形の四隅は格子点上にあり、辺は軸に平行、辺の長さは奇数である。長方形同士は重ならない。
長方形を 4 色で塗り分けたい。ただし接している長方形の色は異なる必要がある。このような塗り分け方が存在するなら、その一例を示せ。