ABC475 C - Walk the Line

考え方

うろうろする方法はいろいろある。
しかし、一度行った町を再訪する意味がないことを考えると、調べる候補を削ることができる。
つまり、左に行って右に行ってまた左、のように $2$ 回以上折り返すのは意味がない。
一方向に進むだけ、または $1$ 回だけ折り返して $S$ を通過して反対へ行く場合、だけ考えれば十分。
しかも、折り返しまでの距離が $0$ と考えることで前者は後者に吸収できる。

ということで、折り返し位置を動かしながらゴール地点も動かす尺取法が成立する。
折り返し位置までで既に距離がオーバーするようになったら打ち切り。
あるいは、折り返した後 $S$ まで戻ることすらできなくなった場合も打ち切りでよい。

これを $S$ から左右どちらに出発するかで $2$ 回やって、最大値を答えればよい。
計算量は $O(N)$ である。

尺取法の際、毎回 $A$ の値を足し引きしてもよいが、累積和で町の位置を出しておくと書きやすくなる。

入力例1での動作

入力を受け取る。

n: 6
s: 3
l: 10
a: {5, 2, 4, 1, 6}

町の番号は 0-indexed とする。
町 $2$ から出発し、移動できる距離の合計は $10$ 以下である。

各町の位置を累積和で求めると、左から順に $0,5,7,11,12,18$ となる。
出発地点である町 $2$ の位置は $7$ である。

まず、左へ進んでから右へ進む場合を調べる。
左端を $1$ つずつ左へ動かし、距離和が $10$ を超える間は右端も左へ動かす。
左移動距離は出発地点から左端まで、右移動距離は左端から右端までの距離とする。

左へ進んでから右へ進む場合、訪問できる町数の最大値は $4$ である。

次に、右へ進んでから左へ進む場合を調べる。
今度は右端を $1$ つずつ右へ動かし、距離和が $10$ を超える間は左端も右へ動かす。
右移動距離は出発地点から右端まで、左移動距離は右端から左端までの距離とする。

町 $5$ は、出発地点から右へ進むだけで距離が $11$ となるので、ここで探索を打ち切る。
右へ進んでから左へ進む場合、訪問できる町数の最大値は $3$ である。

両方の最大値を比べると、答えは $4$ となる。

注意点

街の位置や移動距離は、int 型からはみ出る。
long long 型を用いること。

別解

「$S$ を挟んでここからここまで」という範囲を全探索すると、計算量が $O(N^2)$ になってしまう。
だが、実は $N$ の上限が $8000$ なので、今回はそれでも間に合う。

指定範囲の街を全て巡る最短距離は、以下の $2$ つの短い方を調べるだけで見つかる。

• 範囲の一番左まで行ってから、範囲の一番右まで行く
• 範囲の一番右まで行ってから、範囲の一番左まで行く

累積和により町の位置が計算してあれば、候補 $1$ つの判定が $O(1)$ で済む。
よって、全体で計算量は $O(N^2)$ になる。