ARC100 E問題 OrPlusMax (高速ゼータ変換)

E - Or Plus Max
高速ゼータ変換の問題。といっても貼るだけの問題ではなく、集合や演算を自分で考察してうまくテンプレに落としてやる必要がある。
また、やってることはbitDPなので言葉を知らなくても解ける(僕はコンテスト中には解けてない)
この記事では、どこの部分がいわゆる高速ゼータ変換のテンプレになっているかを書いておく。

1. そもそも高速ゼータ変換とは ?

こちらの記事を参考にさせていただきました。
https://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228

高速ゼータ変換
集合に対する関数 に対し、全集合 に対して、

これを実装したものが

 rep (i, n) rep (b, 1 << n) if ((b & (1 << i)) == 0 )  a[b] += a[b | (1 << i)];

と書けるそう。

1. 本問ではどのように使われているのか ?

結論から先に言うと、

• 集合

• 演算

と定義する。ソースコードはこんな感じ。

 rep (i, n) rep (b, 1 << n) if ((b & (1 << i)) == 1 )  
        a[b] = merge( a[b] , a[b ^ (1 << i)] );

( おまけ )
集合をと取ることもできるが、
この時は になっており、
理解の足りない僕はあれ?包含関係逆じゃね ? いいの ? とか考えてしまった。
また、こちらの方針で実装する場合は以下のようになる。

for (int i = (n-1); i >= 0 ; i-- )
    for (int b = (1 << n) - 1 ; b >=  0 ; b-- )
        if (!(b & (1 << i))) dp[b|(1<<i)] = merge(dp[b|(1<<i)],dp[b]);

ループの向きを逆にしないといけない。これは大いにバグの原因になりそう。

最後に僕のE問題のソースコード

//演算
#include <bits/stdc++.h>
vector<long> merge(vector<long> &A,vector<long> &B) {
	vector<long> cp(A);
	REP(i,B.size()) cp.push_back(B[i]);
	sort((cp).begin(),(cp).end(),greater<long>());
	return vector<long>(cp.begin(),cp.begin()+min(2,(int)cp.size()));
}

int main(void) {
	int N;
	cin >> N;
	vector<long> A(1<<N);
	for(long i = 0;i < (1<<N);i++) cin >> A[i];
	vector<vector<long>> dp(1<<N,vector<long>(2,0));
	for(long i = 0;i < (1<<N);i++) dp[i] = {A[i]};

	/*ゼータ変換部分*/
	for(int i = 0;i < N;i++) REP(b,1<<N) if ((b & (1 << i))) {
		dp[b] = merge(dp[b],dp[b ^ (1 << i)]);
	}

	long ans = 0;
	for(int i = 1;i < (1<<N);i++) {
		ans = max(ans,dp[i][0]+dp[i][1]);
		cout << ans << endl;
	}
}