ABC 317 E — Avoid Eye Contact

考察

視線に入るかを先に確定できれば、残る問題は各辺コスト1の grid 最短路なので BFS である。視線は壁または人で止まり、S/G や空きマスでは止まらない。人ごとに長い ray を独立に伸ばす代わりに、各行・各列を四方向から一度ずつ読む。最後に見たblockerの種類だけを持てば各マスを定数回で処理できる。左から右のscanでは最後のblockerが右向き人なら、その後の空きマスは監視下にある。壁または別の人に会った時点で状態を更新し、残り三方向も同様に処理する。監視マスは通れないが視線を遮らない。視線を止めるのは # と四種の人だけなので、mark済み空きマスでscanを止めてはいけない。

採用する候補: 行列の四方向scanで監視マスを印付け、そのマスと障害物・人を通行不可にして S から BFS する。

前処理と探索がともに O(HW) で、視線計算と最短路計算の責務を分離できる。

棄却する候補: BFS 中に各候補マスから四方向を逆走し、見張る人がいるか都度調べる。

開けた行列では一移動判定に O(H+W) かかり、全体が O(HW(H+W)) まで悪化する。

監視マスは通れないが視線を遮らない。

viewed を false で作り、各行を左右から、各列を上下から走査する。対応方向を向く人の後で blocker までの . を viewed=true にする。次に #・人・viewed を禁止として S から四近傍 BFS し、G の距離または −1 を出す。

典型の発動条件

ray制約の四方向scan

発動条件: grid 上の直線効果が blocker まで続き、方向種類が定数個のとき。

各行・各列を一方向にscanし、現在activeなrayの有無だけを持って全マスを一度ずつ印付ける。

制約前処理+BFS

発動条件: 移動不能条件が位置だけで決まり、移動ごとに再計算する必要がないとき。

危険マスを静的 obstacle に変換して単位重み最短路を解く。

問題固有の要素

監視されたことと視線を遮ることは別属性であり、前者をobstacleとしてBFSに使っても方向別scanのblockerにはしない。

別の問題へ持ち帰る視点: grid 前処理では「入れない」「効果を止める」を同じ boolean に潰さず、意味ごとに分ける。

正当性

各rayは壁か人でだけ止まるので走査方向に最後のblockerを覚えると全viewedセルが厳密に決まる。危険セルを通行不可にした残存graphは元の合法移動と一致し単位辺BFSで最短。S/Gも視線遮断物として扱わず公式セル条件を守る。

実装上の注意

  • S/Gは監視外保証だが方向別scanでは空きマス同様に視線を通す。人のマス自身はviewedにせずとも常にBFS禁止とする。

復習の核

  • 前処理の blocker 条件と BFS の通行条件を別に列挙する。四方向実装は方向配列で共通化し、端・連続する人をテストする。

計算量と制約

時間

H×W。四方向視線走査とBFS O(HW)。

空間

盤面、視線flag、dist O(HW)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq H, W \leq 2000; A_{i,j} is ., #, >, v, <, ^, S, or G.; Each of S and G occurs exactly once among A_{i, j}.; Neither the starting point nor the goal is in a person's line of sight.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Avoid Eye Contact の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 方向別grid scanによる長距離効果の前計算

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

    主タグ: 方向別grid scanによる長距離効果の前計算

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

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

    学習の位置

    体系上の位置: 方向別grid scanによる長距離効果の前計算

    • 各行・各列でactiveな向きだけを更新し、blockerと通行禁止条件を混同せず、定数方向へ伸びる全効果領域をgrid全体の線形時間で印付けられる。

    先に読む単元:

    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題