CS Academy 082 DIV1 C - City Break

しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかも

CS Academy 082 DIV1 C - City Break

問題概要

円環状に 個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街 1 の距離)。

今街 S からスタートする。「訪れたことのない街のうち、現在地からもっとも近い街へ移動する」ことを繰り返して、最終的にすべての街を訪れた時、移動距離の総和を求めよ。

制約

• 

解法

数珠は基本的に、同じベクトルを2週3週とコピーしておくと扱いやすい。index i + N や i + 2N は i と同じ地点を表すものと考える。最初は、S を 0-indexed にして、N を足しておく

• left = S-1+N (訪れた区間の左端)
• right = S-1+N (訪れた区間の右端)
• cur = S-1+N (今いる場所)

を初期値として、毎ステップごとに

• left - 1
• right + 1

のどちらに移動するかを考えれば良い。数珠を 3 週したものの累積和をとっておいて

• sum[cur] - sum[left - 1]
• sum[right + 1] - sum[cur]

のうち小さい方に移動する。同じ値だったら、(left - 1) % N と (right + 1) % N のうち小さい方に移動する。

#include <iostream>
#include <vector>
using namespace std;

int N, S;
vector<long long> a;
vector<long long> sum;

int main() {
    cin >> N >> S;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sum.resize(N*3+1, 0);
    S += N-1;
    for (int i = 0; i < 3*N; ++i) sum[i+1] = sum[i] + a[i%N];

    int left = S, right = S, cur = S;
    long long res = 0;
    while (right - left < N - 1) {
        long long ld = sum[cur] - sum[left - 1];
        long long rd = sum[right + 1] - sum[cur];
            
        bool isleft = false;
        if (ld < rd) isleft = true;
        if (ld == rd && ((left - 1) % N < (right + 1) % N)) isleft = true;
            
        if (isleft) res += ld, --left, cur = left;
        else res += rd, ++right, cur = right;
    }
    
    cout << res << endl;
}