Bubble Cup8 Finals F. Bulbo

問題

概要

はじめ位置$x$にいて,$N$回のイベントがある.
イベント前にある整数座標上の点に移動できる.移動した距離だけコストがかかる
各イベントごとに区間$[l,r]$の整数座標の点が光る.
光っている点のうち,現在位置ともっとも近い点までの距離だけコストがかかる.

コストを最小化せよ.

制約

  • $1 \le N \le 5000$
  • $1 \le x \le 10^{9}$
  • $1 \le l \le r \le 10^{9}$

解法

値の取りうる範囲は広いが,実際に訪れる必要があるところは少ない.
座標圧縮する.

次に各イベントごとに,$dp[i]=$ある位置$i$にいるときの最小コストとしてDPを行う.
遷移はある位置$i$から$i+1$に移動する遷移と,$i$から$i-1$に移動する遷移と,$i$に留まるという遷移の繰り返しで表せる.
ここで往復するのは意味がないので左から右に向かう遷移と,右から左に向かう遷移を別々に試す.

その後,点灯する区間と位置までの最短距離を加算してやればよい.

計算量は$O(N^{2})$.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var p = sc.Integer();
var xs = new List<int>(); xs.Add(p);
var L = new int[n];
var R = new int[n];
for (int i = 0; i < n; i++)
{
var l = sc.Integer();
var r = sc.Integer();
xs.Add(l); xs.Add(r);
L[i] = l; R[i] = r;
}
xs = xs.Distinct().ToList();
xs.Sort();
var dp = Enumerate(xs.Count, x => 1L << 50);
dp[xs.BinarySearch(p)] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < xs.Count; j++)
dp[j] = Math.Min(dp[j], dp[j - 1] + xs[j] - xs[j - 1]);
for (int j = xs.Count - 2; j >= 0; j--)
dp[j] = Math.Min(dp[j], dp[j + 1] + xs[j + 1] - xs[j]);
var l = xs.BinarySearch(L[i]);
var r = xs.BinarySearch(R[i]);
for (int j = 0; j < xs.Count; j++)
{
if (j < l) dp[j] += xs[l] - xs[j];
if (r < j) dp[j] += xs[j] - xs[r];
}
}
IO.Printer.Out.WriteLine(dp.Min());
}
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}

まとめ

座圧してDPするだけだけど,ちょっと考えてしまった.