モラトリアムライフ

自由を求めて

精進記録 : Codeforces Round #346 Div2 F. Polycarp and Hay

問題概要

n \times m の2次元数列 A = \{ a_{i, \, j} \} \, (1 \leq i \leq n, 1 \leq m) が与えられる.
このとき, 次の条件を満たすような n \times m の2次元数列 B = \{ b_{i, j} \} を求めよ. (存在しないなら "NO" を出力せよ)

  • b_{i, j} は整数
  • 0 \leq b_{i, j} \leq a_{i, j} (1 \leq i \leq n, 1 \leq j \leq m)
  • B の総和が k と一致する, すなわち \sum_{b \in B} b = k
  • ある A の要素 a_{i, j} \in A が存在して, a_{i, j} = b_{i, j} かつ すべての b \in B に関して「 b = 0 または b = a_{i, j}」が成り立つ.
  • b \neq 0 なる B の要素は グリッド上連結である.

    制約

  • 1 \leq n, m \leq 1000
  • 1 \leq k \leq 10^{18}
  • 1 \leq a_{i, j} \leq 10^{9}
  • 入力はすべて整数

codeforces.com

考察

答えが存在する場合について考える. そのとき, 上記の4, 5番目の条件を満たすような a_{i, j} がわかっているとすると, DFSやBFSなどによって簡単に答えを求めることができる. ( a_{i, j} 以上となるような要素に向かって探索範囲を広げていく)
したがって, そのような a_{i, j} を求めることがこの問題の本質である. そこでまずは, どのような条件が満たされていれば良いかを考える.
b = a_{i, j} となるようなものの数を m とすると 3番目の条件から m \cdot a_{i, j} = k であるから, m = \frac{k}{a_{i, j}} であり, また, m は整数であるから a_{i, j} は k の約数である必要があることが言える.
つまり

k の約数であるような a_{i, j} であって, a_{i, j} 以上となる (i, j) との連結成分の個数が \frac{k}{a_{i, j}} 以上 となるような a_{i, j} は存在するか? 存在するならば1つ求めよ.


という問題を考えることになる (逆に, この条件が成り立っているならばBFS, DFSで構成可能)

しかし, 各 a_{i, j} が条件を満たしているかをBFS, DFSなどで確認すると 1回に O(nm) かかってしまい全体として間に合わなくなってしまう. (多分) それゆえ, 全体として連結成分を数える時の計算量を落としたい. そこで, 個人的によく使っている考え方を示すと (※ 個人の感想です)

  • 情報を丸める : (ex : 平均値, 総和だけの情報しかいらない等の各数列の情報全てを必要としない場合)
  • 過去の情報(履歴を用いる).
    • ある単調性が成り立つ場合 → (ソートをしてから)過去の情報を用いて計算,情報を逐次更新 (ex : 尺取り法)
    • 「組合せ数」や「可能か不可能か」などの情報が比較的軽い場合 → 動的計画法 DP を行う
  • 強いデータ構造で殴る！(Segment木, 遅延伝搬Segment木, Rolling Hash, Link Cut木, HL分解 etc... )

今回は, a_{i, j} 以上となる要素の連結要素を知りたい！ということであったので, f(x) を x 以上となるような(連結の情報を含む)二次元配列のデータとすると, 雑な記法をすると a_{x_{1}, y_{1}} \leq a_{x_{2}, y_{2}} \longrightarrow f(a_{x_{1}, y_{1}}) \supseteq f( a_{x_{2}, y_{2}} ) という "単調性" が成り立つので a_{i, j} が 大きい順にソートして Union Find で連結成分を更新しながら判定をして行けば良い. (2次元グリッド上でUnionFind木を使う)

実装例

codeforces.com