ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 82 F. Number of Components

Problem - F - Codeforces

※解説の都合上、マスに書かれている整数を「色」と表現することにします。記号も  c だし。

問題概要

 n\times m のマスからなる盤面があり、各マスには色が塗られている。このマスそれぞれを頂点とし、隣り合うマスの色が等しいときにその間に辺を張るようなグラフを考える。

色は整数として表現され、全てのマスには初期状態で色  0 が塗られている。以下のようなクエリを  q 個処理せよ。

  •  i 番目のクエリは整数  (x_{i}, y_{i}, c_{i}) で特徴付けられる。マス  (x_{i}, y_{i}) の色を  c_{i} に変更し、その後グラフの連結成分の個数を答えよ。

ここで任意の  i に対して  c_{i} \le c_{i+1} である。

制約

  •  1 \le n, m \le 300
  •  1 \le q \le 2\times 10^{6}
  •  1 \le c_{i} \le \max(1000, \lceil\frac{2\times 10^{6}}{nm}\rceil)
  •  c_{i} \le c_{i+1}

解法

連結成分の管理と言えばUnion-Findですが、Union-Findは連結成分を併合していくという操作に非常に強い一方で、分離する(辺や頂点を削除する)という操作に弱いです。この問題ではいったん繋がったマス同士が、間を別の色に上書きされることで切れてしまう可能性があります。なんとか併合だけで解き切れないでしょうか。

ここで  c_{i} \le c_{i+1} という条件に注目します。考える色  c を1つ固定すると、その色のマス目は「 c_{i} = c である間は増えていき、 c_{i} \gt c になってからは減っていく」という一種の単調性があります。これを利用しましょう。

クエリを順番に適用することを時間の経過として考え、 t 番目のクエリを適用する時刻をそのまま  t とします。 c のマスが増えていく間は時間を順方向に、色  c のマスが減っていく間は時間を逆方向に見ていくことで、どちらも色  c の頂点とその間の辺が増えていく方向に処理を進めていくことができます。これならUnion-Findが使えます。

具体的な処理方針です。まずはクエリ操作をシミュレートしながら、色  c ごとに「時刻  t にマス  (x, y) の色が新しく  c になった」というinイベントと「時刻  t にマス  (x, y) の色が  c でなくなった」というoutイベントを並べます。ただし同じ色で上書きしているところは単に無視します。ここで

  • 初期時刻  0 に、全てのマスの色が新しく  0 になった。(inイベント)
  • 最後のクエリより後の時刻  q+1 に、全てのマスの色が消えた。(outイベント)

というイベントも追加することにすると、両端の条件を特別扱いしなくてもよくなります。

 c についてのイベントの時刻だけを考え、以下のように順方向・逆方向それぞれUnion-Findでシミュレートします。そうすると、これらのイベントで区切られた時刻区間それぞれについて色  c でできた連結成分の個数を求めることができます。

f:id:betrue12:20200213222741p:plain

これを全ての色について計算すると、答えは時刻区間に対する加算操作を大量に行った結果として求められます。これはimos法で効率的に処理することができます。

計算量について考えましょう。上記の方法だとinイベント、outイベントを全ての色について合計した個数はそれぞれ最大で  q + nm となります。生じる時刻区間の個数もこれと同程度になるため、ここは問題ありません。

工夫が必要なのはUnion-Findで、全ての色について頂点数  nm のUnion-Findを毎回作り直していると間に合いません。各色について触る頂点の個数もイベントの個数と同程度なので、1つのUnion-Findを使い回し、1回のシミュレーションが終わったら触った頂点だけ親やサイズ等の内部状態を初期化するようにすれば、一般的なUnion-Findの実装では初期状態に戻せます。これでUnion-Find部分の計算量も大丈夫です。

ACコード

Submission #70892348 - Codeforces

実装はなかなか大変です。図を描きながらしっかり整理して、区間の両端の時刻や連結成分数などを正しく処理していきましょう。

あとは制約をパターンマッチング的に読むと  1 \le c_{i} \le \max(1000, \lceil\frac{2\times 10^{6}}{nm}\rceil) \min と誤読しやすいので注意です。(1敗)