競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 133C

ARC133C

\(\equiv\)は\(mod\ K\)とする. 必要条件や,上限の見積もりを考える.

判定問題
最大の前に,簡単のため判定問題を考える. 行列において掛かれた値の和は, 行方向と列方向それぞれで集計すれば, \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) が分かるので,これが必要条件. これは十分条件でもある.
実際,左上の行列を\(0\)で埋めておいて, 一番下の行と一番右の列で帳尻を合わせることを考えると, 一意に決まる. 一番右下のマスの埋め方に問題がないことは, \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) から確かめられる.

 

最大化
次に最大化を考える. 以下, \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) を満たすとする.

上界の見積もり:
とりあえず,判定問題と似た手法を取りたい. つまり,まずは何かで埋めてしまって,後で帳尻合わせを考える. まず,\(K-1\)で全てのマスを埋めておくおき, その後で条件を満たすように減らしていく.
行,対して減らすべき値を\(C_{i}, D_{j}\)と定める. すなわち,各\(i \in H,\ j \in W\)に対して \begin{align} A_{i} = (K-1)W - C_{i},\\ B_{j} = (K-1)H - D_{j} \end{align} となるように定める. \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) より, \(\sum_{i \in H} C_{i} \equiv \sum_{j \in W} D_{j}\) となる.
\(Z := max(\sum_{i \in H} C_{i}, \sum_{j \in W} D_{j}) \) とおく. すべてのマスに\(K-1\)を書いたのち,最低\(Z\)回は,マスを選んで\(-1\)する必要がある. つまり,\((K-1)HW - Z\)が上界になる. 上界の実現:
\(\sum_{i \in H} C_{i} \equiv \sum_{j \in W} D_{j}\) より,\(C_{0}\) or \(D_{0}\)に\(K\)の倍数を足すことで \(\sum_{i \in H} C_{i} = \sum_{j \in W} D_{j}\) とできる. \(=\)とすると,\(Z = \sum_{i \in H} C_{i} = \sum_{j \in W} D_{j}\) となる. また,この操作後でも,任意の\((i,j) \in H \times W\) に対して \(min(C_{i}, D_{j}) \leq K-1\) が成立する.
よって,次を繰り返せばよい. 「\((i,j) \in H \times W\)であって, \(C_{i} \geq 0\) and \(D_{j} \geq 0\) となるものをとり,マス\((i,j)\)の値を1減らす.」 ここで, \(min(C_{i}, D_{j}) \leq K-1\) であることから,この操作後にマスの値が負になることはない.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"