AtCoder Regular Contest 072 E - Alice in linear land
はじめ距離0にいて目的地が距離Dのところにある。計画{d1, d2, ..., dN}があって、i回目の行動でd[i]進んだとき、現在地点よりも目的地に近くなるならばその方向に進む。通り過ぎた場合は折り返しもあり。この計画のqj番目を書き換えて目的地にゴール出来ないようにすることはできるか？
i番目の行動をした時に、その後の行動をしたときに目的地にたどり着けない最小の距離をdpで求める。このdpはdp[N]が1(残りの行動がない場合、ゴールできる可能性があるのはDの上にいる場合のみ)として後ろから更新できる。また最小の距離を求めているので、この数列は単調増加になる。
次にi番目まで行動した時の位置を前もって計算しておく。この時、行動のi番目を書き換えるとは、i-1番目まで行動が終わった位置からゴールまでの任意の位置に移動させることで目的地につかないようにできるか？という問題になる。
よって答えは、dpで求めたi番目の値が、i-1番目までの行動結果の位置よりも小さい場合、dpで求めた位置に移動するように書き換えることによってゴールできないようにすることができる。
逆の場合、距離が大きくなる方向へは移動できないので必ずゴールできてしまう。
折り返しとかがあるので、絶対値のdpで求める。
