ABC 277 F — Sorting a Matrix

考察

行と列をどう並べても、もとの非零値の大小は変えられない。まずは非零値だけが小さい順に現れる並べ方を探し、0を埋められることは最後に確かめよう。目標の順序は「先の行の値が後の行の値以下」と「各行を左から読むと非減少」の二つに分けられる。

非零値を持つ行 ii の最小値を mim_i、最大値を MiM_i とする。この行を行 jj より前に置くには、Mi≤mjM_i\leq m_j が必要であり、これで両行の全ての非零値の比較を満たせる。そこで、全零行をいったん除き、行を (mi,Mi)(m_i,M_i) の辞書順、つまり最小値が小さい順、同じなら最大値が小さい順に並べる。隣接する行で「前の最大値 ≤\leq 次の最小値」を全て確認する。同じ最小値のとき、例えば区間 [2,2][2,2] は [2,5][2,5] より先に置く必要がある。全零行は既知値の制約を持たないので、先頭にまとめて置いてよい。

次は列順である。各行で、小さい非零値を持つ列は大きい非零値を持つ列より左でなければならない。この前後関係を有向辺で表し、全行の制約を一つのグラフへ集めれば、列の並べ替えはトポロジカル順序の存在判定になる。ただし、列数を WW とすると、列の組ごとに直接辺を張る方法では1行だけで O(W2)O(W^2) 本になり得る。

必要なのは、ある値の列を全て次の値の列より前へ置くことだ。同じ行の非零要素を (値,列番号)(\text{値},\text{列番号}) の組として取り出して値でソートし、等しい値を持つ列を一つの群にまとめる。値の小さい順にこれらを G1,…,GrG_1,\ldots,G_r とする。行 ii の隣接群 Gk,Gk+1G_k,G_{k+1}(1≤k<r1\leq k<r)ごとに新しい補助頂点 bi,kb_{i,k} を作り、次の辺を張る。

  • GkG_k の全ての列頂点から bi,kb_{i,k} へ張る。
  • bi,kb_{i,k} から Gk+1G_{k+1} の全ての列頂点へ張る。

例えば一行が (2,2,5,0)(2,2,5,0) なら、G1={1,2}G_1=\{1,2\}、G2={3}G_2=\{3\} なので、辺は 1→bi,11\to b_{i,1}、2→bi,12\to b_{i,1}、bi,1→3b_{i,1}\to3 となる。列1と列2はどちらも列3より先になるが、この行の制約では列1と列2の前後を決めない。列4の0からも辺を作らず、他の行の制約に任せる。等しい値の列を一本の鎖で結ぶと、この自由度を失い、本来可能な並べ方を排除しかねない。

群が三つ以上あっても、G1G_1 から G2G_2、G2G_2 から G3G_3 へと経路がつながるので、推移性により離れた群の全比較を表せる。各列が辺に関わるのは、その行で前後の群との境界に高々1回ずつであり、辺数は非零要素数に比例する。実列の頂点は全行で共有し、補助頂点は行・境界ごとに別々に作る。

行区間の検査に成功したら、この圧縮グラフを入次数0の頂点から順に取り除く。補助頂点を含む全頂点を取り出せなければ有向閉路があるので No。全頂点を取り出せたら、その順序から補助頂点だけを除いたものが、必要な実列の順序になる。行区間の順と組み合わせれば、0を除いた値は全体で非減少になる。あとは先頭の0を1、それ以降の0を直前の値で埋めればよく、答えは Yes である。判定だけを求めるので、実際の並べ替えや補完を出力する必要はない。

典型の発動条件

行列sorting条件の独立化

行と列の置換が互いの判定条件を変えず、目標を行間と行内に分けられるときは、それぞれを独立に解けるか考える。本問では、行間は非零値の区間、行内は全行で共有する列の前後関係として表せる。

dense precedenceの補助頂点圧縮

ある群の全要素を別の群の全要素より前へ置く制約は、「前の群 →\to 補助頂点 →\to 後の群」で表せる。二群の大きさの積だけあった辺を、和に減らせる。大小関係の推移性が使えるなら、隣接群の間だけを結べばよい。同値要素へ不要な前後関係を課していないかも確認する。

問題固有の要素

0には任意の正の整数を入れられるため、非零値の順序だけを決めた後で、直前の値を延ばすように補完できる。これは、正数を入れるという制約と、同値を許す非減少条件に支えられている。

別の問題で自由に値を埋めるときも、既知値を抜き出して並べるだけでよいか考えよう。ただし、埋められる整数の範囲がマスごとに異なる、全て異なる値が必要、といった条件が加われば、隙間を必ず埋められるとは限らない。

正当性

可能な並べ方が存在するなら、先の行の非零値は後の行の非零値以下なので、行区間の端点は Mi≤mjM_i\leq m_j を満たす。このとき最小値も昇順になる。同じ最小値 aa の行どうしでは、先に置ける区間は [a,a][a,a] に限られるため、最大値も昇順にしてよい。従って、可能なら (mi,Mi)(m_i,M_i) の辞書順での隣接区間検査も通る。

列については、補助頂点を通る経路が、隣接する値群だけでなく離れた値群の全比較も強制する。逆に、全ての大小関係を満たす実列の順序があるなら、各 bi,kb_{i,k} を GkG_k の最後の列と Gk+1G_{k+1} の最初の列の間へ挿入できる。各補助頂点は実列との辺だけを持つので、同じ隙間に複数置く場合も矛盾しない。従って、圧縮グラフがDAGであることと、必要な列順が存在することは同値である。

両検査を通れば、行区間の順と実列のトポロジカル順を同時に使える。列の置換は各行の最小・最大値を変えず、行の置換は各行内の列順制約を変えないためである。この行列を行ごとに左から右、上から下へ読むと、行内でも行をまたいでも、0を除いた値は非減少になる。

そこで、その読み順で最初の非零値より前の0を1にし、それ以降の0を直前の値で埋める。非零値は正で、次の非零値は直前の非零値以上なので、どの位置も非減少性を保つ。全零なら全て1でよい。よって両検査の成功は必要かつ十分である。

実装上の注意

  • 行を mim_i だけでソートせず、(mi,Mi)(m_i,M_i) の辞書順にする。同じ最小値では、全ての非零値がその最小値と等しい行を先に置く。
  • 全零行は区間検査から除く。非零の値群が0個または1個なら、その行から辺も補助頂点も作らない。
  • 補助頂点には、実列の頂点と重ならない通し番号を振る。行が異なる境界に同じ番号を使わない。
  • 入次数0の頂点は、非零要素がない列や補助頂点も含めて全て候補にする。処理数は実列数だけでなく、作成した全頂点数と比較する。
  • 補完は行をまたいだ読み順で行う。前の行の末尾の値も引き継ぎ、行頭ごとに1へ戻さない。問題文では補完が置換より先だが、構成した値を元のマスへ対応させれば、その手順でも同じ完成行列を得られる。

復習の核

  • 多数の大小比較は、等しい値を群にまとめ、隣接群の全対制約を補助頂点で圧縮できないか考える。
  • 二つの必要条件で十分と言うには、両方の結果を同時に使える理由と、残る自由部分の具体的な埋め方まで示す。
  • 行区間の交差と列の閉路は別の障害である。列順があっても行間の大小が逆転することがあり、行間が通っても列順が矛盾することがある。

計算量と制約

時間

行数を HH、列数を WW、行列全体の非零要素数を LL とする。入力全体の走査に O(HW)O(HW)、各行の非零要素のソートに合計 O(Llog⁡W)O(L\log W)、行区間のソート・検査に O(Hlog⁡H)O(H\log H) 時間かかる。

補助頂点数と辺数はともに O(L)O(L) なので、実列の WW 頂点を含むグラフの構築とトポロジカルソートは O(W+L)O(W+L) 時間である。全体は

O(HW+Llog⁡W+Hlog⁡H+W+L)O(HW+L\log W+H\log H+W+L)

時間となる。L=0L=0 でも入力の走査は必要である。

空間

行列を保持する実装では O(HW)O(HW)、行区間の配列に O(H)O(H)、一行分の非零要素をソートする作業領域に O(W)O(W) を使う。圧縮グラフの隣接リスト、入次数、取り出し候補のキューや順序列は合計 O(W+L)O(W+L) である。

従って全体は O(HW+H+W+L)=O(HW)O(HW+H+W+L)=O(HW) 空間となる。0の補完を確認するための別の完成行列は不要である。

制約との対応

公式制約は 2≤H,W2\leq H,W、HW≤106HW\leq10^6、0≤Ai,j≤HW0\leq A_{i,j}\leq HW。実行時間制限は3秒、メモリ制限は1024 MiBである。L≤HWL\leq HW であり、補助頂点による圧縮後は頂点・辺を入力サイズに比例する個数へ抑えられる。0を順序制約から除いてよい理由には、補完後の値が正で、等しい値を並べることも許されるという条件を使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: DAGのtopological processing

主題
  • DAGのtopological processing: 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DAGのtopological processing

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

      学習の位置

      体系上の位置: DAGのtopological processing

      • 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題