# ABC334 F - Christmas Present 2

## 問題リンク
- https://atcoder.jp/contests/abc334/tasks/abc334_f

## 解法
基本的に家のことは点と, サンタさんの家のことは始点と呼ぶことにします. 簡単のために点$0$は始点であるとします.
### $O(NK^2)$
以下のDPを考えましょう
$$dp[i]= 点iに至るまでに必要な時間の最小値$$

このとき, 遷移は貰うDPで以下のように記述できます

1. $$dp[i] \leftarrow\min\left(dp[i],\sum_{k=0}^{i-1}{d(k,k+1)}\right)$$
2. $$dp[i] \leftarrow \min\left(dp[i],dp[j]+d(0,j)+d(0,j+1)+\sum_{k=j+1}^{i-1}{d(k,k+1})\right)$$

1.の方はOKでしょう.
2.の方は, $j$で一旦始点に戻ってから$j+1,\dots,i$を一気に配る場合のコストを表します. $i-j\leq K$ でなければいけないことに気を付けてください.

これを真面目に計算すれば $O(NK^2)$ になります.

### 高速化

まず, 遷移に現れる$\sum$ はいずれも区間和です. したがって, 累積和

$$ D_{i}=\sum_{k<i}{d(k,k+1)}$$

を用意しておけば遷移が以下のようになります

1. $$dp[i]\leftarrow \min\left(dp[i],D_i\right)$$
2.
$$
\begin{aligned}
dp[i] &\leftarrow \min\left(
dp[i],
\min_{i-K\leq j\lt i }\left(dp[j]+d(0,j)+d(0,j+1)+D_{i}-D_{j+1}\right)\right)
\\
&=
\min\left(dp[i],D_i+\min_{i-K\leq j\lt i}\left(dp[j]+d(0,j)+d(0,j+1)-D_{j+1}\right)\right)
\end{aligned}
$$

1.については, 前処理 $O(N)$ の下で $O(1)$ で遷移できます.
2.については, $j$が区間を動くことに注目するとセグメント木やスライド最小値により $O(\log N)$ あるいはならし $O(1)$ で遷移できます.

以上より, 状態 $O(N)$ 遷移 $O(\log N)$ のDPによって この問題を $O(N\log N)$ で解くことができました.

- 提出 : https://atcoder.jp/contests/abc334/submissions/48793676