ABC 427 E — Wind Cleaning

考察

全てのごみは同じ向きに動くので、生き残ったごみ同士の位置関係は変わらない。現在位置を一つずつ記録する代わりに、「初期盤面のどこが生き残ったか」と「全体がどれだけずれたか」を分けて持つ。盤外へ出たごみを復活させないため、累積変位だけでなく、途中で削られた範囲も記録するのが鍵になる。

生存範囲を初期座標で持つ

座標は0始まりとし、行は下向き、列は右向きに増える。初期盤面を SS、高橋君の固定位置を (tx,ty)(t_x,t_y) とする。初期座標 (x,y)(x,y) のごみが生き残っていれば、累積変位 (dx,dy)(d_x,d_y) を用いて現在位置は

(x+dx, y+dy)(x+d_x,\ y+d_y)

と書ける。一回の風を受けた後も盤内にある条件は、次の変位を (dx′,dy′)(d_x',d_y') として

0≤x+dx′<H,0≤y+dy′<W0\leq x+d_x'<H,\qquad 0\leq y+d_y'<W

である。これを初期座標の条件に直すと、行・列それぞれの区間になる。過去の全操作についてこの条件の共通部分を取っても、残る範囲は半開矩形で表せる。

そこで状態を六変数 (lx,rx,ly,ry,dx,dy)(l_x,r_x,l_y,r_y,d_x,d_y) とし、

R=[lx,rx)×[ly,ry)R=[l_x,r_x)\times[l_y,r_y)

を生存矩形と呼ぶ。これは初期座標の範囲であり、現在の盤面上での矩形ではない。現在のごみは、RR 内で Sx,y=#S_{x,y}=\texttt{\#} である初期マスを (dx,dy)(d_x,d_y) だけ平行移動したものにちょうど一致する。矩形には初めからごみのないマスが含まれていてよい。

初期状態は (0,H,0,W,0,0)(0,H,0,W,0,0) である。盤面の各マスにごみがあるかを直接持つと候補は指数的に増えるが、この表現なら各変数の範囲を盤面の大きさで抑えられる。

四方向の風と矩形の更新

次の風でまず変位を更新する。上なら dx′=dx−1d_x'=d_x-1、下なら dx′=dx+1d_x'=d_x+1、左なら dy′=dy−1d_y'=d_y-1、右なら dy′=dy+1d_y'=d_y+1 とし、もう一方の変位は変えない。

盤内条件を初期座標について解けば、次の風の後に残れる範囲は [−dx′,H−dx′)×[−dy′,W−dy′)[-d_x',H-d_x')\times[-d_y',W-d_y') である。これを今までの生存矩形と交差させるので、更新式は次になる。

lx′=max⁡(lx,−dx′),rx′=min⁡(rx,H−dx′),ly′=max⁡(ly,−dy′),ry′=min⁡(ry,W−dy′).\begin{aligned} l_x'&=\max(l_x,-d_x'), & r_x'&=\min(r_x,H-d_x'),\\ l_y'&=\max(l_y,-d_y'), & r_y'&=\min(r_y,W-d_y'). \end{aligned}

各方向で実際に切り落とし得る端を抜き出すと、次の表になる。表にない三つの端点は変わらない。例えば上向きの風では、現在の上端から出るごみだけが消え、下端から新たに出るごみはない。

風変位の更新切り落とし得る端の更新
上dx′=dx−1d_x'=d_x-1lx′=max⁡(lx,1−dx)l_x'=\max(l_x,1-d_x)
下dx′=dx+1d_x'=d_x+1rx′=min⁡(rx,H−dx−1)r_x'=\min(r_x,H-d_x-1)
左dy′=dy−1d_y'=d_y-1ly′=max⁡(ly,1−dy)l_y'=\max(l_y,1-d_y)
右dy′=dy+1d_y'=d_y+1ry′=min⁡(ry,W−dy−1)r_y'=\min(r_y,W-d_y-1)

右辺の変位は更新前の値である。実装では、方向ごとに式を分けず、更新後の変位を使って四端点の共通式を適用してもよい。

この交差が必要な理由を、小盤面で追ってみよう。

#.#
..T

初めのごみは (0,0),(0,2)(0,0),(0,2) にある。左へ一回吹かせると dy=−1d_y=-1、生存矩形は [0,2)×[1,3)[0,2)\times[1,3) となり、初期座標 (0,0)(0,0) のごみが消える。残るごみの現在位置は (0,1)(0,1) である。続いて右へ吹かせると dy=0d_y=0 に戻るが、生存矩形の列範囲は [1,3)[1,3) のままで、残るごみは (0,2)(0,2) の一つだけになる。変位が元に戻っても、一度消えたごみは戻らない。矩形を毎回盤内条件だけから作り直すと、この消滅を忘れてしまう。

高橋君への衝突と空状態を判定してBFSする

高橋君は動かない。次の風で位置 (tx,ty)(t_x,t_y) へ届く可能性がある初期マスは、変位を引いた一マス

(a,b)=(tx−dx′, ty−dy′)(a,b)=(t_x-d_x',\ t_y-d_y')

だけである。これを高橋君の位置の逆像と呼ぶ。更新後の矩形を R′R' とすると、(a,b)∈R′(a,b)\in R' かつ Sa,b=#S_{a,b}=\texttt{\#} のとき、その風を禁止する。初期盤面にごみがあっても、既に生存矩形の外へ消えたごみなら衝突しない。先に矩形内かを確かめれば、盤外の添字で SS を参照することも避けられる。

禁止されなかった風では、ごみが全て消えたかを調べる。lx′≥rx′l_x'\geq r_x' または ly′≥ry′l_y'\geq r_y' なら空矩形なので終了する。矩形自体が非空でも、初期ごみを一つも含まなければ終了である。初期盤面の # を1、それ以外を0とする二次元累積和 PP を、P(i,j)P(i,j) が [0,i)×[0,j)[0,i)\times[0,j) の和になるよう前計算する。非空矩形内のごみ数は

P(rx′,ry′)−P(lx′,ry′)−P(rx′,ly′)+P(lx′,ly′)\begin{aligned} &P(r_x',r_y')-P(l_x',r_y')\\ &\quad-P(r_x',l_y')+P(l_x',l_y') \end{aligned}

で O(1)O(1) 時間で得られる。

以上を一回の遷移として、初期状態からBFSする。距離 kk の状態から風を試し、合法な空状態ができたら k+1k+1 を答える。それ以外は、未訪問の六変数の組だけを距離 k+1k+1 でキューへ入れる。空状態を発見せずにキューが空になれば、答えは −1-1 である。公式入力には初めから一つ以上のごみがあるため、初期距離0での終了はない。

典型の発動条件

状態空間 BFS

発動条件: 各操作のコストが1で、将来の合法操作と結果を決める情報を多項式個の状態へ圧縮できるとき。

矩形境界と平行移動量を頂点、四方向の合法な風を有向辺として最短距離を求める。同じ配置に表現が一つだけである必要はなく、状態数が十分少なく、各状態からの遷移が正しければよい。

変換前座標での状態圧縮

発動条件: 全要素が同じ変換を受け、境界から脱落するだけの過程を扱うとき。

共通変位は現在位置を、生存範囲は過去の脱落を表す。変位が往復しても脱落は取り消されないので、二つを分けて保持する。

二次元累積和

発動条件: 変化しない初期盤面に対し、さまざまな矩形内の対象数を繰り返し尋ねるとき。

動いているごみを直接数えず、生存矩形内の初期ごみ数を求める。矩形が残っていてもごみ数は0になり得るため、空状態の判定に使う。

問題固有の要素

一様な平行移動に加え、盤内にある条件が行・列それぞれの区間になるため、生存範囲を矩形で保てる。高橋君への衝突も、移動後の全ごみを走査せず、固定位置の逆像一マスだけを調べればよい。

別の問題へ持ち帰る視点: 全体が同じ変換を受けるときは、現在の全要素を動かす代わりに、消えずに残った元データの範囲と、固定された障害物の逆像を調べられないか考える。

正当性

初期状態では、生存矩形内の初期ごみを共通変位だけ平行移動したものが、現在のごみ配置に一致する。一回の風で各ごみの変位は同じだけ増え、盤内に残る条件と従来の生存矩形との交差が、更新後の生存矩形になる。したがって、この表現は各遷移後も成り立ち、消滅したごみが復活することはない。

高橋君の位置へ届く初期座標は更新後の変位を引いた一マスだけなので、逆像が生存矩形内の初期ごみかを調べる条件は、衝突する条件と同値である。空矩形または矩形内の初期ごみ数が0であることも、全てのごみが消えたことと同値である。

同じ六変数の組は同じ配置を表し、次の四方向の合法性と遷移先を決める。同じ配置を異なる組が表すことはあっても、どの合法な操作列も六変数の遷移として追跡でき、逆に探索中の各辺は合法な風に対応する。よって、この状態グラフ上の空状態への最短距離が求める最小操作数である。各辺の重みは1なので、BFSが最初に空状態を発見した距離を答えればよい。全ての到達可能な非空状態を調べても空状態へ進めなければ、実現する操作列は存在しない。

実装上の注意

  • 生存矩形は初期座標で持つ。風で変位を更新してから矩形を切り詰め、矩形そのものを風向きへ平行移動しない。
  • ごみを含まない端行・端列を走査して削る正規化は不要である。訪問済み判定は六変数の組をキーとし、同じ配置の別表現は残してよい。これで各方向の処理は定数回の演算で済む。正規化を追加するなら、その走査の費用を別途評価する必要がある。
  • 空矩形の判定を先に行い、端点の順序が逆転した範囲へ累積和の式を適用しない。空状態は答えとして直ちに終了させ、キューへ入れて変位を増やし続けない。
  • 衝突判定と空判定を済ませてから、非空の未訪問状態をキューへ追加する。符号付きの変位を配列の添字にする場合は、行に H−1H-1、列に W−1W-1 を加えて非負にする。最後の風では変位がこの範囲を越える場合もあるので、空状態を先に終端化し、訪問済み配列を参照しない。

復習の核

  • 同じ変換を受ける多数の要素は、共通変位と元データ上の生存範囲で表せないか考える。
  • 現在の変位と過去の消滅は別の情報である。風を戻す小例で、ごみが復活しないか確かめる。
  • 状態の表現を一意にすることより、未来を決める情報が揃っていることと、探索する状態数が有限で十分小さいことを確認する。

計算量と制約

時間

探索するのはごみが一つ以上ある状態だけである。生き残った初期座標 (x,y)(x,y) と現在座標 (x+dx,y+dy)(x+d_x,y+d_y) はどちらも盤内にあるので、

−(H−1)≤dx≤H−1,−(W−1)≤dy≤W−1.\begin{aligned} -(H-1)&\leq d_x\leq H-1,\\ -(W-1)&\leq d_y\leq W-1. \end{aligned}

である。また、非空状態の端点は 0≤lx<rx≤H0\leq l_x<r_x\leq H、0≤ly<ry≤W0\leq l_y<r_y\leq W を満たす。行に関する三変数はそれぞれ O(H)O(H) 通り、列に関する三変数はそれぞれ O(W)O(W) 通りなので、六変数の組は O(H3W3)O(H^3W^3) 個である。同じ配置の重複表現も、この評価に含まれる。

二次元累積和の前処理は O(HW)O(HW)。各状態からの四遷移では端点更新、逆像の検査、矩形和が全て O(1)O(1) なので、全体の時間計算量は O(HW+H3W3)=O(H3W3)O(HW+H^3W^3)=O(H^3W^3) である。六変数の範囲に対応する配列で距離を管理すれば、訪問済み判定も O(1)O(1) で行える。

空間

距離配列とBFSのキューに O(H3W3)O(H^3W^3)、初期盤面と二次元累積和に O(HW)O(HW) を使う。全体で O(H3W3)O(H^3W^3) である。空になった後の変位を探索しないことが、この有限な状態数評価の前提になる。

制約との対応

公式制約は 2≤H,W≤122\leq H,W\leq 12 で、T はちょうど一つ、# は一つ以上である。制限時間は2秒、メモリ制限は1024 MiBである。非空な行区間は H(H+1)/2H(H+1)/2 通り、行変位は 2H−12H-1 通りなので、列側も掛けた状態数の上界は、最大の H=W=12H=W=12 でも約322万個である。実際に到達できない組も含む上界だが、盤面の全配置を直接列挙する場合と異なり、この範囲でBFSできる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Wind Cleaning の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 状態グラフのモデリングと探索

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

    主タグ: 状態グラフのモデリングと探索

    補助タグ: DPの最小十分状態 累積和・差分配列

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

    学習の位置

    体系上の位置: 状態グラフのモデリングと探索

    • 暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題