Official

D - Grid Repainting 3 Editorial by E869120

この問題は A・B・C 問題と比較するとかなり難易度が高く、コンテスタントの 9 割以上が苦戦しています。
しかし、適切な考察を行うと、綺麗に解くことができます。 本解説では、

  • 考察 1：問題の言い換え（二部グラフに落とし込む）
  • 考察 2：グラフが木の場合に解く
  • 考察 3：グラフが森の場合に解く
  • 考察 4：グラフが一般の場合を考える
  • 解法のまとめ
  • サンプルコード

の 6 つのセクションに分けて解説します。


1-1. ステップ 1｜問題の言い換え

今回解くべき問題は、次のような二部グラフに対する操作の問題に言い換えることができます。

二部グラフの問題
黄色頂点 \(1, 2, \cdots, H\)、灰色頂点 \(1, 2, \cdots, W\) がある。
グラフの辺は（操作前・操作途中含め常に）赤色で塗られているマスに対応する。
つまり、操作前の時点では \(c_{i, j}=\)R であるような \((i, j)\) に限り、黄色頂点 \(i\) と灰色頂点 \(j\) を双方向に結ぶ辺が存在する。

そのとき、あなたは次の操作を行うことができる。（それぞれ本問題の操作 X・Y と対応する）
操作X　次数 \(1\) 以上の黄色頂点を選び、その頂点と隣接する辺をすべて消す。
操作Y　次数 \(1\) 以上の灰色頂点を選び、その頂点と隣接する辺をすべて消す。

操作Xを行った回数を \(X\) 回、操作Yを行った回数を \(Y\) 回とすると、白色で塗られたマスの数は \(HW - (H-X)(W-Y)\) となる。その値を最大にするような操作手順を 1 つ求めよ。

例えば、次のようなマス目を考えてみましょう。

RRR
BBR
BBR
BRR

この場合、対応する二部グラフは下図のようになります。

  • 操作 X で黄色頂点 \(i\) を消す操作は、赤マスが \(1\) 個以上ある \(i\) 行目を全部白にする操作
  • 操作 Y で灰色頂点 \(j\) を消す操作は、赤マスが \(1\) 個以上ある \(j\) 列目を全部白にする操作

となっていることが分かると思います。


1-2. ステップ 2｜二部グラフが連結な木の場合を解く

では、どのような操作を行うのが最適であるかを考えていきたいと思います。

しかし残念ながら、いきなり一般の場合に解くのは難しいです。そんなときは、

  • 特殊なケースを考える

という考察の進め方をするのが、競技プログラミングにおける戦略の 1 つです。


この問題では、グラフが連結な木の場合について、最大で操作 X を何回、操作 Y を何回行えるかを考えてみましょう。

まず、以下の理由で「全部の頂点を消すこと」は不可能だと言えます。（背理法による証明）

全部の頂点を消すことが可能であると仮定する。
そのとき、必ず「\(1\) 頂点だけ残った状態」を経験することになる。しかし、最後に残った頂点は（その時点で）次数 \(0\) であるため、操作ができず矛盾する。

次に、以下のような操作方法をとることで、頂点を \(1\) 個だけ残すことができます。

操作
「次数が \(1\) の頂点を消すこと」を繰り返す。

証明
木には必ず次数 \(1\) の頂点が存在する。また、次数 \(1\) の頂点を消しても、操作後のグラフは連結な木のままである。
したがって、辺がなくなるまで操作を行うことができ、最終的には \(1\) 頂点のグラフになる。

つまり、操作回数的には、次の \(2\) つのうちいずれかが最適であることを意味します。

  • 操作X を \(H\) 回、操作Y を \(W-1\) 回
  • 操作X を \(H-1\) 回、操作Y を \(W\) 回

より分かりやすく説明するため、具体例の図も載せておきます。
次数 \(1\) の頂点を消し続けることで、最終的に \(1\) 頂点だけ残せることが分かると思います。


1-3. ステップ 3｜二部グラフが森の場合を解く

次に、「閉路を含まないが複数の連結成分が存在する場合」、つまりグラフが森の場合を考えてみましょう。

頂点数が \(1\) ではない連結成分の数を \(K\) 個とします。\(i\) 個目の連結成分が黄色頂点を \(a_i\) 個、灰色頂点を \(b_i\) 個含むとき、この連結成分については、

  • タイプA：操作X を \(a_i\) 回、操作Y を \(b_i-1\) 回行う
  • タイプB：操作X を \(a_i-1\) 回、操作Y を \(b_i\) 回行う

のいずれかを行うのが最適です。

操作は連結成分ごとに独立に考えられるので、全体の操作回数は、

  • 操作X を \((a_1 + a_2 + \cdots + a_K)\) 回、操作Y を \((b_1 + b_2 + \cdots + b_K) - K\) 回行う
  • 操作X を \((a_1 + a_2 + \cdots + a_K) - 1\) 回、操作Y を \((b_1 + b_2 + \cdots + b_K) - (K - 1)\) 回行う
  • 操作X を \((a_1 + a_2 + \cdots + a_K) - 2\) 回、操作Y を \((b_1 + b_2 + \cdots + b_K) - (K - 2)\) 回行う
  • \(\vdots\)
  • 操作X を \((a_1 + a_2 + \cdots + a_K) - K\) 回、操作Y を \((b_1 + b_2 + \cdots + b_K)\) 回行う

のいずれかになります。そこで、タイプA を選ぶ回数を \(x\) とするとき、白マスの個数 \(f(x)\) は二次関数

\[ f(x) = HW - (H - (a_1 + a_2 + \cdots + a_K - x))(W - (b_1 + b_2 + \cdots + b_K - (K - x))) \]

で表されますが、これが下に凸な関数であることから、以下の \(2\) つのうちいずれかの選択が最適となります。

  • 全部の連結成分についてタイプA を選ぶ
  • 全部の連結成分についてタイプB を選ぶ

例えば下図のケースでは、タイプA に全振りした場合、白マスを最大値 \(76\) 個にすることができます。


1-4. ステップ 4｜一般の二部グラフの場合に解く

最後に、一般のグラフの場合を考えてみますが、実は

木にいくつか辺を加えても、木の場合と答えは変わらない

ことが証明できます。なぜなら、どのようなグラフでも、操作によって「ある連結成分のすべての頂点を消す」ことはできないからです。

したがって、Union-Find 木などを用いて各連結成分における全域木を \(1\) つ取り出し、それ以外の辺を無視しても、白マスの数は変わりません。

そうすると森の場合に帰着できます。あとは、1-3. 節までに説明したアルゴリズムを実装すると、正解（AC）を出すことができます。


1-5. まとめ・計算量

解法をまとめると、次のような手順で問題を解くことができます。

手順1　マス目の問題を、二部グラフに対する操作の問題に言い換える（1-1. 節）
手順2　マス目の状態をもとに、二部グラフを構成する（1-1. 節）
手順3　各連結成分について、グラフの全域木を 1 つ取り出し、それ以外の辺を無視して考える（1-4. 節）
手順4　各連結成分のサイズをもとにして、操作 X（タイプ A）に全振りするか、操作 Y（タイプ B）に全振りするか決める（1-3. 節）
手順5　各連結成分について、「次数 1 の頂点を消す」など、適切に操作を行う （1-2. 節）

計算量は \(O(HW)\) です。操作回数は高々 \(H+W\) 回なので、手順5 では各操作について \(O(H+W)\) かけて愚直に「次数 \(1\) の頂点」を探しても十分高速に動作します。


2. サンプルコード

各プログラミング言語における想定解は、次の通りです。

posted:
last update: