ARC100 E - Or Plus Max

漂うインフレ感...？(適当いってます)

問題

E - Or Plus Max

感想

高速ゼータ変換初めて使いましたが。

ある集合Aに対して、A⊆Bを満たすBすべてに対する処理(逆も可)を各集合に対してうまく行うものという感覚でいいのかな？

詳しくはこの方の記事を参照くださいな。
d.hatena.ne.jp

この知識(もしくはO(n^3)の部分集合の列挙)が前提の問題ですね。

問題の考察ポイントに関してですが、

(上記の知識があると)x⊆Kを満たすA_xのうち大きいもの二つを見つけるのは簡単であるのはわかるため。

(i or j) <= K を満たす A_i + A_j の最大

を

ma[q] := (i or j) ⊆ K を満たすA_i + A_j の最大
としてから
max(ma[i])(1 <= i <= k)

と言い換えるところですね。
扱いやすい形に変えてあげましょうという話でした。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

pair<ll,ll> ans[1 << 20];
ll ret[1 << 20];

pair<ll,ll> toptwo(pair<ll,ll> A,pair<ll,ll> B){
	ll fir = max(A.FI,B.FI);
	ll sec = max(min(A.FI,B.FI),max(A.SE,B.SE));
	return MP(fir,sec);
}	

int main(){
	
	int n;cin >> n;
	
	REP(i,1<<n){
		ll tmp;cin >> tmp;
		ans[i].FI = tmp;
	}
	
	REP(i,n){
		for(int j = 0;j < (1<<n);j++){
			if(j & (1 << i)){
				ans[j] = toptwo(ans[j],ans[j^(1<<i)]);
			}
		}
	}
	
	REP(i,1<<n){
		ret[i] = ans[i].FI + ans[i].SE;
	}
	
	REP(i,1<<n){
		ret[i+1] = max(ret[i+1],ret[i]);
	}
	
	for(int i = 1;i < (1<<n);i++){
		cout << ret[i] << endl;
	}
	
	return 0;
}