ABC 095 D - Static Sushi

問題

円周上に配置された $n$ 個の点それぞれに価値 $V _ i$ が定まっている。円周上を自由に移動していくつかの点を回収するとき、「価値の総和$-$移動距離」の最大値を求めよ。（$n\leq10 ^ 5$）

atcoder.jp

解説

$n$ 点の座標をそれぞれ $X _ 0 < \cdots < X _ {n - 1}$ とすると、 最適な経路は以下の $2$ 通りに分けられる。

1. 右回りにスタートして $X _ i$ で折り返し、左回りに進んで $X _ j$ でやめる。
2. 左回りにスタートして $X _ j$ で折り返し、右回りに進んで $X _ i$ でやめる。

$S _ i = \displaystyle\sum _ {j = 0} ^ {i - 1} V _ j$ とすると、 $1$ の場合の「価値の総和$-$移動距離」の最大値は $$ \mathrm{max} \{ (S _ i -2 X _{i -1}) + (S _ n - S _ j - (c - X _ j) ) \mid i \leq j \} $$ となる。ただし、補助的に $X _ {-1}=0,\ X _ {n} = c$ とする。これは、各 $j$ に対して $\mathrm{max} \{ S _ i -2 X _ {i -1} \mid i = 0,\ldots,j \}$ を累積的に計算しておくことで、$O(n)$ で計算できる。
同様に、$2$ の場合は $$ \mathrm{max} \{ (S _ i - X _ {i -1}) + (S _ n - S _ j - 2 (c - X _ j) ) \mid i \leq j \} $$ で求められるので、$2$ つの場合の大きい方を解とすればよい。

実装

n, c = map(int, input().split())
XV = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, v in XV]
V = [v for x, v in XV]
S = [0]
for i in range(n):
    S.append(S[-1]+V[i])
# 右回りから行く場合
A = [0]
for i in range(1, n+1):
    A.append(max(A[-1], S[i]-2*X[i-1]))
B = []
for i in range(n):
    B.append(S[n]-S[i]-(c-X[i]))
B.append(0)
ans0 = max([A[i]+B[i] for i in range(n+1)])
# 左回りから行く場合
A = [0]
for i in range(1, n+1):
    A.append(max(A[-1], S[i]-X[i-1]))
B = []
for i in range(n):
    B.append(S[n]-S[i]-2*(c-X[i]))
B.append(0)
ans1 = max([A[i]+B[i] for i in range(n+1)])
print(max(ans0, ans1))

atcoder.jp