D. Alice, Bob and Candies (Codeforces Round #640 Div. 4)

問題

https://codeforces.com/contest/1352/problem/D

問題概要

非負整数で構成された長さnの数列が与えられる。アリスは右からボブは左から以下の規則のとおりに数列の数字を取っていく。

• 最初にアリスが一番左の数字をひとつだけ取る
• 次にボブが右から取る
  • 取った数字の和が、アリスが最初に取った数字を上回るまで取り進める
• 以下、交互に相手が直前に取った数字の和を上回るまで取り進める
• 残りが少なくなり相手の数字を上回れない場合は、構わず全部取る

二人が最後まで取りきった時のターン数とそれぞれが取った数字の合計を答えよ。

考察

単純にシミュレーションしても線形時間で終わりますし制約は2*10^5なので、与えられた条件に沿って素直に実装するだけです。

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        int prev = 0;
        int turn = 0;
        int alice = 0;
        int bob = 0;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int cur = 0;
            if (turn % 2 == 0) {
                while (cur <= prev and l <= r) {
                    cur += a[l];
                    l++;
                }
                alice += cur;
            } else {
                while (cur <= prev and l <= r) {
                    cur += a[r];
                    r--;
                }
                bob += cur;
            }
            turn++;
            prev = cur;
        }
        cout << turn << " " << alice << " " << bob << endl;
    }
}

感想

Div. 4、こういうシンプルな問題がもっと出るのかと思ってました。