ABC 301 E — Pac-Takahashi

考察

お菓子は高々18個なので、S/G/各菓子間のgrid最短距離を圧縮すれば訪問順だけのTSP型問題になる。障害物grid上の移動経路は訪問する重要点順が決まれば点間最短距離へ置き換えてよい。

採用する候補: 重要点BFS+bitmask TSP DP

各重要点間距離をBFSし、dp[mask][last]で菓子集合を訪問する最短時間を求めてgoalまで含めT以下の最大個数を選べる。

棄却する候補: 時刻付きgrid BFSで取得集合も状態化

HWTまたはgrid×2^18状態が大きく、重要点圧縮の方が小さい。

S,G,菓子各点からBFSして距離行列を作る。dp[mask][i]をSからmask菓子を訪れiで終わる最短距離として遷移し、dp+dist(i,G)≤Tのpopcount最大を取る。

典型の発動条件

metric closure

発動条件: 大きいgraphで少数の必訪候補間移動だけが重要。

各重要点BFSで完全距離graphへ圧縮する。

bitmask TSP DP

発動条件: 高々18候補から訪問subsetと順序を最適化する。

mask,lastで最短路を計算する。

問題固有の要素

時間TをDP軸にせず最短距離を値に持つことでT=2×10^6を避ける。

別の問題へ持ち帰る視点: 候補数が小さい収集問題はmetric closure+subset DPへ落とす。

正当性

重要点間の動きはBFS最短pathへ置換して時間を増やさない。訪問集合と末尾だけで将来を決められ、最短時間だけ保持すれば全訪問順を覆う。最後のgoal距離まで加えT以内の最大popcountを取る。最短区間に他菓子を通る場合も実際の獲得数を減らさず最適上界を保つ。

実装上の注意

  • S→Gが到達不能またはT超なら-1。INF距離を足さず、菓子0個maskも評価する。

復習の核

  • 小gridの状態BFSと比較し、菓子なし、回収不能菓子、最短S-GがTちょうど、訪問順依存を確認する。

計算量と制約

時間

盤面HW、菓子C≤18。重要点BFS O((C+2)HW)、subset DP O(C²2^C)。

空間

盤面とBFS O(HW)、mask DP O(C2^C)、距離O(C²)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 1\leq H,W \leq 300; 1 \leq T \leq 2\times 10^6; H, W, and T are integers.; A_{i,j} is one of S, G, ., #, and o.; Exactly one pair (i,j) satisfies A_{i,j}= S.; Exactly one pair (i,j) satisfies A_{i,j}= G.; At most 18 pairs (i,j) satisfy A_{i,j}= o.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Pac-Takahashi の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 部分集合・bitmask状態DP

主題
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    主タグ: 部分集合・bitmask状態DP

    補助タグ: 最短路モデル

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

    学習の位置

    体系上の位置: 部分集合・bitmask状態DP

    • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

    先に読む単元:

    • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題