けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #681 (Div. 1) A. Extreme Subtraction (R1800)

Codeforces いもす法的変換 数列 操作 Yes/No判定問題 算数と数学 区間 操作:区間 操作を好きな回数だけ行える 変数変換して扱いやすい同型な問題を見出す 条件の言い換え CodeforcesDIV1-A CodeforcesR1800 マルチテストケース問題

区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる！

問題概要

長さ N の数列 A_{1}, \dots, A_{N} が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ。

  • 数列の先頭から連続する何個かについて -1 する
  • 数列の末尾から連続する何個かについて -1 する

(というテストケースが T 個与えられる)

制約

  • 1 \le T \le 30000
  • 1 \le N の総和 \le 30000

考えたこと

数列の差分をとった世界で考える。そうすると、区間に加算する操作は、「2 点に対する操作」になる！！！

たとえば A = (3, 1, 4, 1, 5) に対して、最初の 3 個の要素から 1 を引くと A = (2, 0, 3, 1, 5) になる。差分をとった数列を D とすると...

  • 操作前： D = (3, -2, 3, -3, 4, -5)
  • 操作後： D = (2, -2, 3, -2, 4, -5)

となる。先頭に -1、3 番目に 1 を足す操作となっている。同様に末尾から連続する要素から 1 を引く操作は、 D の内点から 1 を引いて、末尾に 1 を引く操作となる。

よって、次の判定問題を解けばよいことがわかる。

  • D の内点 (先頭と末尾以外) に対して、以下のように操作ができるとして、内点をすべて 0 にできるかどうか +「+1」が D_{N} 回できる
    • 「-1」が D_{0} 回できる

D の内点のプラスの値の総和を求めて、それが D_{N} 回以下であれば OK。計算量は O(N)。

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<long long> a(N), b(N-1);
        for (int i = 0; i < N; ++i) cin >> a[i];
        for (int i = 0; i < N-1; ++i) b[i] = a[i+1] - a[i];

        long long minus = a[0], plus = a.back();
        long long need_plus = 0;
        for (int i = 0; i < N-1; ++i) if (b[i] >= 0) need_plus += b[i];
        if (plus >= need_plus) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}