https://codeforces.com/contest/1253/problem/E
区間[$1, M$]で表される道があり、そこに$N$本のアンテナが立っている。アンテナ$i$は[$x_i-s_i, x_i+s_i$]に電波を届けることができる。アンテナを1つ選んでコインを1枚支払うことによって$s_i$を1増やすことができるとき、[$1, M$]をすべてカバーするために必要なコインの最小枚数を求めよ。
$DP[i]=[1, i]$をカバーするための最小コイン枚数
とする。ここで、[$1, i$]がカバーされているとき[$1, i-1$]もカバーされていることから、$DP[i]$は$i$について広義単調増加であり、これを最短経路問題として解くことができる。
$[0,M]$の$M+1$個のノードを用意し、ノード$i$をそれぞれ$DP[i]$に対応させる。ここで、DP[0]は座標1がカバーされていない状態を表す。このとき、ノード0からノード$M$への最短距離が$[1, M]$をカバーするための最小コイン枚数となるように辺を貼る。
あるアンテナが区間[$L, R$]をカバーしているとき、ノード[$L-1, R$]のどこからでも[$L, R$]へ遷移できることを意味する。これはノード[$L-1, R$]間の全点対に辺を貼ることに対応するが、辺を($L-1, R$)に貼って、すべての$i$に対してコスト0の後退辺($i, i-1$)を貼ることで辺の数を減らすことができる。
区間[$1, i-1$]がカバーされているとき、$i$以降をカバーするために、どのアンテナを使うこともあり得る。ここで、カバー範囲が[$L, R$]であるようなアンテナを使うとする。このとき必要に応じてアンテナを強化する必要があるが、それは以下のように行う。
$i\lt L$のとき、アンテナの$s$を$L-i$だけ拡張する必要があり、その範囲は[$i, R+(L-i)$]となる。よって、($i-1, R+(L-i)$)にコスト$L-i$の辺を張れば良い。
$L\leq i$かつ$i\leq R$であるとき、アンテナの拡張は必要なく、辺($i-1, R$)をコスト0で張る。
$R\lt i$であるとき、当該アンテナを使って右に行くことはできないが、そのアンテナを使って$i$に遷移してくることはあり得る。その場合には$s$を$i-R$だけ拡張することになるので、辺($L-(i-R)-1, i$)をコスト$i-R$で張る。
以上をすべてのノード$\times$すべてのアンテナに対して行ったグラフに対して、ノード0から$M$までの最短距離を求めればよい。
第二回全国統一プログラミング王決定戦予選のDと非常によく似ている。当該問題は遅延セグ木を使ってゴリ推したのだが、想定解法を読んでいたので解きたかった。