なんかいろんな解法があるのと、僕の解法が別の問題を解いた時に使った解法と似ていたので記事にします。
このリンク にも問題がいずれ出てくると思います。
問題概要
$N\times N$ の正方行列 $A,B$ が与えられるので、以下の操作を $A$ に対して好きなだけして $B$ にすることが可能か判定してください。
整数 $i,x$ を選んで、 $i$ 行目の全ての数に $x$ を足す。
整数 $i,x$ を選んで、 $i$ 列目の全ての数に $x$ を足す。
整数 $i,x$ を選んで、 $a-b\equiv i$ を満たす $a$ 行目 $b$ 列目の全ての数に $x$ を足す。
$1\leq N \leq 1000$
解法
$X_{i,j}=B_{i,j}-A_{i,j}$ とします。
この問題は以下の条件を満たす長さ $N$ の整数列 $R,C,D$ が存在すれば良いです。
$\forall i,j (R_{i}+C_{j}+D_{i-j}+X_{i,j}=0)$
添字は 0-index で全て $\pmod{N}$ とします。
$(i,j),(i+1,j+1)$ について考えて差分を取ると以下が成り立つ必要があります。
$\forall i,j ((R_{i+1}-R_{i})+(C_{j+1}-C_{j})+(X_{i+1,j+1}-X_{i,j})=0)$
ここで、 $P_{i}=R_{i+1}-R_{i},Q_{j}=C_{j+1}-C_{j},Y_{i,j}=X_{i+1,j+1}-X_{i,j}$ とすると以下が成り立ちます。
$\forall i,j (P_{i}+Q_{j}=-Y_{i,j})$
$i=0$ について、上の式の和を取ると以下が成り立ちます。
$NP_{0}+\sum Q=-\sum Y_{1}$
$\sum Q=\sum (C_{i+1}-C_{i})=\sum C -\sum C=0$ より、
$P_{0}=\frac{-\sum Y_{1}}{N}$ が成り立ちます。
$P_{0}$ を決めると $P,Q$ は存在するなら全て定まります。
このとき、 $P_{0}$ が整数である必要があり、 $\sum P=0$ が成り立つ必要があります。
$R,C,D$ が存在するとき、 $R_{0}=0$ かつ $C_{0}=0$ の解が存在します。
よって、$P,Q$ が求まっていることから $R_{0}=C_{0}=0$ とすることで $R,C$ が決まります。
ここまで来れば $i=0$ のときついて $(R_{i}+C_{j}+D_{i-j}+X_{i,j}=0)$ の式をみることで $D_{i,j}$ が求まります。あとは全ての $i,j$ に対して式が成り立っているか見ればいいです。
さまざまな解法
行や列の操作に対して普変な量を見つけてそこから求めています。
tatyam の解法
D 簡単枠
— tatyam (@tatyam_prime) 2023年5月4日
斜めに合計すると、縦と横の影響は全体加算なので、N の倍数の加算で全体を定数にする必要がある
G 木 DP でこの先の最大値を計算しておいて、ダブリングとかでパスからの最大値が取れるね〜 (実装なし)
L Library Checker で見た (実装なし)
M L の経路版ですか？
斜めに足す数が和を見ることで簡単に求まります。
olphe さんの解法
A むずかしい
— olphe (@_olphe) 2023年5月4日
D 縦に足す数と横に足す数は明らかなので、斜めで調整できるか調べる
J Trieをいじりつつにぶたん
これはさっきの斜めのやつを縦、横どっちもやって、最後に斜めをするという解法です。
後ろ二つの解法を見るとさっきの解法がかなり遠回りに見えますが、この解法はこの前の週のuniversal cup の問題にも応用できます。
問題概要
一辺が $N$ の正三角形のグリッド状にランプが並んでいて、全てのランプについて光っているか光っていないかの情報が与えられます。
ある辺に平行な列を一つ選び、その列上のランプのオンオフを切り替えるという操作を繰り返して全てのランプを消せるかどうか判定してください。
解法
下のようにランプに添字をします。
(0,0)
(0,1) (1,0)
(0,2) (1,1) (2,0)
(0,3) (1,2) (2,1) (3,0)
初めランプ $(i,j)$ がついているとき $X_{i,j}=1$ そうでないとき $X_{i,j}=0$ とすると、以下が成り立つ長さ $N$ の数列 $A,B,C$ が存在すれば良いです。
$\forall i,j \;XOR(A_{i},B_{j},C_{i+j},X_{i,j})=0$
これについても $(i,j),(i+1,j-1)$ について考えると以下が成り立ちます。
$XOR(A_{i+1},A_{i},B_{j},B_{j-1})=XOR(X_{i,j},X_{i+1,j-1})$
よって、 $P_{i}=XOR(A_{i+1},A_{i}),Q_{j}=XOR(Q_{j+1},Q_{j})$ とすることで、
いくつかの $(i,j)$ のペアについて $XOR(P_{i},Q_{j})$ の値に関する条件がわかります。
これら全てを満たす $P,Q$ が存在するか否かは二部グラフの判定と同じように求めれば良いです。
$P,Q$ が存在すれば $A,B,C$ も存在することが示せるので ok です。
