ARC096 D : Static Sushi(500)
作成日：2018.09.16
最終更新日：2018.09.16
問題概要
外周$C$メートルの円形の机の周上に$N$貫の寿司が置かれており、$i$貫目は出発点から$x_i$メートル時計回りに進んだ位置にあり、$v_i$kcalを有する。
出発点から机の外周を任意の方向に移動しながら、目の前にある寿司をいくつか食べた後に停止することにする。
$1$メートルの移動により$1$kcal消費する時、摂取したエネルギーから消費したエネルギーを引いた値の最大値を求めよ。
制約
$1 \leq N \leq 10^5$
$2 \leq C \leq 10^{14}$
$1 \leq x_1 \lt x_2 \lt ... \lt x_N \lt C$
$1 \leq v_i \leq 10^9$
考え方
目の前に寿司があっても食べないのは損であるから、移動した区間内の寿司はすべて食べたものとして良い。
また、寿司がない地点へ移動して停止するのも損であるから、移動した区間の両端は寿司が置いてあったか出発点であったかのいずれかである。
さらに寄り道をするのは損であるから、移動は出発点から区間の一方の端点へ向かった後、引き返してもう一方の端点へ向かうのが良い。
以上より、先に向かう端点とその方向及び後に向かう端点を出発点または寿司が置かれている位置から決めれば、エネルギーの収支が決まることが分かる。
$x_0 = 0$,$x_{N+1} = C$とし、端点を$x_p,x_q$($p \lt q$)とする。
$x_p$に先に向かう時のエネルギーの収支は$\sum_{1 \leq i \leq p}v_i$$+ \sum_{q \leq j \leq N} v_j$$-(2x_p+C-x_q)$であり、$x_p$に先に向かう時のエネルギーの収支は$\sum_{1 \leq i \leq p}v_i$$+ \sum_{q \leq j \leq N} v_j$$-(x_p+2(C-x_q))$である。
求めるべきは$p,q$を動かしたときのこれらの最大値である。
前者において$p$を固定すると、$max_{p \lt q \leq N+1}($$\sum_{q \leq j \leq N} v_j$$- C + x_q$$)$が求まれば良いが、これは$q$を大きいほうから見ていけば容易に求められる。
後者においても同様であるから、$v_i$の累積和を$O(N)$の前計算で求めておけば、答えを$O(N)$で求めることができる。
ソースコード
マクロ等はこちら
const int MC = 1e5 + 3;
int N;
LL C,x[MC],v[MC],s[MC];
int main(){
cin >> N >> C;
repp(i,1,N+1){
cin >> x[i] >> v[i];
s[i] = s[i-1] + v[i];
}
LL ans = 0;
LL mx0 = 0 , mx1 = 0;
repm(i,N,0){
ans = max(ans,s[i]-x[i]+mx0);
ans = max(ans,s[i]-2*x[i]+mx1);
mx0 = max(mx0,s[N]-s[i-1]-2*(C-x[i]));
mx1 = max(mx1,s[N]-s[i-1]-(C-x[i]));
}
cout << max(ans,mx1) << endl;
return 0;
}解法まとめ
$max_{0 \leq p \leq N}($$\sum_{1 \leq i \leq p}v_i$$-x_p$$+ max_{p \lt q \leq N+1}($$\sum_{q \leq j \leq N}v_j$$-2(C-x_q)))$と$max_{0 \leq p \leq N}($$\sum_{1 \leq i \leq p}v_i$$-2x_p$$+ max_{p \lt q \leq N+1}($$\sum_{q \leq j \leq N}v_j$$-(C-x_q)))$のうち大きいほうが答えである。
これは$\sum v_i$を前計算で求めておけば、$p$を降順に見ることによって$max_q$を更新しながら求めることができる。(9,11-19行)