AtCoder ARC #100 : E - Or Plus Max

第100回おめでとうございます。
https://beta.atcoder.jp/contests/arc100/tasks/arc100_c

問題

長さ2^Nの添え字が0-originな数列Aが与えられる。
Kを1～(2^N-1)まで変化させたとき、0≦i＜jかつ(i or j)≦Kを満たすi,jのうちA[i]+A[j]の最大値を求めよ。

解法

B(x) := xをbitmaskとみなしたとき、xの部分集合である異なる2値a,bに対するA[a]+A[b]の最大値
とする。B(1)～B(K)を求めれば、すなわちこの問題の解となる。

B(x)を求めるため、以下を考えよう。C(x)は整数のペアであり、B(x)は明らかにそのペアの和である。
C(x) := xをbitmaskとみなしたとき、xの部分集合であるに対するA[a]のうち、上位２個(同じaを２回取ってはいけない)

初期状態としてC(x) := {A[x], 0}とし、高速ゼータ変換の要領でC(x)を更新していけば、最終的にB(x)も求められる。

int N;
ll A[1<<18];
vector<ll> V[1<<18];
ll S[1<<18][19];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,1<<N) {
		cin>>x;
		V[i]={x,0};
	}
	
	FOR(i,N) {
		FOR(x,1<<N) if(x&(1<<i)) {
			V[x].push_back(V[x^(1<<i)][0]);
			V[x].push_back(V[x^(1<<i)][1]);
			sort(ALL(V[x]));
			reverse(ALL(V[x]));
			V[x].resize(2);
		}
	}
	
	ll ma=0;
	for(int k=1;k<=(1<<N)-1;k++) {
		ma=max(ma,V[k][0]+V[k][1]);
		cout<<ma<<endl;
	}
	
}

まとめ

コードは非常に単純。