AtCoder Beginner Contest 334F問題 - 競技プログラミング日記

ABC334F

スタートとゴールの vertex を \(0\), それ以外の vertex を \(1, \cdots , N-1\) として， \(N\) 個の頂点で書き直したバージョンで説明する． \(d_{i,i+1}\) を \(i\) から \(i+1\) への距離とおく．

解法 0: Segtree

まず簡単なバージョンの問題を考える．

Eary: プレゼントの制限無し

プレゼントを無限に持てるという場合は， 0 に戻る必要がない．よって，\(i \rightarrow i+1\) の距離 \(d_{i,i+1}\) の和が答え．

Normal: プレゼントの制限有り

何回か vertex \(0\) へ戻らないといけないとする．戻らないといけない具体的な条件は，一旦無視する．この場合，\(i \rightarrow i+1\) への移動をする際に，補給するために \(0\) を経由する選択肢が生まれる．つまり，\(i \rightarrow i+1\) と \(i \rightarrow 0 \rightarrow i+1\) の二つの選択肢がある．よって Normal の問は，各 \(i\) に対してどちらの選択をするのが最善かを選ぶというものに言い換えられる．
ここで，\(0\) を経由する度にかかるコスト \(f_{i} := d{i,0} + d{0,i+1} - d_{i,i+1} \geq 0\) を定義する． Noraml の問は，\(f_{i}\) の和が最小になるように選ぶという問になる．

Hard(本問)

\(K\) 個までしかプレゼントを持てないとする．このとき，何度か vertex \(0\) へ戻らないといけない． \(f_{i}\) の和が最小になるように \(i\) を選ぶのは同じだが，以下の条件を追加する:

\(f_{i}\) と \(f_{j}\) を選ぶためには， \(abs(j-i) \leq K\) が必要十分．

選んだ \(i\) の集合を \(I\) とおく．
DP でこの問題を解く． \(i \in [0,N]\) に対して，

\(dp_{i} := \) 最後に選んだ \(f\) の番号が \(i\) のときの \(\sum_{j \in I} f_{j}\) の min

とおく．遷移と初期化は

\(dp_{i} = min_{1 \leq j \leq K} (dp_{i-j}) + f_{i}\)
\(dp_{0} = 0\)

となる．求める答えは \(ans = \sum_{i \in [0,N]} dp_{i,i+1} + dp_{N}\). 遷移は区間 min なので，segtree を用いて \(O(log N)\) で遷移出来る．

解法 1: Lazy segtree

解法 2: Slide min

実装

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

// segtree ------------------------------------------
double op(double a, double b){
  return min(a,b);
}

double e(){
  return 1e18;
}

int main() {
  ll n,k;
  cin >> n >> k;
  n++;

  vector<pll> p(n);
  rep(i,n){
    ll x,y; cin >> x >> y;
    p[i] = {x,y};
  }

  auto dis = [&](ll i, ll j) -> double {
    auto [x,y] = p[i];
    auto [z,w] = p[j];
    return sqrt(square(x-z) + square(y-w));
  };

  // rem: スタートとゴールが同じ vertex なので %n
  // %n をつけないと，存在しない座標を参照して nan.

  double base = 0;
  rep(i,n) base += dis(i,(i+1)%n);

  // rem: dp のグラフ:
  // vertex: n+1 個
  // edge: n 本
  // dp は edge の選び方.
  // dp[i] = edge i を最後に選んだ場合の min cost
  segtree<double,op,e> dp(n);
  dp.set(0,0);
  rep1(i,n-1){
    double f = dis(i,0) + dis(0,(i+1)%n) - dis(i,(i+1)%n);
    dp.set(i, f + dp.prod(max(i-k,0LL), i));

  }
  printf("%.10lf\n", base + dp.get(n-1));

  return 0;
}


// lazy segtree --------------------------------------------
double op (double a, double b){
  return min(a,b);
}

double e(){
  return 1e18; // rem: lazy segtree の mapping の度に足されるので，桁あふれに注意．
}

double mapping(double f, double x){
  return f + x;
}

double composition(double f, double g){
  return f + g;
}

double id(){
  return 0;
}

int main() {
  ll n,k;
  cin >> n >> k;
  n++;

  vector<pll> p(n);
  rep(i,n){
    ll x,y; cin >> x >> y;
    p[i] = {x,y};
  }

  auto dis = [&](ll i, ll j) -> double {
    auto [x,y] = p[i];
    auto [z,w] = p[j];
    return sqrt(square(x-z) + square(y-w));
  };

  lazy_segtree<double, op, e, double, mapping, composition, id> dp(k+1+n+1);
  // 範囲外は計算しないほうが安全．
  // 上手くやれば範囲外を計算しても，正しい答えは求まるけど．
  ll l = 1, r = k+1;
  dp.set(k, 0);
  rep(i,n-1){
    double d;
    
    d = dp.prod(l,r);
    d += dis(i,0) + dis(0,(i+1)%n);
    dp.set(r, d);
    dp.apply(l,r, dis(i,(i+1)%n));

    l++, r++;
  }
  printf("%.10lf ", dp.prod(l,r) + dis(n-1,0));

  return 0;
}