AtCoder Regular Contest 135 C,D問題メモ
C - XOR to All
問題
- $N$ 個の整数 $A_1,A_2,...,A_N$ が与えられる
- 以下の操作を好きな回数行える（行わなくてもよい）
- 操作
- 現在の $A_i$ の中から整数を1つ選ぶ（$x$ とする）
- $A_i$ を全て、$A_i \ XOR \ x$ に置き換える
- 操作後、$A_i$ の総和としてあり得る最大値を求めよ
- $1 \le N \le 3 \times 10^5$
- $0 \le A_i \lt 2^{30}$
解法
具体的な数字で試すのもアリだが、ここは汎用性を持たせて記号で考えてみる。
N=5
a b c d e
↓ a に対して操作(* をXORの記号とする)
0 a*b a*c a*d a*e
↓ a*bに対して操作
a*b 0 b*c b*d b*e
↓ b*cに対して操作
a*c b*c 0 c*d c*e
すると結局、大事なのは「最後に操作した1個」であることがわかる。
その前にどのように他の数字に操作していても、最後の数字を、最初の数列に対して1回だけ操作したものと同じになる。
よって、「全く操作しない」か「どれか1個だけ操作した」ものだけ考えればよい。
どれか1個だけ操作したものを全て愚直に計算していくと $O(N^2)$ かかる。
前もって、各bit、初期状態の $A_i$ で '1' が立っている個数を数えておくと、$O(N \log{A_{max}})$ でできる。
A1 1 1 0 0 1 (25)
A2 0 0 1 0 1 ( 5)
A3 1 0 1 1 1 (23)
A4 1 0 0 0 1 (17)
-------------
3 1 2 1 4 '1'の立っている個数。下の桁から C0,C1,... とする
ここで $A_i$ の総和は、各bitごとに分割して計算できる。
「$k$ 桁目が表す2進数 $2^k$ 」×「$k$ 桁目が立っている $A_i$ の個数 $C_k$」として、合計すればよい。
25 + 5 + 23 + 17 = 70 3*16 + 1*8 + 2*4 + 1*2 + 4*1 = 70
それを踏まえて $A_1$ に対して操作すると、
- $A_i$ の $k$ 桁目が '1' なら、全て反転するので操作後に立っている個数は $N-C_k$
- $A_i$ の $k$ 桁目が '0' なら、変化しないので操作後に立っている個数は $C_k$
となるので、この当てはまる方に $2^k$ をかけて合計していけば、1つの $A_i$ に対し操作した結果が求まる。
D - Add to Square
問題
- $H \times W$ のマス目に整数 $A_{i,j}$ が書かれている
- 以下の操作を好きなだけ行える
- 操作
- $2 \times 2$ の範囲に一律、好きな整数 $x$ を足す
- 操作後の全マスの絶対値の総和 $\sum{|A_{i,j}|}$ を最小化したい
- その最小値と、最小値を達成できるマス目の状態の一例を求めよ
- $2 \le H,W \le 500$
上手な解法
市松模様に塗って黒になるマス目を全て正負逆転させて、これを $B$ とする。
$B$ 上でも、スコアの計算方法は $A$ と変わらない。
A B 1 2 3 1 -2 3 4 5 6 → -4 5 -6
$B$ 上での操作は2×2に以下を足す操作となり、行・列の総和に影響を及ぼさないことがわかる。
x -x -x x
$B$ の操作前の $i$ 行目の総和を $R_i$、$j$ 列目の総和を $C_j$ とする。
操作によってこれらは変わらないので、最適解でもその行、列にある数字の絶対値の合計を $|R_i|,|C_j|$ 未満にすることはできない。
さらにいうと、全体スコアは $\max(\sum_i{|R_i|},\sum_j{|C_j|})$ 未満にすることはできない。
行内の0を除く全ての符号が一致しているときに $|R_i|$ を達成でき、正負が入り交じっているとそれだけ余計に増える。これは列も一緒。
ある行の操作前 4 -5 6 → Ri=5 Riが同じ状態の例とスコア（絶対値の和） 1 2 2 → スコア 5 3 -2 4 → スコア 9
例えば $\sum_i{|R_i|}$ の方が大きいのであれば、各行、$R_i$ が正ならその行には正だけ、負なら負だけを置くことで全体スコア $\sum_i{|R_i|}$ を達成できる。
その時、$C_j$ は一部、つじつまを合わせるために正負が入り交じることがあるかも知れないが。
$B$ 上で構築した最適解を $D$ とする。
- $D$ の構築はどうしたらいい？
- 総和が一緒でありさえすれば、$B$ からどんな $D$ でも構築できるのか？
$D$ の構築
以下のようにするとできる。
- $R_i$ と $C_j$ がともに正の場合、$D_{i,j}$ に $\min(R_i,C_j)$ を配置、$R_i,C_j$ をその分減らす
- $R_i$ と $C_j$ がともに負の場合、$D_{i,j}$ に $\max(R_i,C_j)$ を配置、$R_i,C_j$ をその分増やす
$\sum_i R_i$ と $\sum_j C_j$ は等しいので、これを繰り返すと、どちらかが全て0になり、もう一方が残る。
（仮に両方残る場合、これ以上操作できないのだから、$R_i$ で残っているのが正ばかり、$C_j$ が負ばかり、という状態（または逆）しかあり得ないが、すると総和が一致しなくなり矛盾する）
$\sum_i{|R_i|},\sum_j{|C_j|}$ の2つのうち、大きい方が残ることになる。
仮に $R_i$ が残っているとする。適当な列 $j$ を1つ選んで、
- $R_1$ を合わせるために $B_{1,j}$ に $R_1$ を加算、帳尻を合わせるため $B_{2,j}$ と $R_2$ に $-R_1$ を加算
- $R_2$ を合わせるために $B_{2,j}$ に $R_2$ を加算、帳尻を合わせるため $B_{3,j}$ と $R_3$ に $-R_2$ を加算
- …
と決めていくと、（$C_j$ を全て0にした時点での）$R_i$ の総和は0のため、最後では必ず帳尻が合う。
ボトルネックとなる $R_i$ に対して、異なる符号のものが $B_{i,j}$ に置かれることがないので、 このように構築した場合、全体スコアは $\sum_i{R_i}$ を実現できる。
どんな $D$ でも構築できる証明
ある $D$ が決まったら、元の盤面 $B$ の左上から、枠を1ずつずらしながら$D$ に合致するように操作していくことができる。
末尾行と末尾列のみ、自由に操作できず最後に残るが、総和が一緒となるように $D$ を決めたので、これらの値も必ず $D$ に一致している。
解法2
まぁ結局は上の解法を、正負逆転させずにその都度 $i,j$ の差分で場合分けして解いているだけのような感じだが……
まず考えやすいよう、末尾行・末尾列を除いて全て0にする。
左上から枠をずらして操作していくとできる。
x = -3 x = 2 3 1 4 1 [0]-2 4 1 0 [0] 6 1 0 0 0 -5 5 9 2 6 → 2 6 2 6 → 2 8 4 6 → .. → 0 0 0 8 5 3 5 8 5 3 5 8 5 3 5 8 3 -5 7 16
操作を行や列方向に1つずつずらしながら連続して適用することを考えると、 2×2に限らず、ある $(i_1,j_1,i_2,j_2)$ に対して以下のように（複数操作を1回にまとめた）操作ができる。
(i2-i1)%2 == 1, (j2-j1)%2 == 1 のとき
j1 j2
i1 -x -x
i2 -x -x
(i2-i1)%2 == 0, (j2-j1)%2 == 1 のとき
j1 j2
i1 -x -x
i2 +x +x
(i2-i1)%2 == 1, (j2-j1)%2 == 0 のとき
j1 j2
i1 -x +x
i2 -x +x
(i2-i1)%2 == 0, (j2-j1)%2 == 0 のとき
j1 j2
i1 -x +x
i2 +x -x
ここで先ほど0にした各マス $i=0～H-2,j=0～W-2$ に対し、「$0$ から別の値にした方が得になる」場合を考える。
$(i,j,H-1,W-1)$ でこのような操作をすることを考える。
（0-indexで考え、$H-1,W-1$ は末尾行・末尾列を指す）
0 0 0 -5 0 0 0 8 3 -5 7 16
操作すると、$(i,j)$ は事前に0に揃えているので、確実に絶対値は増える。
$(i,W-1),(H-1,j),(H-1,W-1)$ は増えたり減ったりする。
操作の損得の前提として、以下を踏まえる。
- 操作する4個中、3個の絶対値を減らす方向に操作できるなら、した方が必ず得
- 操作する4個中、2個の絶対値を減らす方向に操作できるなら、して損しない
- 操作する4個中、2個の絶対値が増えてしまうなら、操作して得しない
$(i,j,H-1,W-1)$ に適当な操作をして $(i,W-1),(H-1,j)$ の絶対値をともに減らすことができるかどうかを調べる。
$(H-1,W-1)$ は複数の操作で繰り返し使われ、増えたり減ったりするので、
現在の操作が絶対値を増やす方向に寄与するのか減らす方向に寄与するのか評価しにくいが、、、いずれにしても操作すべきかどうかは前の2つだけで決められる。
- $(i,W-1),(H-1,j)$ の絶対値がともに減る場合
- 減るのが2個、増えるのが1個 → 仮に $(H-1,W-1)$ の絶対値が増えることになっても操作して損しない
- $(i,W-1),(H-1,j)$ の絶対値が一方は増え、一方は減る場合
- 減るのが1個、増えるのが2個 → 仮に $(H-1,W-1)$ の絶対値が減ることになっても操作して得しない
よって、貪欲に $(i,W-1),(H-1,j)$ の絶対値をともに減らせる場合だけ減らしていけばよい。
貪欲で良い証明
「操作 $(i,j,H-1,W-1)$ はマス目 $(i,W-1),(H-1,j)$ の絶対値をともに減らせるが、しない方がよい」というケースを考える。
操作したらその分 $(i,W-1)$ と $(H-1,j)$ の絶対値が減るので、 他でできたはずの操作ができなくなる（または操作可能回数が減る）可能性がある。
もし $(i,j,H-1,W-1)$ が得しない操作（最終的に $(H-1,W-1)$ の絶対値が増える方向に寄与してしまう操作だった）で、 そのためにできなくなった他の操作は得する操作だった場合、たしかに貪欲が成り立たなくなる。
しかし、できなくなる操作というのは $i$ が同じ、または $j$ が同じ操作に限られるが、 これらの操作は $(H-1,W-1)$ を増やすか減らすかも一致する。
よって、上記のようなケースは起こらず、貪欲でよいといえる。
これが最適解である証明
わかんない
まぁ、1番目の、市松模様に正負逆転させる上手い解法を知った後では、 末尾行と末尾列以外を0にする操作は「各行・各列の総和を求める」ことに結果的にはなっているし、 その後0にした箇所に数字を戻していくのも、市松模様の解法で正負が入り交じらないように $D$ を構築していく作業とやっていることは同じなので、 あってはいるんだろうなとは思うが、正負逆転のないままでこれが最善ということをきちんと言語化できない。
