ABC432 F - Candy Redistribution で知ったテク

問題のリンク

この問題は最終的に以下の問題を解くことに帰着されるのですが、解法が面白かったのでメモ。

問題

和が 0 であるような $N(\le20)$ 個の数がある。これらを、和が 0 のグループに分割する。グループ数の最大値を求めよ。

例： [1,2,4,-1,-1,-2,-3] → [[1,2,-3], [4, -1, -1, -2]]、[[1,-1], [2,-2], [4,-1,-3]] などの分割方法がある。グループ数の最大値は 3。

解法

以下のような $O(3^N)$ のアルゴリズムはすぐわかります。

vector<int> dp(1 << N, -1);
dp[0] = 0;
for (int bit = 0; bit < (1 << N); bit++) {
    for (int sub = bit; sub; sub = (sub - 1) & bit) {
        if (sum[sub] == 0) chmax(dp[bit], dp[bit ^ sub] + 1);
    }
}

しかし、$N$ が最大 20 なので $O(3^N)$ では厳しく、$O(N2^N)$ で求める必要があります。

ポイントは、「和が 0 のグループ数の最大値」を「数を任意に並べ替えたときの、累積和が 0 になる回数の最大値」と対応させられることです。これを利用することで、以下の $O(N2^N)$ の DP が得られます。

vector<int> dp(1 << N);
for (int bit = 0; bit < (1 << N); bit++) {
    for (int i = 0; i < N; i++) {
        if (bit & (1 << i)) {
            chmax(dp[bit], dp[bit ^ (1 << i)] + (sum[bit] == 0 ? 1 : 0));
        }
    }
}

公式解説はこの問題に帰着するところまでの説明がメインで、ここは「1 要素ずつ追加していく bitDP によって $O(N2^N)$ 時間で計算できます」と書かれているのみだったのですが、自分はこのパートだけわかりませんでした🙁

有名なのかもしれないですが、知らなかった & 面白かったです。