The 2nd Universal Cup. Stage 4: Taipei I. Interval Addition

問題のリンク：https://qoj.ac/contest/1382/problem/7566

問題概要

長さ $n$ の数列が与えられる。1回の操作で、連続する区間と任意の実数を選び各要素に足し合わせる時、最小何回の操作で数列の全ての要素を0にできるか求めよ。

制約

$1 \le n \le 23$

解法

いきなりですが、区間に数を足す時の典型テクで、先頭と末尾に0を追加した数列の階差数列を取って考えます。

すると区間 $[l, r]$ に実数 $x$ を足す操作は、$l$ 項目に $+x$、$r+1$ 項目に $-x$ する操作に言い換えられ、この操作で長さ $n+1$ の数列の各要素を0にする問題になります。

総和が0となる集合について、集合の大きさを $K$ とおくと、$K - 1$ 回の操作で全ての要素を0に出来ることから、総和が0の集合で出来るだけ分割することを目標とすれば良いことが分かります。ちなみに、上記で得られた階差数列の総和は常に0です。

この段階で $O(3 ^ n)$ の解法が得られます。チームメイトは足して0になるペアを予め除く、枝刈りを利用してACしていました。

ここでは $O(n 2 ^ n)$ の解法を扱います。大きさ $K$ の集合に対するコストが $K - 1$ となることを利用し、遷移先の総和が0かどうか、01のコストを定めるようにすると、1要素ずつ加えていくDPに寄与を分解することができ、計算量が落ちます。

実装

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<ll> a(n), b(n + 1);
    ll pre = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i] - pre;
        pre = a[i];
    }
    b[n] = 0 - pre;
    int m = n + 1;
    vector<ll> sum(1 << m);
    for (int i = 0; i < (1 << m); ++i) {
        for (int j = 0; j < m; ++j) {
            if ((1 << j) & i) sum[i] += b[j];
        }
    }
    vector<int> dp(1 << m, 1e9);
    dp[0] = 0;
    for (int i = 0; i < (1 << m); ++i) {
        for (int j = 0; j < m; ++j) {
            if ((1 << j) & i) continue;
            int k = i + (1 << j);
            dp[k] = min(dp[k], dp[i] + (sum[k] != 0));
        }
    }
    cout << dp.back() << endl;
}