かしのブログ

競技プログラミングとか

AtCoder Beginner Contest 164 F - I hate Matrix Construction

AtCoder bitwise Dinic法 最大フロー

問題

次の条件を満たす N\times N整数行列が構築可能なら1つ求める。

  • 0 \leq a_{i,j} \lt 2^{64}
  • 行のbitwise-or/bitwise-andが U_i
  • 列のbitwise-or/bitwise-andが V_i

atcoder.jp

考察

bitwise-or/bitwise-andなので、桁ごとに独立して考えてよい。 桁毎に分けると、 U_i, V_iは 0, 1 のいずれか。 そのように考えると、各行/列の条件は以下の4つのいずれかである。（）内は、本記事でのこれらの状態の省略記法である。

  • bitwise-andが1なら、すべて黒である（ \forall B）
  • bitwise-orが1なら、1つ以上が黒である（ \exists B）
  • bitwise-orが0なら、すべて白である（ \forall W）
  • bitwise-andが0なら、1つ以上が白である（ \exists W）

解法1

強い制約として、 \forall B, \forall Wの行と列はすぐに決まる。 また、行列ともに \exists B (\exists W)も、その色を使うことにしてよい。 よって、考える必要があるのは行列で \exists B,\exists Wが交差する、下図の?マークの箇所である。

\forall B \exists B \exists W \forall W
\forall B111x
\exists B11?0
\exists W1?00
\forall Wx000

2行目3列目の「行が \exists Bで、列が \exists W」な場合に注目する。 この列以外で、「 \forall B, \exists B」の列が存在すれば、白で確定させていい。また、この行以外で「 \forall W, \exists W」の行が存在しても黒で確定させられる。そうでない場合を考える。このような場合、行列の状況は下図のようになる。

\exists W \forall W
\forall B1x
\exists B?0

ここで、 \exists Bである行の数を h、 \exists Wである列の数を wとする。

  • h = w = 0のとき、すでに塗り終えている
  • h = 0, w \gt 0 のとき、白になる行を作れないので実現できない（ w = 0, h \gt 0 のときも同様）
  • h = 1のとき、すべて白にしないと \exists Wの列の制約を満たせないので実現できない（ w = 1のときも同様）
  • h, w \leq 2を仮定すると、（なんとでも実装できるが）行列のインデックスの和の偶奇で 0, 1と市松模様に塗ると \exists B, \exists Wの制約を満たせる

実装1

atcoder.jp

解法2

twitterでみた、最大フローを使って解く方法。

行/列を頂点とみなし、任意の行から列に容量1の辺を張る。 a_{i, j}は、行 iの頂点と列 jの頂点に張った辺のフローが1なら黒く、0なら白く塗ることになる。

行/列の条件は、以下のように言い換えられる。

  • \forall B \Rightarrow黒マスの個数 \in [N, N]
  • \exists B \Rightarrow黒マスの個数 \in [1, N]
  • \forall W \Rightarrow黒マスの個数 \in [0, 0]
  • \exists W \Rightarrow黒マスの個数 \in [0, N-1]

まず、黒マスの必要量（黒マスの個数の下限）を確保することを考える。 起点→行→列→終点のようなパスについて、

  • 起点→行 \cdots任意の行に、容量がその行の黒マスの必要量の辺
  • 行→列 \cdots任意の行と列の組み合わせに容量1の辺
  • 列→終点 \cdots任意の列に、容量がその列の黒マスの必要量の辺

このグラフの起点から終点への最大フローは、 \min(行の黒マスの必要量の総和, 列の黒マスの必要量の総和 )になる。 行の黒マスが必要量に足りていないとき、列の余剰量(=最大量-必要量)を使って黒マスの必要量を塗ることができる。 ここで、先ほどのグラフに、次のような起点→行→列→終点のパスを追加する。

  • 起点→行 \cdotsさっきのあまり
  • 行→列 \cdotsさっきのあまり
  • 列→終点 \cdots任意の列に、容量がその列の黒マスの余剰量の辺

新たな起点から終点への最大フローは、行の必要量に足りなかった分を列の余剰量で満たす、ようになる。行と列を入れ替えて同じ処理を行うと、行/列それぞれの必要量を他方の余剰でまかなうことができた。

以上の処理で、可能な範囲で必要最低限の黒マスの塗り終わっている。 行必要量→列必要量と行必要量→列余剰量での最大フローの和が行の必要量の総和と等しければ、行は十分塗り終わっている。そうでない場合は、必要なのに塗れていな行があるため、実現不可能。列についても同様。

最大フローはDinic法を用いて求められる。

実装2

atcoder.jp

感想

実装1は数独とかヤジリンみたいな推論ゲームで、落ち着いてやれば難しくはないけど、コンテスト時間内で正確にやるのは結構しんどそう

実装2みたいな問題の置き換えができると、場合分けが少なくなってミスが減らせそう。