ABC 315 F — Shortcuts

考察

通過した checkpoint の列が決まれば距離は隣接する選択点間の Euclid 距離の和で、過去の具体的経路は最後に通った点と skip 総数だけで十分である。

skip penalty は 2^{C−1} と指数増加する一方、全点を通る距離は座標範囲と N から多項式上界を持つ。従って大きな C は最適解にならず、小さい定数まで切れる。

採用する候補: dp[i][c] を checkpoint i を最後に通り合計 c 個 skip した最小移動距離とし、小さい c 上限だけ遷移する。

次に通る j までの skip j−i−1 を加える Markov 状態になり、指数 penalty から c を数十程度に制限できる。

棄却する候補: 各中間 checkpoint を通る/skip の 2^{N−2} 通りを全探索する。

N=10^4 では列挙不能で、同じ最後の点と skip 数へ至る履歴を最小距離一つに統合できる。

全点経由の距離上界より 2^{C−1} が大きくなった C は、それだけで既知解を超えるため安全に捨てられる。

dp 遷移では i から j へ直接飛ぶ距離を加え、skip 数を j−i−1 増やす。penalty は最後に一度だけ加える。

座標制約から得た既知上界を超える最小 2^{C−1} を基に CMAX を取る。dp[1][0]=0 とし、各 i,c から j=i+1..min(N,i+CMAX−c+1) へ距離(i,j)を加えて chmin する。最後に dp[N][c]+(c=0?0:2^{c−1}) の最小を出す。

典型の発動条件

指数 penalty による状態打切り

発動条件: 最適化の一変数に指数増加コストがあり、容易な feasible 解の上界が得られるとき。

penalty 単独で上界を超える領域を証明付きで DP から除く。

最後の選択点 DP

発動条件: 順序付き点列から一部を選び、連続して選んだ点間のコストを足すとき。

最後に選んだ index と累積 skip 数を状態にし、次の選択点へ飛ぶ。

問題固有の要素

N=10^4 でも skip 数軸は N まで不要で、目的関数の指数項そのものが強い枝刈り証明になる。

別の問題へ持ち帰る視点: DP の次元上限は入力制約だけでなく、既知解上界と penalty 下界を比較して削れないか調べる。

正当性

dp[i,c]を点iへ到達し、途中でc点を省いた最小距離とする。直前に訪れた点jからiへ移ると距離を一度足し、省略数をi−j−1だけ足すので全経路と遷移列が一対一になる。全点経由の既知距離Uよりpenalty 2^{c−1}が大きいcは、非負距離と合わせて既知解より劣るため捨ててよい。残るcだけのDPで全最適候補を保持し、終点で総cに対するpenaltyを一回加えた最小を取れば目的関数そのものになる。

実装上の注意

  • C=0 の penalty は0で 2^{-1} ではない。CMAX は座標・Nからの上界に十分な余裕を持たせ、float の infinity と誤差を管理する。

復習の核

  • 「100個なら大きい」と感覚で切らず、必ず全点経由解の上界と penalty を比較する。遷移時の skip 増分 j−i−1 を小例で検算する。

計算量と制約

時間

O(NC²)、Cは既知全点経由上界より大きくなるpenaltyを初めて与えるskip数。

空間

O(NC)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 2 \le N \le 10^4; 0 \le X_i,Y_i \le 10^4; (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 列・subsequence DP

    補助タグ: 幾何の基本判定・配置・座標変換

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

    学習の位置

    体系上の位置: 列・subsequence DP

    • 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題