E - グリッドの塗りつぶし / Grid Filling Editorial by admin
GPT 5.4 High概要
行集合 \(R\) を固定すると、各列 \(j\) は「選ぶと何点増えるか」が独立に決まります。
この性質を使って、\(2^{H+W}\) 通りを全探索する代わりに、片方（小さい方の次元）の部分集合だけを全探索して最大値を求めます。
考察
まず、行と列を両方そのまま全探索すると、選び方は
\(2^H \times 2^W = 2^{H+W}\)
通りあります。
\(H, W \le 19\) なので、最大で \(2^{38}\) 通りとなり、これは到底間に合いません。
1. 行集合 \(R\) を固定して考える
\(R\) を固定したとき、塗られる値の合計 \(S\) は包除原理より
\[ S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} \sum_{j \in C} A_{i,j} \]
です。これを整理すると、
\[ S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \left( \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} A_{i,j} \right) \]
となります。
ここで、列 \(j\) を選んだときの「追加得点」を
\[ b_j = \sum_{i \notin R} A_{i,j} \]
とおくと、
\[ S = \left(\text{選んだ行の総和}\right) + \sum_{j \in C} b_j \]
と書けます。
2. 固定した \(R\) に対する最適な \(C\)
上の式では、列ごとの寄与が完全に独立です。
したがって各列 \(j\) について、
- \(b_j > 0\) なら選ぶ
- \(b_j \le 0\) なら選ばない
のが最適です。
よって、固定した \(R\) に対する最大値は
\[ f(R) = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j=1}^{W} \max(0, b_j) \]
になります。
つまり、問題は
- 行集合 \(R\) を全探索する
- そのたびに各列の \(b_j\) を求める
だけで解けます。
3. ここで素朴にやると少し重い
各 \(R\) ごとに毎回 \(b_j = \sum_{i \notin R} A_{i,j}\) を最初から計算すると、
- 部分集合の数：\(2^H\)
- 各部分集合で全マスを見る：\(O(HW)\)
なので、全体で
\[ O(2^H \cdot H \cdot W) \]
になります。
制約内でも理論上はギリギリですが、Python では少し重めです。
そこで、「隣り合う部分集合の差が 1 行だけ」になるように列挙すると、更新を高速化できます。
4. Gray code を使うと 1 行だけ増減する
通常の部分集合列挙では、次の集合に移ると複数の行が同時に変わることがあります。
しかし Gray code 順に列挙すると、連続する 2 つの集合で変わるビットはちょうど 1 個です。
つまり、
- 1 行追加した
- または 1 行削除した
だけが毎回起こります。
すると、各列の \(b_j\) もその 1 行分だけ更新すればよくなります。
5. 列側の情報をどう持つか
各列について
\[ \text{resid}[j] = \sum_{i \notin R} A_{i,j} \]
を持っておきます。
これは「今の \(R\) に対して、列 \(j\) を選んだときに増える得点」です。
最初は \(R = \emptyset\) なので
\(\text{resid}[j] = \sum_i A_{i,j}\)行 \(r\) を新たに \(R\) に入れると、その行はもう「列を選んだときの追加分」ではなくなるので
\[ \text{resid}[j] \mathrel{-}= A_{r,j} \]
- 逆に行 \(r\) を \(R\) から外すと
\[ \text{resid}[j] \mathrel{+}= A_{r,j} \]
です。
また、固定した \(R\) に対する列の最適値は
\[ \sum_j \max(0, \text{resid}[j]) \]
なので、これも毎回再計算するのではなく、
各列の値が変わるたびに「正の部分の総和」だけ更新すればよいです。
6. 小さい方の次元を全探索する
この問題は行と列が対称です。
したがって、もし \(H > W\) ならグリッドを転置して、常に
\[ H \le W \]
としておけば、列挙する部分集合数を \(2^{\min(H, W)}\) に抑えられます。
これにより計算量は
\[ O(2^{\min(H,W)} \cdot \max(H,W)) \]
になります。
アルゴリズム
- \(H > W\) ならグリッドを転置して、常に \(H \le W\) にする。
- 各行の総和
row_total[i]、各列の総和total_col[j]を求める。 - 初期状態を \(R = \emptyset\) とする。
row_sum = 0resid = total_colpos_sum = \sum_j \max(0, resid[j])- このときの答え候補は
row_sum + pos_sum
- 行集合 \(R\) を Gray code 順に列挙する。
- 1 つ前の集合との差分から、「どの行が追加/削除されたか」を求める。
- その 1 行に対して
row_sumを更新- 全列の
resid[j]を更新 pos_sumも「古い値が正だったか」「新しい値が正か」を見て更新
- 各状態で
row_sum + pos_sumを答え候補として最大値を取る。 - 最後に最大値を出力する。
計算量
- 時間計算量: \(O(2^{\min(H,W)} \cdot \max(H,W))\)
- 空間計算量: \(O(HW)\)
実装のポイント
転置して小さい方を全探索するのが重要です。
Gray code は
g = k ^ (k >> 1)で作れます。連続する Gray code の差分
diff = cur ^ gには、変化した 1 ビットだけが立ちます。 その位置をbit_length() - 1で取り出しています。pos_sumは毎回全列を走査して計算し直すのではなく、更新された列ごとに- 変更前に正なら引く
- 変更後に正なら足す とすることで高速化しています。
値の合計は大きくなるので、C++ などで書く場合は
long longが必要です。ソースコード
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
H = next(it)
W = next(it)
A = [[next(it) for _ in range(W)] for _ in range(H)]
if H > W:
A = [list(row) for row in zip(*A)]
H, W = W, H
row_total = [sum(row) for row in A]
total_col = [0] * W
for i in range(H):
row = A[i]
for j, v in enumerate(row):
total_col[j] += v
resid = total_col[:]
pos_sum = sum(x for x in resid if x > 0)
row_sum = 0
ans = pos_sum
cur = 0
for k in range(1, 1 << H):
g = k ^ (k >> 1)
diff = cur ^ g
bit = diff.bit_length() - 1
row = A[bit]
if (g >> bit) & 1:
row_sum += row_total[bit]
for j, v in enumerate(row):
old = resid[j]
if old > 0:
pos_sum -= old
new = old - v
resid[j] = new
if new > 0:
pos_sum += new
else:
row_sum -= row_total[bit]
for j, v in enumerate(row):
old = resid[j]
if old > 0:
pos_sum -= old
new = old + v
resid[j] = new
if new > 0:
pos_sum += new
total = row_sum + pos_sum
if total > ans:
ans = total
cur = g
print(ans)
この解説は gpt-5.4-high によって生成されました。
posted:
last update: