ABC 276 Ex — Construct a Matrix

考察

積を0にしたい長方形と、1または2にしたい長方形では、0の役割が異なる。まず0を置けない領域を確定し、そこに置く1と2の条件を解こう。非零の積は2の個数の偶奇だけで決まり、長方形の偶奇は四隅の変数で表せる。これにより、マスの数よりはるかに少ない変数で行列を構成できる。

0を置ける場所を先に分ける

行列の大きさを N×NN\times N、条件数を QQ とし、行と列は1始まりとする。条件の番号を tt とし、長方形を Rt=[at,bt]×[ct,dt]R_t=[a_t,b_t]\times[c_t,d_t]、積を3で割った余りの指定を ete_t と書く。et≠0e_t\ne 0 の条件を非零条件、et=0e_t=0 の条件を0条件と呼ぶ。

非零条件の長方形には、0を一つも置けない。そのような長方形すべての和集合を UU とする。一方、UU の外のマスを0にしても非零条件は変わらず、0条件は満たしやすくなる。したがって、最後に UU の外をすべて0にすると決めてよい。

この方針では、各0条件が満たせるかどうかは「長方形に UU の外のマスがあるか」だけで決まる。残る問題は、UU の中に1と2をどう置いて非零条件を同時に満たすかである。いったん全マスを1か2で埋め、後から UU の外を0にする手順で考える。

積を偶奇へ、マスの変数を四隅の変数へ

0に置き換える前の各マスに、1を置くなら yi,j=0y_{i,j}=0、2を置くなら yi,j=1y_{i,j}=1 というビットを対応させる。22≡1(mod3)2^2\equiv1\pmod3 なので、積が1か2かは指数の和の偶奇だけで決まる。非零条件の右辺を、et=1e_t=1 なら st=0s_t=0、et=2e_t=2 なら st=1s_t=1 とすれば、条件は

⨁i=atbt ⨁j=ctdtyi,j=st\bigoplus_{i=a_t}^{b_t}\ \bigoplus_{j=c_t}^{d_t}y_{i,j}=s_t

となる。⊕\oplus は排他的論理和(XOR)で、0と1からなる体 F2\mathbb F_2 での加算である。0にはこの指数表現を使えないため、0条件をこの式へ混ぜない。

これで連立一次方程式になったが、マスをそのまま変数にすると最大 N2=4×106N^2=4\times10^6 変数になる。条件は高々2000本なので、一つの長方形を少数の変数で表す方法を探したい。通常の二次元累積XORなら、境界を0とした配列 PP により、長方形内のXORは

Pbt,dt⊕Pat−1,dt⊕Pbt,ct−1⊕Pat−1,ct−1P_{b_t,d_t}\oplus P_{a_t-1,d_t}\oplus P_{b_t,c_t-1}\oplus P_{a_t-1,c_t-1}

と四隅だけで書ける。そこで、この四隅の値を先に未知数として解き、後からマスを復元する。

ここでは 0≤i,j≤N0\leq i,j\leq N で0か1を値に持つ補助配列 pi,jp_{i,j} を用意し、添字0の行・列も自由な変数にする。通常の累積配列 PP と違い、p0,j=pi,0=0p_{0,j}=p_{i,0}=0 とは固定しない。それでもよい理由は、どのような pp に対しても、

yi,j=pi,j⊕pi−1,j⊕pi,j−1⊕pi−1,j−1(1≤i,j≤N)y_{i,j}=p_{i,j}\oplus p_{i-1,j}\oplus p_{i,j-1}\oplus p_{i-1,j-1} \qquad(1\leq i,j\leq N)

でマスを定めれば、長方形内のXORが必ず同じ四隅の式になるからである。実際、行方向にXORを取ると途中の項は2回ずつ現れて消え、

⨁i=abyi,j=pb,j⊕pa−1,j⊕pb,j−1⊕pa−1,j−1\bigoplus_{i=a}^{b}y_{i,j} =p_{b,j}\oplus p_{a-1,j}\oplus p_{b,j-1}\oplus p_{a-1,j-1}

となる。さらに列方向でも途中の項が消え、四隅だけが残る。境界の値が0であることは使っていない。

例えば N=2N=2 で p0,0=1p_{0,0}=1、他の値をすべて0とすると、復元されるビットは y1,1=1y_{1,1}=1、他は0である。[1,2]×[1,2][1,2]\times[1,2] 全体のXORは1で、四隅の式も p2,2⊕p0,2⊕p2,0⊕p0,0=1p_{2,2}\oplus p_{0,2}\oplus p_{2,0}\oplus p_{0,0}=1 になる。pp 自体が通常の累積XOR配列でなくても、長方形の式は正しく使える。

したがって、非零条件ごとに解く式は

pbt,dt⊕pat−1,dt⊕pbt,ct−1⊕pat−1,ct−1=stp_{b_t,d_t}\oplus p_{a_t-1,d_t}\oplus p_{b_t,c_t-1}\oplus p_{a_t-1,c_t-1}=s_t

でよい。式に現れる座標だけを集め、同じ座標を同じ変数として番号付けする。非零条件の本数を MM、異なる座標数を CC とすると、C≤4M≤4QC\leq4M\leq4Q である。座標は行と列を別々に圧縮するのでなく、組 (i,j)(i,j) をまとめてソートし、重複を除く。

連立方程式の一解を実際の行列へ戻す

各式の係数 CC ビットと右辺1ビットを連結し、一行のbitsetで持つ。列を順に見て、まだ使っていない行にその係数が1のものがあれば交換してピボット行にする。その下の、同じ列の係数が1の行へピボット行をXORする。右辺も一緒に更新する。

係数がすべて0なのに右辺が1の行が残れば矛盾なので No である。そうでなければ、ピボットを持たない自由変数を0にし、ピボット行を後ろからたどる。各ピボット変数は「右辺と、その行の右側にある係数1の変数すべてのXOR」で求まる。消去後に単に各行の右辺をピボット変数へ入れるだけでは、右側の項が残っている場合に誤る。

得られた値を対応する pp の座標へ戻し、式に一度も現れなかった座標には0を入れる。未出現の値はどの方程式にも影響しないため、この選択で解を失うことはない。これは、式には現れる自由変数を0に選ぶ操作とは別である。

あとは四隅の差分の式から全マスの yi,jy_{i,j} を計算し、0なら1、1なら2に戻す。四隅の式を満たす pp から作ったため、すべての非零条件を満たす。最後に UU の外だけを0へ置き換える。

0条件は被覆数と累積和で調べる

各長方形をマスごとに塗ると、最悪で O(QN2)O(QN^2) かかる。各マスを覆う非零条件の本数を求めるには、整数の二次元いもす法を使う。最初は全要素0の差分配列 DD に、各非零条件について

Dat,ct+=1,Dbt+1,ct−=1,Dat,dt+1−=1,Dbt+1,dt+1+=1\begin{aligned} D_{a_t,c_t}&\mathrel{+}=1, &D_{b_t+1,c_t}&\mathrel{-}=1,\\ D_{a_t,d_t+1}&\mathrel{-}=1, &D_{b_t+1,d_t+1}&\mathrel{+}=1 \end{aligned}

と加える。両軸で累積して得られる値を ki,jk_{i,j} とすれば、それがマスを覆う非零条件の本数になる。ki,j>0k_{i,j}>0 が UU の内側、ki,j=0k_{i,j}=0 が0を置けるマスである。複数の長方形で覆われても0を置けないことは変わらないので、被覆数にはXORを使わない。

0を置けるなら zi,j=1z_{i,j}=1、そうでなければ0とし、その個数の二次元累積和 HH を作る。ここでは通常の累積和なので H0,j=Hi,0=0H_{0,j}=H_{i,0}=0 とし、

Hi,j=zi,j+Hi−1,j+Hi,j−1−Hi−1,j−1H_{i,j}=z_{i,j}+H_{i-1,j}+H_{i,j-1}-H_{i-1,j-1}

で埋める。各0条件の長方形に含まれる0の個数は

Hbt,dt−Hat−1,dt−Hbt,ct−1+Hat−1,ct−1H_{b_t,d_t}-H_{a_t-1,d_t}-H_{b_t,c_t-1}+H_{a_t-1,c_t-1}

で O(1)O(1) で求まり、これが正なら条件成立、0なら No である。例えば2マスを別々の非零条件が覆っていれば、両方を含む0条件は不可能になる。一つの非零長方形が0条件全体を覆っているかだけを調べても、この矛盾は見つからない。

処理をまとめると、非零条件から四隅の方程式と被覆数を作り、方程式の一解を求め、0を置けるマスの累積和で全0条件を調べる。両方の判定を通れば、四隅の差分から1と2を復元して被覆数0のマスを0にし、Yes と行列を出力する。非零条件は元の四隅の式を再計算して O(M)O(M)、0条件は上の個数を使って合計 O(Q)O(Q) で確認できる。検査のために各長方形内を走査する必要はない。

典型の発動条件

multiplicative conditionの指数化

非零元の積を指定する条件があり、それらが小さな巡回群をなすときに使える。本問では1と2を2の指数へ写し、指数の和を2で割った余り、つまりXORの条件へ変える。0は非零元の群に属さないため、先に分けて扱う。

rectangle queryのprefix corner化

長方形内の和やXORが線形制約になる一方、マスを直接変数にすると多すぎるときに候補になる。式に現れる四隅だけを変数にすれば、その数は条件数の4倍以下になる。ただし、変数を解いた後に元のマスへ戻せることを差分と相殺で確かめる必要がある。

bitset Gaussian elimination

F2\mathbb F_2 上で数千規模の変数と式から可解性と一解が必要なときに使う。行の加算はbitsetのXORでまとめられる。矛盾行の検出だけでなく、自由変数の選択と後退代入までが構成の一部になる。

問題固有の要素

非零条件は0の禁止領域を作り、0条件は長方形内に少なくとも一つ0を要求する。この二つの役割に注目すると、許可されたマスをすべて0にする選択が、すべての0条件に同時に有利だと分かる。0の位置を探索せずに済むのは、0を増やして困る条件が非零条件だけだからである。

別の問題でも、ある印を置くことの禁止条件と存在条件が分かれていれば、許可領域の全体に印を置けないか考えたい。ただし、印の個数上限や「ちょうど一つ」という条件があれば、この単調性は使えない。

正当性

非零条件の長方形の和集合を UU とする。合法な行列の UU 内の値は必ず1か2である。UU 外にある0を仮に1へ変えても非零条件は保たれるので、全マスを指数ビットへ写し、境界0の通常の累積XORを取れば、四隅の連立方程式の解が得られる。したがって、この方程式が矛盾するなら合法な行列は存在しない。

逆に、補助配列 pp の任意の解を四隅の差分でマスへ戻すと、長方形内のXORでは途中の項が相殺され、指定された右辺に等しくなる。未出現の座標を0にしても式は変わらず、復元した1と2は全非零条件を満たす。

UU 外をすべて0にしても非零条件は変わらない。このとき0条件が成立する必要十分条件は、長方形内に UU 外のマスがあることであり、その有無は被覆数0のマスの累積和で判定できる。そのようなマスがなければ、どの合法な行列でも長方形内はすべて非零で積も非零となるため不可能である。よって、方程式と全0条件の判定を通った場合に構成する行列は、元の全条件を満たす。

実装上の注意

  • 四隅の座標には添字0を含める。本解説の pp は自由な補助配列であり、添字0の値を消去後に勝手に0へ戻してはいけない。個数の累積和 HH は境界0の通常の配列である。
  • いもす法では bt+1,dt+1b_t+1,d_t+1 が N+1N+1 になる。差分配列は添字 0,…,N+10,\ldots,N+1 を持てる大きさに確保する。
  • 同じ長方形に非零の指定1と2が来れば、係数が同じで右辺だけ違うため消去で矛盾する。同じ長方形に0と非零の指定が来れば、0を置けるマスがなく、0条件の判定で落ちる。二種類の不可能性を分ける。
  • 非零条件が一つもなければ M=C=0M=C=0 で、消去を飛ばしてよい。全マスが UU の外なので、すべて0の行列ですべての条件を満たす。

復習の核

  • 積を指数の和へ変える前に、0をどこへ置けるかを分ける。非零元に使う変換を0へ広げない。
  • 累積値を先に変数として解くなら、差分による復元と長方形での相殺まで確認する。境界の値を自由にできる理由もここにある。
  • 「少なくとも一つ印がある」を全許可領域への配置で満たせるなら、残るのは個数が正かの検査である。二次元いもす法で禁止領域を作り、累積和で存在判定へつなぐ。

計算量と制約

時間

非零条件数を MM、圧縮した四隅の変数数を C≤4MC\leq4M とする。bitsetの1語のビット数を ww とし、右辺を含む一行の語数を L=⌈(C+1)/w⌉L=\lceil(C+1)/w\rceil とする。

座標のソートと番号付けに O(Qlog⁡(Q+1))O(Q\log(Q+1))、行列の初期化に O(ML)O(ML) かかる。消去のピボット探索・係数検査に O(MC)O(MC)、高々 min⁡(M,C)\min(M,C) 本のピボットによる行XORに O(Mmin⁡(M,C)L)O(M\min(M,C)L) かかる。自由変数を0とする一解の後退代入は、各ピボット行の係数を走査して O(MC)O(MC) で行える。

被覆数、0を置けるマスの累積和、全マスの復元は合計 O(N2+Q)O(N^2+Q)。元の非零条件と0条件の検査は合計 O(Q)O(Q)、行列の出力は O(N2)O(N^2) である。全体は

O(N2+Qlog⁡(Q+1)+ML+MC+Mmin⁡(M,C)L)O\left(N^2+Q\log(Q+1)+ML+MC+M\min(M,C)L\right)

となり、M≤Q, C≤4QM\leq Q,\ C\leq4Q を使うと O(N2+Q2+Q3/w)O(N^2+Q^2+Q^3/w) と評価できる。M=0M=0 の場合は消去部分を行わない。

空間

行列のbitsetに O(ML)O(ML) 語、補助配列・被覆数・個数の累積和に O(N2)O(N^2)、入力と座標に O(Q)O(Q) を使う。合計 O(N2+Q+ML)O(N^2+Q+ML) 語である。

制約との対応

公式制約は 1≤N,Q≤20001\leq N,Q\leq2000、1≤at≤bt≤N1\leq a_t\leq b_t\leq N、1≤ct≤dt≤N1\leq c_t\leq d_t\leq N、et∈{0,1,2}e_t\in\{0,1,2\}。入力はすべて整数で、実行時間制限は4秒、メモリ制限は1024 MiBである。

マスは最大400万個なので、復元・被覆数の集計・累積和・出力は全マスを走査できる。一方、消去に用いるのは最大2000行・8000変数であり、w=64w=64 なら右辺を含む一行は最大126語で済む。消去には固定長または語配列のbitsetを使い、1ビットずつ行を加算しない。ki,j≤Qk_{i,j}\leq Q、Hi,j≤N2H_{i,j}\leq N^2 なので、被覆数と個数は符号付き32ビット整数に収まる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Construct a Matrix の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 線形方程式・rank

主題
  • 線形方程式・rank: 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 線形方程式・rank

    補助タグ: bitsetによるword並列集合演算 構成解・witness復元 座標・値の順序保存圧縮 累積和・差分配列

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 線形方程式・rank

    • 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題