ABC 413 G — Big Banned Grid

考察

通れるマスをすべて探索する代わりに、障害物が通路をふさぐ境界を作るか調べる。平面グラフの双対を使うと、この境界の有無を障害物の周囲だけの連結性に置き換えられる。

盤面全体にBFSを行うと、最大で HW=4×1010HW=4\times10^{10} 個のマスを扱う。一方、障害物数 KK は高々 2×1052\times10^5 である。入力が疎なので、通れる領域の広さではなく、通行を妨げる部分の個数に比例する解法を探したい。

通行不能を容量0のカットへ変える

各マス (i,j)(i,j) を頂点とし、上下左右の隣接マス間に無向辺を張ったグラフを考える。これを元グラフ(primal)と呼ぶ。障害物の頂点も残し、辺の容量を次のように定める。

  • 両端とも障害物がなければ1。
  • 少なくとも一端に障害物があれば0。

始点を s=(1,1)s=(1,1)、終点を t=(H,W)t=(H,W) とする。まず s≠ts\ne t の場合を考える。容量1の辺だけを使う経路が、実際に移動できる経路に一致する。従って到達不能であることは、s,ts,t を分離する容量0のカットが存在することと同値である。実際、到達不能なら容量1の辺で ss から到達する頂点集合を取り、その集合の内外を結ぶ辺はすべて容量0になる。

元グラフはマスの中心を頂点として平面上に描ける。主単元のcut/path対応を使い、各面(face)を双対グラフの頂点へ、各辺をその両側の面を結ぶ双対辺へ写す。双対辺の重みは元辺の容量とする。ここで必要なのは重み0の経路の有無だけなので、最短路計算の代わりに重み0の双対辺をDSUで結べばよい。

内部の面と外周の二端子を座標で表す

添字は問題文と同じく1始まりとする。四頂点 (i,j),(i+1,j),(i,j+1),(i+1,j+1)(i,j),(i+1,j),(i,j+1),(i+1,j+1) に囲まれる内部の面を F(i,j)F(i,j) と定義する。範囲は 1≤i<H, 1≤j<W1\le i<H,\ 1\le j<W である。これは四つのマスの中心間にできる面であり、マス自体とは区別する。

外側の面は、ss から上辺・右辺を通って tt へ至る側を端子 UU、左辺・下辺を通る側を端子 DD として二つに分ける。主単元で外側の面に仮の s-ts\text{-}t 辺を加え、その双対辺を除いたものに当たる。外側を一頂点のままにすると、どちら側まで障害物の境界が伸びたかを区別できない。

内部の範囲から外れた FF も、次の規則で外周の端子を返す記法として使う。

問い合わせる座標対応する双対頂点
1≤i<H, 1≤j<W1\le i<H,\ 1\le j<W内部の面 F(i,j)F(i,j)
i=0i=0 または j=Wj=W上側・右側の端子 UU
j=0j=0 または i=Hi=H左側・下側の端子 DD

例えば上端の横辺の上側は F(0,j)=UF(0,j)=U、左端の縦辺の左側は F(i,0)=DF(i,0)=D となる。相反する規則に当たる角 (0,0),(H,W)(0,0),(H,W) は、盤面内の隣接辺に対する以下の問い合わせでは現れない。始終点は障害物でない保証も使い、盤面外への辺を処理しない。他の二角 (0,W),(H,0)(0,W),(H,0) の規則は、それぞれ U,DU,D で一致する。

元辺に対して結ぶ二つの面は、座標から直接求められる。

元グラフの辺結ぶ双対頂点
横辺 (i,j)–(i,j+1)(i,j)\text{–}(i,j+1)、1≤j<W1\le j<W上の F(i−1,j)F(i-1,j) と下の F(i,j)F(i,j)
縦辺 (i,j)–(i+1,j)(i,j)\text{–}(i+1,j)、1≤i<H1\le i<H左の F(i,j−1)F(i,j-1) と右の F(i,j)F(i,j)

障害物の周囲だけを結ぶ

初めに U,DU,D を別々のDSU頂点として用意する。内部の面は座標からDSUのIDを得る辞書で管理し、初めて必要になったときにだけ頂点を作る。以後、同じ座標には同じIDを返す。

障害物 (r,c)(r,c) ごとに、次の操作を行う。表の条件は、対応する元辺が盤面内に存在する条件である。各 FF は上の規則で内部の面または外周の端子へ変換してから結ぶ。

向き条件結ぶ二頂点
上r>1r>1F(r−1,c−1), F(r−1,c)F(r-1,c-1),\ F(r-1,c)
下r<Hr<HF(r,c−1), F(r,c)F(r,c-1),\ F(r,c)
左c>1c>1F(r−1,c−1), F(r,c−1)F(r-1,c-1),\ F(r,c-1)
右c<Wc<WF(r−1,c), F(r,c)F(r-1,c),\ F(r,c)

この操作が列挙するのは、少なくとも一端が障害物である元辺、つまり容量0の辺すべてである。両端が障害物の辺は二度現れるが、DSUで同じ二頂点を再び結んでも結果は変わらない。障害物でない隣接マスを探索したり、容量1の辺を生成したりする必要はない。全障害物を処理した後、U,DU,D が同じ根なら No、異なる根なら Yes を返す。

斜めの障害物でも、結ぶ外周で結果が変わる

3×33\times3 の盤面で、次の二配置を比べる。これらは座標の意味を確認するための独自例である。

  • 障害物が (1,2),(2,1)(1,2),(2,1) の場合、前者から UU と F(1,1)F(1,1) が結ばれ、後者から F(1,1)F(1,1) と DD が結ばれる。従って U,DU,D は連結し、No。実際、始点の右と下がともにふさがっている。
  • 障害物が (1,2),(2,3)(1,2),(2,3) の場合、二つの障害物の周囲は F(1,2)F(1,2) を介してつながる。しかし接する外周は上側と右側であり、どちらも UU である。DD までは届かず、Yes。実際、左端を下り、下端を右へ進める。

斜めに接する障害物のつながりも、共有する面を介した双対の連結性が捉える。ただし、つながりがあるだけで遮断と判断せず、異なる外周端子を結ぶかまで見る。

典型の発動条件

planar duality

発動条件: 無向平面グラフで、同じ面の境界上にある異なる二頂点の到達性を判定するとき。

容量0のカットを重み0の双対経路へ変換する。本問では外側の面を二つに分けることで、経路の両端を定められる。

疎なdual graphのDSU

発動条件: 全体は巨大でも、連結性の判定に使う辺が少数の入力から列挙できるとき。

本問では重み0の双対辺だけを使う。障害物に接する辺の両側の面だけを生成し、最短路計算をDSUの連結判定へ置き換える。

outer face splitting

発動条件: 始終点が外周にあり、その二点を分けるカットを双対経路へ写すとき。

外周の二つの側を別々の端子にする。同じ側へ戻る障害物の境界と、二つの側を結んで通路を遮断する境界を区別する。

問題固有の要素

始終点が左上・右下の角なので、上・右の外周と左・下の外周を明示的に分けられる。また、格子の面は四つのマスの中心で囲まれるため、一般の面の走査をせず座標だけで双対辺を得られる。この二点と障害物の疎性を合わせ、計算量を面積から障害物数へ落とす。

別の問題へ持ち帰る視点: 巨大領域の到達性では、通れる領域の圧縮に加え、通路を分離する境界を少数の入力から構築できるかも考える。

正当性

まず H>1, W>1H>1,\ W>1 とする。容量1の元辺だけを使う経路が存在しなければ、その辺だけで始点から到達できる頂点集合の境界は容量0のカットである。逆に容量0のカットがあれば、始終点を結ぶどの元経路も容量0の辺を通る必要があり、実際には移動できない。

次に、容量0のカットと重み0の双対経路を対応させる。外側の面に仮の始終点間の辺を加えると、その両側の面が U,DU,D になる。UU から DD への双対経路に仮の辺の双対辺を戻すと、始終点を異なる側へ分ける閉じた境界になる。その経路の元辺がすべて容量0なら、元グラフに容量0のカットが存在する。逆に容量0のカットから不要な辺を除いて包含極小にすると、その境界は仮の辺を横切る双対の閉路になる。そこから仮の辺の双対辺を除けば、重み0の U-DU\text{-}D 経路を得る。従って、到達不能と重み0の U-DU\text{-}D 経路の存在は同値である。

各容量0の元辺は少なくとも一端が障害物であり、手順はその障害物から必ず列挙する。座標の規則はその元辺の両側の面を正しく返すので、DSUは重み0の双対辺すべての連結性を保持する。問い合わせられない内部の面は重み0の辺を持たない孤立頂点であり、省略しても U,DU,D の連結性は変わらない。よって二端子が同じ根であるとき、かつそのときに限り No を返す。

H=1<WH=1<W では、各横辺の上側が UU、下側が DD である。W=1<HW=1<H では、各縦辺の右側が UU、左側が DD である。いずれも一本道なので、障害物が一つでもあればそれに接する有効辺が二端子を結び、なければ二端子は別の根に残る。従って同じ判定で正しい。H=W=1H=W=1 では始終点が同一で、制約より障害物はなく、移動0回で Yes。この場合に「最大流が正なら到達可能」という異なる始終点を前提にした議論は適用しない。

実装上の注意

  • H=1H=1 または W=1W=1 でも U,DU,D を同一視しない。例えば1行盤面の横辺は F(0,j)=UF(0,j)=U と F(1,j)=DF(1,j)=D を結ぶ。内部の面がなくても、二つの外周端子は必要である。
  • 表の条件を確認し、盤面内に存在する隣接辺だけを処理する。盤面の外へ出る移動に対応する辺を追加しない。
  • 座標辞書は外周の規則を先に適用し、内部の面だけを登録する。内部座標を整数キー iW+jiW+j にするなら、値は HW−1<4×1010HW-1<4\times10^{10} となり得るため、積を計算する前に64 bit整数型へ変換する。このキーは端子用の0、1と衝突しない。圧縮後のDSUのIDとは分けて扱う。
  • K=0K=0 なら結合は一度も起きず、常に Yes。H=W=1H=W=1 もここに含まれる。

復習の核

  • 通れるマスが多すぎるとき、通路を遮断する境界を入力の疎性から作れないか考える。
  • 双対の頂点はマスではなく面。どの元辺を横切るかから、結ぶ二面の座標を導く。
  • 外周の同じ側へつながるだけでは遮断にならない。始終点で分けた二つの側を結ぶことが条件である。
  • 1行・1列では内部の面が消えても二端子は残る。同一の始終点は、移動0回の可否を直接確認する。

計算量と制約

時間

各障害物から調べる元辺は高々4本で、辞書への問い合わせとDSUの結合は合計 O(K)O(K) 回。座標をハッシュ表で圧縮後のIDへ対応させ、配列上のDSUに経路圧縮とサイズによる併合を使うと、期待 O(1+Kα(K+2))O(1+K\alpha(K+2)) 時間である。α\alpha は逆アッカーマン関数。平衡二分探索木の辞書なら O(1+Klog⁡(K+2))O(1+K\log(K+2)) 時間となる。入力と最後の判定を含み、元盤面の HWHW 個のマスは走査しない。

空間

一つの障害物から現れる内部の面は周囲の高々4個で、外周端子は2個。辞書とDSUが持つ頂点数は高々 4K+24K+2 なので、入力の保存を含めて O(K+1)O(K+1) 空間である。

制約との対応

公式制約は 1≤H,W≤2×1051\le H,W\le2\times10^5、0≤K≤2×1050\le K\le2\times10^5。障害物の座標は盤面内の相異なる整数座標であり、(1,1),(H,W)(1,1),(H,W) は障害物でない。実行時間制限は2秒、メモリ制限は1024 MiBである。面積は最大 4×10104\times10^{10} になるが、処理する元辺は重複を含めても高々 4K4K 本で済む。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Big Banned Grid の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 平面graph双対・cut/path対応

主題
  • 平面graph双対・cut/path対応: 埋め込みのfaceをdual頂点へ写し、primal cutとdual path/cycleの対応から最小cut問題を最短路へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 平面graph双対・cut/path対応

    補助タグ: DSUによる連結成分管理・縮約

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

    学習の位置

    体系上の位置: 平面graph双対・cut/path対応

    • 埋め込みのfaceをdual頂点へ写し、primal cutとdual path/cycleの対応から最小cut問題を最短路へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 最大流・最小カット — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、最大流・最小カットの発動条件・正当化・境界を重複なく学ぶ。
    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題