ACM-ICPC 2018 模擬国内予選: F. 対空シールド
解法
シールド$1, \dots, M - 1$だけのまま高階imos法で$O(M + N)$の前処理。シールド$M$の位置を最悪$O(N^2)$でやればかなり高速に通る。
$u \in N$番目のユニットの強さは式$f(u, x_{M-1}) = \sum_{i \in M} \mathrm{max}(0, a_i - (x_i - u)^2)$である。 $x_{M-1}$以外はすべて固定されているので適当な$b_u$に対し$f(u, x_{M-1}) = \mathrm{max}(0, a_{M-1} - (x_{M-1} - u)^2) + b_u$。 まずはこの$b_u$を求めたい。 $O(MN)$で遅いが愚直には、シールド$i \in M$のそれぞれについて、すべてのユニット$u \in N$に対し$b_u \gets b_u + \mathrm{max}(0, a_i - (x_i - u)^2)$と更新。 $a_i \le 10^9$のため計算量は落ちないが、ユニットを舐める範囲を絞れば更新式を$b_u \gets b_u + a_i - (x_i - u)^2$にできる。 これは高階のimos法を用いることのできる形なので$b_u$は解決。
$b_u$が出れば目的関数$g(x_{M-1}) = \min \{ f(u, x_{M-1}) \mid u \in N \}$は$O(N)$で求まる。 ユニットを調べる順番を$b_u$の順にすれば高速化が期待でき、試しに実装してみると間に合う。 列$b_u$の作り方が特殊なことを使えば何か証明できる可能性はある。
note
高階imos法で無理矢理に線形性みたいなのが出てくるの気付いてなかった。 「線形になるまで微分すれば線形」という話なのでよく考えたら自明なんだけど面白い。
入力を覗き見ると大きなケースはひとつだけなので勇気を持って実装をしましょう。
実装
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
ll sq(ll x) { return x * x; }
ll solve(int n, int m, vector<int> const & a, vector<int> const & x) {
// compute strength without last shield, using imos O(N + M)
constexpr int D = 3;
vector<ll> strength(n);
vector<array<ll, D> > strength_fwd(n + 1); // imos
vector<array<ll, D> > strength_bck(n + 1); // imos
REP (i, m - 1) {
strength[x[i]] += a[i];
int sqrt_a = ceil(sqrt(a[i]));
// forward
int r = min(n, x[i] + sqrt_a); // [x_i + 1, r)
if (x[i] + 1 < r) {
strength_fwd[x[i] + 1][0] += a[i];
strength_fwd[r ][0] -= a[i];
strength_fwd[x[i] + 1][1] -= 1;
strength_fwd[x[i] + 1][2] -= 2;
strength_fwd[r ][0] += sq(r - x[i] - 1);
strength_fwd[r ][1] += 2 * (r - x[i] - 1) + 1;
strength_fwd[r ][2] += 2;
}
// backward
int l = max(-1, x[i] - sqrt_a); // (l, x_i - 1]
if (l < x[i] - 1) {
strength_bck[l + 1][0] -= a[i];
strength_bck[(x[i] - 1) + 1][0] += a[i];
strength_bck[l + 1][0] += sq(x[i] - l - 1);
strength_bck[l + 1][1] += 2 * (x[i] - l - 1) + 1;
strength_bck[l + 1][2] += 2;
strength_bck[(x[i] - 1) + 1][1] -= 1;
strength_bck[(x[i] - 1) + 1][2] -= 2;
}
}
// forward propagation
REP (u, n) {
REP (d, D - 1) strength_fwd[u][d] += strength_fwd[u][d + 1];
REP (d, D) strength_fwd[u + 1][d] += strength_fwd[u][d];
strength[u] += strength_fwd[u][0];
}
// backward propagation
REP_R (u, n) {
REP (d, D - 1) strength_bck[u + 1][d] += strength_bck[u + 1][d + 1];
REP (d, D) strength_bck[u][d] += strength_bck[u + 1][d];
strength[u] += strength_bck[u + 1][0];
}
// check
if (n *(ll) m < 10000) {
REP (u, n) {
ll acc = 0;
REP (i, m - 1) {
acc += max(0ll, a[i] - sq(u - x[i]));
}
assert (strength[u] == acc);
}
}
// find the unit to put the last shield
vector<int> order(n);
iota(ALL(order), 0);
sort(ALL(order), [&](int u1, int u2) { return strength[u1] < strength[u2]; });
auto get_min_strength = [&](int y) { // at least O(N), but this is fast
ll acc = LLONG_MAX;
int bottleneck = -1;
for (int u : order) {
if (acc <= strength[u]) break;
ll strength_u = strength[u] + max(0ll, a.back() - sq(u - y));
if (strength_u < acc) {
acc = strength_u;
bottleneck = u;
}
}
return make_pair(acc, bottleneck);
};
ll acc = LLONG_MIN;
REP (u, n) { // bruteforce for x_{m - 1}
acc = max(acc, get_min_strength(u).first);
}
return acc;
}
int main() {
while (true) {
// input
int n, m; cin >> n >> m;
if (n == 0 and m == 0) break;
vector<int> a(m), x(m - 1);
REP (i, m - 1) {
cin >> a[i] >> x[i];
-- x[i]; // NOTE: this modifies the expr of strength
}
cin >> a[m - 1];
// solve
ll answer = solve(n, m, a, x);
// output
cout << answer << endl;
cerr << answer << endl;
}
return 0;
}