ABC 274 E — Booster

考察

townsとchestsを合わせても17 pointsで、visited subsetから必須townsの達成状況と取得booster数の両方を復元できる。visited chests数がkなら現在speedは2^kであり、次pointまでのtravel timeはEuclidean distance/2^kとなる。同じmask,lastに達した経路は現在speedと残りpointsが一致するため、所要時間の最小値だけを保持すればよい。全town bitsを含む任意mask,lastからoriginへ戻るtimeを加えれば、そのmaskに含まれないchestsを訪ねず終了する候補になる。

棄却する候補: 訪問するchest subsetを固定し、その各caseで別々にtown/chest TSPを解く。

可能ではあるがchest subset列挙とpath DPが重なり2^N3^Mの余分なfactorを持つ。

採用する候補: 全pointsを同じbitmaskへ入れ、dp[mask][last]をそのvisited集合でlastへいるminimum timeとして遷移する。

chestを訪問しない選択もmask列挙に自然に含まれ、booster countを追加stateなしで計算できる。

optional pickups that alter speedをsubset TSPへ統合し、visited-mask-derived resource levelでedge costsを評価する。

典型の発動条件

訪問集合bit DP

発動条件: 対象点が20個未満で、経路の将来がvisited subsetとcurrent pointだけで決まるとき。

未訪問point jを追加し、dp[mask∪{j}][j]へcurrent-to-j travel timeをrelaxする。

optional verticesの同一state化

発動条件: 必須訪問点と任意訪問点が同じ移動graph上にあり、任意点の効果をmaskから計算できるとき。

town/chestを同じpoint listに置き、終端条件だけをall-town-bits includedとする。

問題固有の要素

booster countはpopcount(mask & chestMask)なので、speedをDP dimensionとして重複保持しない。

別の問題へ持ち帰る視点: resourceが特定visited itemsの個数だけで単調に変わるならsubset自体から導出する。

正当性

訪問maskからbooster数が分かり速度を2^countで復元できる。nextまでの所要時間は今の速度で決まるのでmask,lastが十分。全街を含むmaskから原点へ戻るcostを評価し、booster任意採否も全maskが覆う。

実装上の注意

  • originをmask外のstart/endとしてdp singletonをdistance from originで初期化し、N+M=0相当の空case規約も明確にする。
  • distanceはhypotでdouble計算し、infinity初期値と2^kによる除算を一貫させる。

復習の核

  • 少数のoptional visitsは外側でsubset固定せず、必須pointsと同じvisited maskへ統合する。
  • 訪問で変化するspeed/resourceは、同じmaskなら一意かを確認してstate dimensionを削る。

計算量と制約

時間

街N、boosterM、V=N+M。subset TSP O(V²2^V)。

空間

mask×last O(V2^V)、距離表O(V²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 12; 0 \leq M \leq 5; -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9; (0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題