考察
通れるマスをすべて探索する代わりに、障害物が通路をふさぐ境界を作るか調べる。平面グラフの双対を使うと、この境界の有無を障害物の周囲だけの連結性に置き換えられる。
盤面全体にBFSを行うと、最大で 個のマスを扱う。一方、障害物数 は高々 である。入力が疎なので、通れる領域の広さではなく、通行を妨げる部分の個数に比例する解法を探したい。
通行不能を容量0のカットへ変える
各マス を頂点とし、上下左右の隣接マス間に無向辺を張ったグラフを考える。これを元グラフ(primal)と呼ぶ。障害物の頂点も残し、辺の容量を次のように定める。
- 両端とも障害物がなければ1。
- 少なくとも一端に障害物があれば0。
始点を 、終点を とする。まず の場合を考える。容量1の辺だけを使う経路が、実際に移動できる経路に一致する。従って到達不能であることは、 を分離する容量0のカットが存在することと同値である。実際、到達不能なら容量1の辺で から到達する頂点集合を取り、その集合の内外を結ぶ辺はすべて容量0になる。
元グラフはマスの中心を頂点として平面上に描ける。主単元のcut/path対応を使い、各面(face)を双対グラフの頂点へ、各辺をその両側の面を結ぶ双対辺へ写す。双対辺の重みは元辺の容量とする。ここで必要なのは重み0の経路の有無だけなので、最短路計算の代わりに重み0の双対辺をDSUで結べばよい。
内部の面と外周の二端子を座標で表す
添字は問題文と同じく1始まりとする。四頂点 に囲まれる内部の面を と定義する。範囲は である。これは四つのマスの中心間にできる面であり、マス自体とは区別する。
外側の面は、 から上辺・右辺を通って へ至る側を端子 、左辺・下辺を通る側を端子 として二つに分ける。主単元で外側の面に仮の 辺を加え、その双対辺を除いたものに当たる。外側を一頂点のままにすると、どちら側まで障害物の境界が伸びたかを区別できない。
内部の範囲から外れた も、次の規則で外周の端子を返す記法として使う。
例えば上端の横辺の上側は 、左端の縦辺の左側は となる。相反する規則に当たる角 は、盤面内の隣接辺に対する以下の問い合わせでは現れない。始終点は障害物でない保証も使い、盤面外への辺を処理しない。他の二角 の規則は、それぞれ で一致する。
元辺に対して結ぶ二つの面は、座標から直接求められる。
障害物の周囲だけを結ぶ
初めに を別々のDSU頂点として用意する。内部の面は座標からDSUのIDを得る辞書で管理し、初めて必要になったときにだけ頂点を作る。以後、同じ座標には同じIDを返す。
障害物 ごとに、次の操作を行う。表の条件は、対応する元辺が盤面内に存在する条件である。各 は上の規則で内部の面または外周の端子へ変換してから結ぶ。
この操作が列挙するのは、少なくとも一端が障害物である元辺、つまり容量0の辺すべてである。両端が障害物の辺は二度現れるが、DSUで同じ二頂点を再び結んでも結果は変わらない。障害物でない隣接マスを探索したり、容量1の辺を生成したりする必要はない。全障害物を処理した後、 が同じ根なら No、異なる根なら Yes を返す。
斜めの障害物でも、結ぶ外周で結果が変わる
の盤面で、次の二配置を比べる。これらは座標の意味を確認するための独自例である。
- 障害物が の場合、前者から と が結ばれ、後者から と が結ばれる。従って は連結し、
No。実際、始点の右と下がともにふさがっている。
- 障害物が の場合、二つの障害物の周囲は を介してつながる。しかし接する外周は上側と右側であり、どちらも である。 までは届かず、
Yes。実際、左端を下り、下端を右へ進める。
斜めに接する障害物のつながりも、共有する面を介した双対の連結性が捉える。ただし、つながりがあるだけで遮断と判断せず、異なる外周端子を結ぶかまで見る。
典型の発動条件
planar duality
発動条件: 無向平面グラフで、同じ面の境界上にある異なる二頂点の到達性を判定するとき。
容量0のカットを重み0の双対経路へ変換する。本問では外側の面を二つに分けることで、経路の両端を定められる。
疎なdual graphのDSU
発動条件: 全体は巨大でも、連結性の判定に使う辺が少数の入力から列挙できるとき。
本問では重み0の双対辺だけを使う。障害物に接する辺の両側の面だけを生成し、最短路計算をDSUの連結判定へ置き換える。
outer face splitting
発動条件: 始終点が外周にあり、その二点を分けるカットを双対経路へ写すとき。
外周の二つの側を別々の端子にする。同じ側へ戻る障害物の境界と、二つの側を結んで通路を遮断する境界を区別する。
問題固有の要素
始終点が左上・右下の角なので、上・右の外周と左・下の外周を明示的に分けられる。また、格子の面は四つのマスの中心で囲まれるため、一般の面の走査をせず座標だけで双対辺を得られる。この二点と障害物の疎性を合わせ、計算量を面積から障害物数へ落とす。
別の問題へ持ち帰る視点: 巨大領域の到達性では、通れる領域の圧縮に加え、通路を分離する境界を少数の入力から構築できるかも考える。
正当性
まず とする。容量1の元辺だけを使う経路が存在しなければ、その辺だけで始点から到達できる頂点集合の境界は容量0のカットである。逆に容量0のカットがあれば、始終点を結ぶどの元経路も容量0の辺を通る必要があり、実際には移動できない。
次に、容量0のカットと重み0の双対経路を対応させる。外側の面に仮の始終点間の辺を加えると、その両側の面が になる。 から への双対経路に仮の辺の双対辺を戻すと、始終点を異なる側へ分ける閉じた境界になる。その経路の元辺がすべて容量0なら、元グラフに容量0のカットが存在する。逆に容量0のカットから不要な辺を除いて包含極小にすると、その境界は仮の辺を横切る双対の閉路になる。そこから仮の辺の双対辺を除けば、重み0の 経路を得る。従って、到達不能と重み0の 経路の存在は同値である。
各容量0の元辺は少なくとも一端が障害物であり、手順はその障害物から必ず列挙する。座標の規則はその元辺の両側の面を正しく返すので、DSUは重み0の双対辺すべての連結性を保持する。問い合わせられない内部の面は重み0の辺を持たない孤立頂点であり、省略しても の連結性は変わらない。よって二端子が同じ根であるとき、かつそのときに限り No を返す。
では、各横辺の上側が 、下側が である。 では、各縦辺の右側が 、左側が である。いずれも一本道なので、障害物が一つでもあればそれに接する有効辺が二端子を結び、なければ二端子は別の根に残る。従って同じ判定で正しい。 では始終点が同一で、制約より障害物はなく、移動0回で Yes。この場合に「最大流が正なら到達可能」という異なる始終点を前提にした議論は適用しない。
実装上の注意
- または でも を同一視しない。例えば1行盤面の横辺は と を結ぶ。内部の面がなくても、二つの外周端子は必要である。
- 表の条件を確認し、盤面内に存在する隣接辺だけを処理する。盤面の外へ出る移動に対応する辺を追加しない。
- 座標辞書は外周の規則を先に適用し、内部の面だけを登録する。内部座標を整数キー にするなら、値は となり得るため、積を計算する前に64 bit整数型へ変換する。このキーは端子用の0、1と衝突しない。圧縮後のDSUのIDとは分けて扱う。
- なら結合は一度も起きず、常に
Yes。 もここに含まれる。
復習の核
- 通れるマスが多すぎるとき、通路を遮断する境界を入力の疎性から作れないか考える。
- 双対の頂点はマスではなく面。どの元辺を横切るかから、結ぶ二面の座標を導く。
- 外周の同じ側へつながるだけでは遮断にならない。始終点で分けた二つの側を結ぶことが条件である。
- 1行・1列では内部の面が消えても二端子は残る。同一の始終点は、移動0回の可否を直接確認する。
計算量と制約
時間
各障害物から調べる元辺は高々4本で、辞書への問い合わせとDSUの結合は合計 回。座標をハッシュ表で圧縮後のIDへ対応させ、配列上のDSUに経路圧縮とサイズによる併合を使うと、期待 時間である。 は逆アッカーマン関数。平衡二分探索木の辞書なら 時間となる。入力と最後の判定を含み、元盤面の 個のマスは走査しない。
空間
一つの障害物から現れる内部の面は周囲の高々4個で、外周端子は2個。辞書とDSUが持つ頂点数は高々 なので、入力の保存を含めて 空間である。
制約との対応
公式制約は 、。障害物の座標は盤面内の相異なる整数座標であり、 は障害物でない。実行時間制限は2秒、メモリ制限は1024 MiBである。面積は最大 になるが、処理する元辺は重複を含めても高々 本で済む。
出典