Codeforces Round #346 (Div. 2) F. Polycarp and Hay
問題概要
二次元数列 h が与えられる。以下のルールにしたがって h を変更することにより、h の総和を K にすることはできるだろうか。
- h[i][j] は好きなだけ減らせる。
- h[i][j] != 0 であるような h[i][j] はすべて等しい。
- h[i][j] > 0 である部分はひと繋がりになっている。
- 少なくともひとつ値が変わらない要素がある。
解法
大きい要素から処理し、Union-Find で繋いでいく。連結成分のサイズが欲しいのでサイズ付き Union-Find を使うと良い。
(y,x) に value を追加したときに構成できるかを判定するには、
- value が K の約数である
- (y,x) が属する連結成分のサイズが K/value 以上である
という 2 点を確認すればいい。
大まかな流れをスライドにした。
Codeforces Round #346 (Div. 2) F. Polycarp and Hay
解法自体は見えやすい。
