考察
反転する行と列を一度に全部決めると、候補は指数的に増える。代わりに経路を一マスずつ伸ばし、初めて入る行・列の反転だけを決めよう。右・下にしか進まないため、離れた行・列には戻らず、その決定を忘れられる。現在の行と列の反転を覚えておけば、次のマスを同じ色にする選択は一意に決まる。
操作の並びを、反転するかどうかの二値へ変える
白黒の盤面で、行や列を反転して、左上から右下へ単色の経路を作る。移動は右と下だけで、経路の色は白でも黒でもよい。
同じ行を二回反転すると元に戻り、行反転と列反転の順番も結果を変えない。費用は正なので、同じ対象の二回分を取り除く方が得である。従って各行・列は反転するかしないかだけ考えればよい。
行 の反転を 、列 の反転を とする。初期色を とすると、最終的な色は、
となる。 はXORで、1を一回加えると反転し、二回なら元へ戻ることを表している。ただし全ビットの列挙は 通りで、縦横2000には使えない。
一つの経路を固定すると、自由な決定はどれだけ残るか
経路の連続する二マスの色を一致させれば、経路全体が単色になる。現在 にいて、右の へ進むとする。現在行の反転は両マスに共通なので、色の一致条件から消える。
つまり、現在の列反転が分かれば、新しい列反転は一意に決まる。同様に下へ進むときは、
となる。どちらも新しい行・列を反転するかの二択を両方試す必要はない。経路と、最初の行・列の反転二ビットを固定すれば、以後の反転はすべて決まる。
独自例として、盤面の各行を 01、11、行費用を 、列費用を とする。最初の行も列も反転せず、下、右と進んでみよう。
始点では色0で始める。次の下のマスは1なので、二行目の反転を決めて0へそろえる。右隣も二行目の反転で0になるため、二列目は反転しない。
二行目だけ反転すると盤面は 01、00 となり、白の経路が費用2で得られる。二行目を二マス通っても、反転費用は一度だけ払う。ここでは一候補の作り方を追っており、最小値を保証するには、他の開始ビットと経路も比較する必要がある。
なぜ過去の反転を全部覚えなくてよいのか
右へ進むと、次の列は初めて訪れる列である。その反転を決めても、今まで通った経路のマスには影響しない。また、左へ戻れないので、離れた列の反転を再び参照することもない。行についても同様である。
従って から先の判断に関わるのは、現在行のビット と現在列のビット だけだ。これまでの違う経路や反転の履歴が同じ二ビットへ合流したなら、以後に選べる方向、新しいビット、追加費用がすべて一致する。そこまでの最小費用だけを残せばよい。
左上から右下への単調経路は、全行・全列を必ず通る。状態を減らせるのは「使わない行・列があるから」ではなく、使い終えて戻らない行・列の情報が、未来に不要になるからである。
各マス四状態のDPにする
を、現在行の反転が 、現在列の反転が で、 までの単色経路を作る最小費用とする。費用には、既に初めて入ったすべての行・列の反転費用を含める。到達不能は とする。
始点では の四通りを試し、
とする。 は行 、 は列 の反転費用である。
状態の値を とし、右へ進めるなら、
と更新する。新しく入る列が反転する場合だけ、その列費用を払う。現在行の費用は既に払っている。
下へ進めるなら対称的に、
と更新する。行を上から下、各行を左から右へ走査すれば、更新元は必ず処理済みになる。答えは終点の四状態の最小値である。
経路の目標色を別に持つ必要はない。現在の色は から復元でき、遷移がそれを保つからだ。先ほどの2×2例で全開始ビット・両経路を比較すると、最小費用も2になる。
典型の発動条件
処理順を選び、未来と接する部分だけを状態へ残す
過去の決定が多くても、そのすべてが未来へ影響するとは限らない。経路を伸ばす、区間を広げる、グラフを順に処理するときは、「今後まだ参照される境界はどこか」を探す。
本問では単調経路により、現在行と現在列だけが過去と未来の両方へ関わる。そこにある二ビットを残せば、他の決定は費用へ集約して忘れられる。前後左右へ自由に動ける設定なら、離れた行や列へ戻る可能性があり、この四状態をそのまま使えない。必要な記憶量は、問題の対象だけでなく処理順や移動制約にも依存する。
全体への操作を、初めて関わる時点で計上する
行反転は行全体へ作用するが、経路を伸ばす過程では、その行へ初めて入る一回だけ費用を払えばよい。「反転する各行・列」と「初訪問時の費用」の対応を作ることで、全体の操作費を局所遷移へ分けられる。
この対応がなければ、同じ行を通るたびに払って二重計上したり、後から払うつもりで数え落としたりする。DPの値を定義するときは、何が決定済みで、どこまで支払い済みかも言葉にする。
最終状態の条件を、隣接する二対象の条件へ分解する
一本の経路が単色であることは、その上の連続する二マスがすべて同色であることと同値である。本問では共通の反転ビットを消去でき、次の新ビットが一意に決まった。
別の表現として、目標色を白・黒に固定して二回解くこともできる。目標色を とすれば、各マスで を要求すればよい。目標色を明示するか、隣接一致で暗に保つかは状態の表現の違いであり、どちらも正当化できる。本稿では一つのDPで両方の色を扱える隣接一致を用いた。
問題固有の要素
行と列を反転する操作だけを見ると、全ビットの依存が複雑に見える。しかし右・下への一移動では、必ず未知の行か列が一つだけ現れる。その未知数一つを隣接色の等式で決める、という組合せが核心である。反転という操作と、単調経路という条件を別々に読むだけでなく、両者が出会う「新しい行・列へ入る瞬間」を調べると状態設計へ進める。
正当性
反転結果は各行・列の反転回数の偶奇だけで決まり、正の費用から二回分の反転を取り除ける。よって最適解は各対象を高々一回反転するものから選べる。
合法な経路と反転集合を固定する。始点の二ビットは初期状態のどれかに対応する。経路上の一移動では、単調性により新しい行か列を初めて訪れる。そのビットは、前のマスと色が等しい条件からDPの式どおりに決まる。従ってこの解の全移動をDPが表し、各反転費用は初訪問時に一度だけ計上される。
逆にDPの遷移列から、経路と、初訪問時に決めた全行・全列の反転を復元できる。過去の決定を変更せず、連続するマスの色が必ず一致するため、復元した経路は単色である。各行・列は経路上で初めて現れる時点が一つしかなく、計上費用も実際の反転費用に等しい。
同じ状態の候補は、以後の選択と追加費用が一致するので、最小値だけを残してよい。DPはすべての合法解を扱い、得られる候補も合法だから、終点の最小値が最適費用になる。
実装上の注意
- 右端では右遷移、下端では下遷移を作らない。各マス四状態をすべて初期化し、到達不能は更新元にしない。
- 始点で最初の行費用と列費用を払う。その後は新しい行・列の分だけ加える。
- 反転後の色は式から求め、入力盤面を書き換えない。複数状態が同じ入力を別の反転候補として使うためである。
- 費用は最大で全行・全列の合計程度になり、32 bitを超える。DPと加算は符号付き64 bit整数にし、 は加算であふれない余裕を持たせる。
- DP領域は現在行と次行へ圧縮できるが、同じ行の右遷移と次行への遷移の両方を保つ。全盤面を入力保存するなら、全空間まで になるわけではない。
復習の核
- 全操作を決める前に、経路を一歩伸ばしたとき初めて決まる変数を調べる。
- 忘れてよい理由は、移動方向と「もう参照しない」ことから説明する。
- 状態の意味には、保持する反転ビットと支払い済みの費用を両方含める。
- 全体の条件を隣接条件へ直すと、共通変数を消せる場合がある。
計算量と制約
時間
入力の読込に 、各マス四状態から高々二方向の更新に 。全体で 時間である。
空間
全状態を保存する実装では、DPと入力盤面に 、費用配列に 、合計 空間。DPだけを二行へ圧縮すればその領域は だが、盤面を全保存する実装の全空間は引き続き である。
制約との対応
、各費用は1以上 以下。マス数は最大400万で、一マス四状態の線形時間DPを使える。全反転費用の合計は最大 なので、符号付き64 bit整数が必要である。
出典