Mister雑記

競プロやります。

ARC100-E 「Or Plus Max」 (700) 高速ゼータ変換解法

atcoder.jp

本記事は以下の記事の番外編です。

misteer.hatenablog.com

問題

略。

考察

misteer.hatenablog.com

以降 X = \{ 0, 1, \cdots, n - 1 \}とする。 また S \subseteq Xに対して Sを二進表記したものを B_S \in {\mathbb N}としたとき、 A_S := A_{B_S}という略記を使うことにする。

上の記事で述べたように、各 S \subseteq Xについて「 T \subseteq Sの中で A_Tの大きい方から2つ」が欲しい。そこで、以下のような加法の定義された集合 Gを考える。

  •  g \in Gについて g \subseteq {\cal P}(X), |g| \leq 2
  •  g, g' \in Gについて、 g + g'を「 g \cup g'から A_Sが大きい方2つのみを残した集合」として定義する。

これは結合則・交換則を満たすため高速ゼータ変換を施すことができる。初期値は f(S) = \{ S \}

実装例

atcoder.jp

struct G {
    vector<int> idx;
    static vector<int> a;
 
    G& operator+=(const G& opp) {
        std::copy(opp.idx.begin(), opp.idx.end(),
                  std::back_inserter(idx));
        std::sort(idx.begin(), idx.end(), [&](Int i, Int j) {
            return a[i] == a[j] ? i < j : a[i] > a[j];
        });
        idx.erase(std::unique(idx.begin(), idx.end()), idx.end());
        idx.resize(2);
        return *this;
    }
};
vector<int> G::a;
 
int main() {
    int n;
    std::cin >> n;
    vector<int> a(1 << n);
    for (auto& x : a) std::cin >> x;
    G::a = a;
 
    vector<G> g(1 << n);
    for (int s = 0; s < (1 << n); ++s) {
        g[s].idx.push_back(s);
    }
 
    // 高速ゼータ変換 下位集合版
    for (int k = 0; k < n; ++k) {
        for (int b = 0; b < (1 << n); ++b) {
            if ((b >> k) & 1) {
                g[b] += g[b ^ (1 << k)];
            }
        }
    }
 
    Int max = 0;
    for (int s = 1; s < (1 << n); ++s) {
        max = std::max(max, a[g[s].idx[0]] + a[g[s].idx[1]]);
        std::cout << max << std::endl;
    }
    return 0;
}