【典型90問】076 - Cake Cut（★3）

問題へのリンク

解法

区間の和を求めるということでまずしゃくとり法が思いついた。
全体の総和をsumとして、x = sum/10 とすると、区間の総和がx以上になるまで右端を動かし続け、x以上になった時点で区間の総和がsumと等しいかを確認すれば良い。
また、sum/10の部分で切り捨てになったりするとややこしいので、数列の全ての要素を10倍しておくことにした。
さらに、円環になっていてめんどくさいが、rightがN以上になったときに0に戻してやることによってrightのみループできるようにした。

実装

const string YES = "Yes";
const string NO = "No";

void solve(long long N, std::vector<long long> A) {
    ll sum = 0;
    REP (i, N) {
        A[i] *= 10;
        sum += A[i];
    }
    ll x = sum/10;

    int right = 0;
    sum = 0;
    for (int left = 0; left < N; left++) {
        while (sum + A[right] <= x) {
            sum += A[right];
            right++;
            if (right >= N) right = 0;
        }

        if (sum == x){
            c(YES)
            return;
        }

        if (left == right) right++;
        else sum -= A[left];
    }

    c(NO)
}

解説の解法

二分探索で解けると聞いてすぐに理解できなかった。
数列が負数を含まない場合、累積和を取った配列は必ず昇順になることを利用しているようだ。
区間の左端ごとに、二分探索によって条件を満たす右端が存在するかどうかを判定するみたいだ。

実装

void solve(long long N, std::vector<long long> A) {
    REP (i, N) {
        A[i]*=10;
        A.push_back(A[i]);
    }

    vector<ll> sum(N*2+1, 0);
    
    for (int i = 1; i <= N*2; i++) {
        sum[i] = sum[i-1] + A[i-1];
    }

    for (int left = 0; left <= N; left++) {
        ll x = sum[left] + sum[N]/10;
        auto iter = lower_bound(all(sum), x);
        if (*iter == x) {
            c(YES)
            return;
        }
    }

    c(NO)
}