Codeforces #320 Div1 B. "Or" Game

意外にひっかけ問題。
http://codeforces.com/contest/578/problem/B

問題

N要素の数列A[i]が与えられる。
数列の全要素のorを取った値を考える。

ここで、A中の要素を1つ選びX倍(2≦X≦8)を行う処理を最大K回行うことができる(同じ要素に複数回適用しても良い)。
数列の全要素のorを最大化せよ。

解法

Xは２以上なので、最上位bitが最高である要素の１つににK回処理を行うのが最適なのは明らかである。
よってK回処理を行う要素iを総当たりし、max( (A[0..(i-1)]のor) | (A[i]*X^K) | (A[(i+1..(N-1))]のor)を求めればよい。
事前に数列の前から及び後ろからの累積和を取っておくと、全体でO(N)で済む。

なお、本番はdp[要素][残り可能処理回数]:=(そこまでのorの最大値)で１要素ずつ順に0～K回X倍していく場合を処理していくDPがあったが、これはうまく行かない。
途中までだけ見ると最大値でも、最終的に悪手である場合があるためである。
例えばK=1,X=2,A={18,17}だと18を倍にした方がよいが、{18,17,4}だと17を倍にした方が得である。(18を倍にすることで4のbitが立ってしまい、最後の4のorが無駄になる)

int N,K,X;
ll FX;
ll A[202020];
ll L[202020],R[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X;
	FOR(i,N) cin>>A[i];
	FX=1;
	while(K--) FX*=X;
	
	FOR(i,N) L[i+1]=((i)?L[i]:0) | A[i];
	for(i=N-1;i>=0;i--) R[i+1]=((i)?R[i+2]:0) | A[i];
	
	ll ma=0;
	FOR(i,N) ma=max(ma,L[i] | R[i+2] | (A[i]*FX));
	cout<<ma<<endl;
	
}

まとめ

DP行かなくて助かった…。