ABC164 F - I hate Matrix Construction
問題
解法
まず、(行/列)ごとの制約はビットごとの論理(積/和)なので、ビットごとに独立に答えを求めればいいです。(以降、説明の都合のため、$a_{i,j}, U_i, V_i$ は0か1であるとします)
問題を扱いやすくするために、論理(積/和)の制約をその(行/列)にある $1$ の数の制約に言い換えます。
すると、各行ごとの1の数は、以下を満たしていなければならないことになります。(列の時も同様)
- $S_i = 0, U_i = 0$ のとき、$0$ 個以上 $N-1$ 個以下
- $S_i = 0, U_i = 1$ のとき、ちょうど $N$ 個
- $S_i = 1, U_i = 0$ のとき、ちょうど $0$ 個
- $S_i = 1, U_i = 1$ のとき、1個以上 $N$ 個以下
これは、行と列を頂点、マスを「行から列に張った辺」に置き換えることで、次のようなグラフの最大流問題に帰着できます。
$S$ から $T$ にフローを流すことにすると、次のように元の行列と対応します。
- $S$ から $i$ 行目への辺には、$i$ 行目の $1$ の数の和だけ流れる
- $i$ 行目から $j$ 列目への辺には、$a_{i, j}$ が $1$ なら流量1だけ流れ、 $0$ なら流れない
- $j$ 列目から $T$ への辺には、$j$ 列目の $1$ の数の和だけ流れる
これを最大流で解くときには、真ん中の辺は単に流量 $1$ とすればよいです。
行と列の制約は少し厄介で、$x$以上$y$以下流さなければいけないので、最小流量制限付き最大流となります。これは、この記事にあるテクニックを使えばいいです。(説明丸投げ)
https://snuke.hatenablog.com/entry/2016/07/10/043918
最大流を求めるのに Dinic 法を使うと、$N+4$ 頂点 $N^{2} + \Theta (N)$ 辺なので $ O(N^{4}) $ になって間に合わないように思えますが、グラフの形状の関係か、実際にはかなり早いです。
復元は、フローを流し切った後に流れているかどうかを確認すればよいです。これを $64$ 回繰り返せば答えを求めることができます。