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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

解法自体は見えやすい。