CODE FESTIVAL 2018 qual A D - 通勤

これを通せたおかげで予選通過できました。嬉しい。

問題

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d

解法

$X_0=0$ とします。DPをします。

$dp[i][j]:=$ ガソリンスタンド $i$ まで来るにあたって、ガソリンスタンド $j$ で最後に補給するとしたときの、そこまでのガソリンスタンドを書店に建て替えるパターン数

次の3つを考える必要があります。

近くのガソリンスタンド $j$ で補給をしていてガソリンスタンド $i$ で補給ができないとき、ガソリンスタンド $i$ を書店に建て替えても建て替えなくても変わらない
やや遠くのガソリンスタンド $j$ で補給をしていてガソリンスタンド $i$ で補給ができるとき、ガソリンスタンド $i$ を書店に建て替えるなら最後に補給した場所は変わらず、建て替えないなら最後に補給したガソリンスタンドは $i$ になる
めっちゃ遠いガソリンスタンド $j$ で補給をしていてガソリンスタンド $i$ までたどり着けないとき、ガソリンスタンド $j$ までの情報は無意味になる

まとめると、次のようになります。

$dp[i][j]= \begin{cases} \displaystyle \sum_{F - T< X_i-X_{j'} \leq F} dp[i-1][j'] & (i=j) \\ 2dp[i-1][j] & (0 < X_i-X_j \leq F - T)\\ dp[i-1][j] & (F - T< X_i-X_j \leq F) \end{cases}$

これを愚直に処理すると $O(N^2)$ となりTLEします。データを使いまわしてオーダーを落とすことを考えましょう。
列の末尾 $n$ 項を $2$ 倍し、その前の $m$ 項の区間和を末尾に追加するという操作ができればいいわけです。
さらに、項は「 $2$ 倍区間」→「区間和区間」→「無意味な区間」と移動する事を利用し、それぞれの区間をqueueで持ち、区間和も持っておけば、遷移が高速化できます。要は尺取法なので、全体の計算量は $O(N)$ となります。