AOJ 2617 Air Pollution

解法

この問題を解く上でポイントとなるのは,大気を循環させたときに,(p[i-1], p[i], p[i+1]) の累積和が不変であるということです.

今大気の状態が (a, b, c, d) であるとしましょう.累積和を取ると,(a, a + b, a + b + c, a + b + c + d) です.
b を選んで大気を循環させてみます.すると,(a + b, -b, b + c, d) となります.累積和を取ると,(a + b, a, a + b + c, a + b + c + d) になっています.
よく見ると,累積和で最初の2つがswapされているだけだということに気づきます.つまり大気の循環は,累積和を取った上での隣接2項間のswapに対応します.

さて,最終的に l[i] が達成すべき大気の綺麗さですが,これは正の値なので,累積和を取ると単調増加になっているはずです.
つまり,もし達成できるなら,これは最初の累積和の転倒数を求める問題と同じです.
達成できない場合というのは,累積和をソートした初項が負であるか,隣接二項の差が l[i] より小さいかのどちらかですから,これを確認すれば良いです.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
using ll = long long;
 
template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n) : n(n), dat(n, 0) {}
 
    void add(int i, T value) {
        for(; i<n; i |= i + 1) {
            dat[i] += value;
        }
    }
 
    T sum(int i) const {
        T res = 0;
        for(; i>=0; i = (i & (i+1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    T sum(int l, int r) const {
        return sum(r-1) - sum(l-1);
    }
 
private:
    const int n;
    std::vector<T> dat;
};
 
 
int main() {
    int n;
    scanf("%d", &n);
    vector<pair<ll, int>> v(n);
    vector<int> l(n);
    for(int i = 0; i < n; ++i) {
        int p;
        scanf("%d", &p);
        if(i == 0) {
            v[i] = make_pair(p, i);
        } else {
            v[i] = make_pair(v[i - 1].first + p, i);
        }
    }
    for(int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    sort(v.begin(), v.end() - 1);
    bool check = v[0].first >= l[0];
    for(int i = 1; i < n; ++i) {
        check &= v[i].first - v[i - 1].first >= l[i];
    }
    if(!check) {
        cout << -1 << endl;
        return 0;
    }
 
    fenwick_tree<int> bit(n);
    ll res = 0;
    for(int i = 0; i < n - 1; ++i) {
        res += i - bit.sum(v[i].second);
        bit.add(v[i].second, 1);
    }
    printf("%lld\n", res);
}

感想

自力で気づけず,教えてもらって解きました.
結構面白い問題だとは思いましたが,AOJ-ICPCで900もあるかと言われると微妙….