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もあるかと言われると微妙….