ABC 264 F — Monochromatic Path

考察

反転する行と列を一度に全部決めると、候補は指数的に増える。代わりに経路を一マスずつ伸ばし、初めて入る行・列の反転だけを決めよう。右・下にしか進まないため、離れた行・列には戻らず、その決定を忘れられる。現在の行と列の反転を覚えておけば、次のマスを同じ色にする選択は一意に決まる。

操作の並びを、反転するかどうかの二値へ変える

白黒の盤面で、行や列を反転して、左上から右下へ単色の経路を作る。移動は右と下だけで、経路の色は白でも黒でもよい。

同じ行を二回反転すると元に戻り、行反転と列反転の順番も結果を変えない。費用は正なので、同じ対象の二回分を取り除く方が得である。従って各行・列は反転するかしないかだけ考えればよい。

行 ii の反転を xi∈{0,1}x_i\in\{0,1\}、列 jj の反転を yj∈{0,1}y_j\in\{0,1\} とする。初期色を Ai,jA_{i,j} とすると、最終的な色は、

Bi,j=Ai,j⊕xi⊕yjB_{i,j}=A_{i,j}\oplus x_i\oplus y_j

となる。⊕\oplus はXORで、1を一回加えると反転し、二回なら元へ戻ることを表している。ただし全ビットの列挙は 2H+W2^{H+W} 通りで、縦横2000には使えない。

一つの経路を固定すると、自由な決定はどれだけ残るか

経路の連続する二マスの色を一致させれば、経路全体が単色になる。現在 (i,j)(i,j) にいて、右の (i,j+1)(i,j+1) へ進むとする。現在行の反転は両マスに共通なので、色の一致条件から消える。

Ai,j⊕xi⊕yj=Ai,j+1⊕xi⊕yj+1A_{i,j}\oplus x_i\oplus y_j =A_{i,j+1}\oplus x_i\oplus y_{j+1}
yj+1=yj⊕Ai,j⊕Ai,j+1y_{j+1}=y_j\oplus A_{i,j}\oplus A_{i,j+1}

つまり、現在の列反転が分かれば、新しい列反転は一意に決まる。同様に下へ進むときは、

xi+1=xi⊕Ai,j⊕Ai+1,jx_{i+1}=x_i\oplus A_{i,j}\oplus A_{i+1,j}

となる。どちらも新しい行・列を反転するかの二択を両方試す必要はない。経路と、最初の行・列の反転二ビットを固定すれば、以後の反転はすべて決まる。

独自例として、盤面の各行を 01、11、行費用を (4,2)(4,2)、列費用を (3,5)(3,5) とする。最初の行も列も反転せず、下、右と進んでみよう。

始点では色0で始める。次の下のマスは1なので、二行目の反転を決めて0へそろえる。右隣も二行目の反転で0になるため、二列目は反転しない。

位置新しい反転の決定費用
(1,1)(1,1)x1=0,y1=0x_1=0,y_1=00
(2,1)(2,1)x2=1x_2=12
(2,2)(2,2)y2=0y_2=00

二行目だけ反転すると盤面は 01、00 となり、白の経路が費用2で得られる。二行目を二マス通っても、反転費用は一度だけ払う。ここでは一候補の作り方を追っており、最小値を保証するには、他の開始ビットと経路も比較する必要がある。

なぜ過去の反転を全部覚えなくてよいのか

右へ進むと、次の列は初めて訪れる列である。その反転を決めても、今まで通った経路のマスには影響しない。また、左へ戻れないので、離れた列の反転を再び参照することもない。行についても同様である。

従って (i,j)(i,j) から先の判断に関わるのは、現在行のビット xix_i と現在列のビット yjy_j だけだ。これまでの違う経路や反転の履歴が同じ二ビットへ合流したなら、以後に選べる方向、新しいビット、追加費用がすべて一致する。そこまでの最小費用だけを残せばよい。

左上から右下への単調経路は、全行・全列を必ず通る。状態を減らせるのは「使わない行・列があるから」ではなく、使い終えて戻らない行・列の情報が、未来に不要になるからである。

各マス四状態のDPにする

dp[i][j][x][y]dp[i][j][x][y] を、現在行の反転が xx、現在列の反転が yy で、(i,j)(i,j) までの単色経路を作る最小費用とする。費用には、既に初めて入ったすべての行・列の反転費用を含める。到達不能は +∞+\infty とする。

始点では x,y∈{0,1}x,y\in\{0,1\} の四通りを試し、

dp[1][1][x][y]=xR1+yC1dp[1][1][x][y]=xR_1+yC_1

とする。RiR_i は行 ii、CjC_j は列 jj の反転費用である。

状態の値を dd とし、右へ進めるなら、

y′=y⊕Ai,j⊕Ai,j+1y'=y\oplus A_{i,j}\oplus A_{i,j+1}
dp[i][j+1][x][y′]←min⁡(dp[i][j+1][x][y′], d+y′Cj+1)dp[i][j+1][x][y']\leftarrow \min\bigl(dp[i][j+1][x][y'],\ d+y'C_{j+1}\bigr)

と更新する。新しく入る列が反転する場合だけ、その列費用を払う。現在行の費用は既に払っている。

下へ進めるなら対称的に、

x′=x⊕Ai,j⊕Ai+1,jx'=x\oplus A_{i,j}\oplus A_{i+1,j}
dp[i+1][j][x′][y]←min⁡(dp[i+1][j][x′][y], d+x′Ri+1)dp[i+1][j][x'][y]\leftarrow \min\bigl(dp[i+1][j][x'][y],\ d+x'R_{i+1}\bigr)

と更新する。行を上から下、各行を左から右へ走査すれば、更新元は必ず処理済みになる。答えは終点の四状態の最小値である。

経路の目標色を別に持つ必要はない。現在の色は Ai,j⊕x⊕yA_{i,j}\oplus x\oplus y から復元でき、遷移がそれを保つからだ。先ほどの2×2例で全開始ビット・両経路を比較すると、最小費用も2になる。

典型の発動条件

処理順を選び、未来と接する部分だけを状態へ残す

過去の決定が多くても、そのすべてが未来へ影響するとは限らない。経路を伸ばす、区間を広げる、グラフを順に処理するときは、「今後まだ参照される境界はどこか」を探す。

本問では単調経路により、現在行と現在列だけが過去と未来の両方へ関わる。そこにある二ビットを残せば、他の決定は費用へ集約して忘れられる。前後左右へ自由に動ける設定なら、離れた行や列へ戻る可能性があり、この四状態をそのまま使えない。必要な記憶量は、問題の対象だけでなく処理順や移動制約にも依存する。

全体への操作を、初めて関わる時点で計上する

行反転は行全体へ作用するが、経路を伸ばす過程では、その行へ初めて入る一回だけ費用を払えばよい。「反転する各行・列」と「初訪問時の費用」の対応を作ることで、全体の操作費を局所遷移へ分けられる。

この対応がなければ、同じ行を通るたびに払って二重計上したり、後から払うつもりで数え落としたりする。DPの値を定義するときは、何が決定済みで、どこまで支払い済みかも言葉にする。

最終状態の条件を、隣接する二対象の条件へ分解する

一本の経路が単色であることは、その上の連続する二マスがすべて同色であることと同値である。本問では共通の反転ビットを消去でき、次の新ビットが一意に決まった。

別の表現として、目標色を白・黒に固定して二回解くこともできる。目標色を tt とすれば、各マスで Ai,j⊕xi⊕yj=tA_{i,j}\oplus x_i\oplus y_j=t を要求すればよい。目標色を明示するか、隣接一致で暗に保つかは状態の表現の違いであり、どちらも正当化できる。本稿では一つのDPで両方の色を扱える隣接一致を用いた。

問題固有の要素

行と列を反転する操作だけを見ると、全ビットの依存が複雑に見える。しかし右・下への一移動では、必ず未知の行か列が一つだけ現れる。その未知数一つを隣接色の等式で決める、という組合せが核心である。反転という操作と、単調経路という条件を別々に読むだけでなく、両者が出会う「新しい行・列へ入る瞬間」を調べると状態設計へ進める。

正当性

反転結果は各行・列の反転回数の偶奇だけで決まり、正の費用から二回分の反転を取り除ける。よって最適解は各対象を高々一回反転するものから選べる。

合法な経路と反転集合を固定する。始点の二ビットは初期状態のどれかに対応する。経路上の一移動では、単調性により新しい行か列を初めて訪れる。そのビットは、前のマスと色が等しい条件からDPの式どおりに決まる。従ってこの解の全移動をDPが表し、各反転費用は初訪問時に一度だけ計上される。

逆にDPの遷移列から、経路と、初訪問時に決めた全行・全列の反転を復元できる。過去の決定を変更せず、連続するマスの色が必ず一致するため、復元した経路は単色である。各行・列は経路上で初めて現れる時点が一つしかなく、計上費用も実際の反転費用に等しい。

同じ状態の候補は、以後の選択と追加費用が一致するので、最小値だけを残してよい。DPはすべての合法解を扱い、得られる候補も合法だから、終点の最小値が最適費用になる。

実装上の注意

  • 右端では右遷移、下端では下遷移を作らない。各マス四状態をすべて初期化し、到達不能は更新元にしない。
  • 始点で最初の行費用と列費用を払う。その後は新しい行・列の分だけ加える。
  • 反転後の色は式から求め、入力盤面を書き換えない。複数状態が同じ入力を別の反転候補として使うためである。
  • 費用は最大で全行・全列の合計程度になり、32 bitを超える。DPと加算は符号付き64 bit整数にし、+∞+\infty は加算であふれない余裕を持たせる。
  • DP領域は現在行と次行へ圧縮できるが、同じ行の右遷移と次行への遷移の両方を保つ。全盤面を入力保存するなら、全空間まで O(W)O(W) になるわけではない。

復習の核

  • 全操作を決める前に、経路を一歩伸ばしたとき初めて決まる変数を調べる。
  • 忘れてよい理由は、移動方向と「もう参照しない」ことから説明する。
  • 状態の意味には、保持する反転ビットと支払い済みの費用を両方含める。
  • 全体の条件を隣接条件へ直すと、共通変数を消せる場合がある。

計算量と制約

時間

入力の読込に O(HW+H+W)O(HW+H+W)、各マス四状態から高々二方向の更新に O(HW)O(HW)。全体で O(HW)O(HW) 時間である。

空間

全状態を保存する実装では、DPと入力盤面に O(HW)O(HW)、費用配列に O(H+W)O(H+W)、合計 O(HW+H+W)O(HW+H+W) 空間。DPだけを二行へ圧縮すればその領域は O(W)O(W) だが、盤面を全保存する実装の全空間は引き続き O(HW+H+W)O(HW+H+W) である。

制約との対応

2≤H,W≤20002\leq H,W\leq2000、各費用は1以上 10910^9 以下。マス数は最大400万で、一マス四状態の線形時間DPを使える。全反転費用の合計は最大 4×10124\times10^{12} なので、符号付き64 bit整数が必要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Monochromatic Path の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DPの最小十分状態

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

      学習の位置

      体系上の位置: 最小十分状態からDPを設計する

      • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

      この解説で扱わないこと:

      • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題