ABC 095 D - Static Sushi

ABC 095 D - Static Sushi についてのメモを残します。

人間回転寿司

• 問題 : ABC 095 D - Static Sushi

下図は、初期位置 から反時計回りに歩き、 で U ターンし、 に戻ってきて、今度は時計回りに歩き、 で退店する様子を表している。

下図のように、 → → → という歩き方もある。

いずれも と は、寿司の位置または に一致しなければならず、寿司の位置でも でもない地点で折り返したり退店したりするのは、カロリーの無駄遣いである。

まずは、前者の → → → で考える。
と の位置を決めることで正味の摂取カロリーを計算できるが、素朴な全探索では で間に合わない。
の位置を としたとき、正味の摂取カロリーが最大となるような の位置を高速に求める方法はないだろうか。
ここで、 から時計回りに歩き、道中の寿司を食べながら の位置に到達したときの － 間の正味の摂取カロリーを とする。
ただし、初期位置 を とし、 とする。

の位置が のとき、 の位置の候補は であり、 のうち最大値をとる を の位置として採用するとよい。
ただし、ここでは最大値さえ分かればよい。

このようにして、 の位置で全探索し、正味の摂取カロリーの最大値を求める。
同様に、 → → → の場合についても行う。

実装

寿司のカロリーの累積和、 の累積和ならぬ "累積 max" なるものを用意しておくとよさそう。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N, C; cin >> N >> C;
  vector<long long> X(N), V(N);
  for (int i = 0; i < N; i++) cin >> X.at(i) >> V.at(i);

  // sumV[i] := [0, i) の寿司の栄養価の合計
  vector<long long> sumV(N+1, 0);
  for (int i = 0; i < N; i++) sumV.at(i+1) = sumV.at(i) + V.at(i);

  // 初期位置から時計回りに i 個目まで食べてもよいとき、
  // 正味の摂取カロリーの最大値
  vector<long long> maxA(N+1, 0);
  long long tmpA = 0;
  for (int i = 1; i <= N; i++) {
    tmpA = max(tmpA, sumV.at(i) - X.at(i-1));
    maxA.at(i) = tmpA;
  }

  // 初期位置から反時計回りに i 個目まで食べてよいとき、
  // 正味の摂取カロリーの最大値
  vector<long long> maxB(N+1, 0);
  long long tmpB = 0;
  for (int i = 1; i <= N; i++) {
    tmpB = max(tmpB, sumV.at(N) - sumV.at(N-i) - (C - X.at(N-i)));
    maxB.at(i) = tmpB;
  }

  long long ans = 0;
  // まず反時計回りに i 個目まで食べて、引き返して、
  // 時計回りに適切な個数食べる
  for (int i = 0; i <= N; i++) {
    long long cost = i ? (2 * (C - X.at(N-i))) : 0;
    ans = max(ans, sumV.at(N) - sumV.at(N-i) - cost + maxA.at(N-i));
  }
  // まず時計回りに i 個目まで食べて、引き返して、
  // 反時計回りに適切な個数食べる
  for (int i = 0; i <= N; i++) {
    long long cost = i ? (2 * X.at(i-1)) : 0;
    ans = max(ans, sumV.at(i) - cost + maxB.at(N-i));
  }
  cout << ans << endl;
}