Codeforces #320 Div2 D

問題

http://codeforces.com/contest/579/problem/D

整数N,K,XそしてN個の整数Aが与えられる。
N個の整数Aのうち、一つの整数A[i](1<= i <= N)にXをK回かける。
そして残りのN-1個の整数とA[i]をOR演算した場合の最大値を求める。

解法

全探索だと間に合わなかったので、A[0]からA[N - 1]までとA[N - 1]からA[0]までの部分和の計算結果ごとに配列に記録していった。

例えば、問題ページの2つ目のサンプルケースの場合を考えると、
N = 4, K = 2 ,X = 3で、A = { 1, 2, 4, 8 }なので 添え字が0からNまでの部分和の配列をsumAとすると、
sumA[0] = 0として、
sumA[1] = sumA[0] OR A[0] (1 = 0 OR 1)
sumA[2] = sumA[1] OR A[1] (3 = 1 OR 2)
sumA[3] = sumA[2] OR A[2] (7 = 3 OR 4)
sumA[4] = sumA[3] OR A[3] (15 = 7 OR 8)
という風にしていき、逆方向からも部分和を求めていく。
逆方向から部分和を求める配列をsumBとすると、
sumB[4] = 0として、
sumB[3] = sumB[4] OR A[3] (8 = 0 OR 8)
sumB[2] = sumB[3] OR A[2] (12 = 8 OR 4)
sumB[1] = sumB[2] OR A[1] (14 = 12 OR 2)
sumB[0] = sumB[1] OR A[0] (15 = 14 OR 1)

そして、A[i]を K回 Xをかけた値と部分和の計算結果を使って最大値を求める。

ソースコード

import java.util.Scanner;
public class D
{
	public void solve()
	{
		Scanner cin = new Scanner(System.in);
		int N = cin.nextInt();
		int K = cin.nextInt();
		int x = cin.nextInt();
		int[] a = new int[N];
		long[] b = new long[N];
		long[] sumA = new long[N + 1];
		long[] sumB = new long[N + 1];
		for(int i = 0;i < N;i++)
		{
			int j = cin.nextInt();
			a[i] = j;
			b[i] = j;
		}

		for(int i = 0;i < N;i++)
		{
			sumA[i + 1] = sumA[i] | a[i];
		}

		for(int i = N - 1;i >= 0;i--)
		{
			sumB[i] = sumB[i + 1] | a[i];
		}
		long ans = 0;
		for(int i = 0;i < N;i++)
		{
			for(int j = 0;j < K;j++)
			{
				b[i] *= x;
			}

			long max = sumA[i] | b[i] | sumB[i + 1];
			ans = Math.max(ans,max);
		}
		System.out.println(ans);
	}
	public static void main(String[] args) 
	{
		new D().solve();	
	}
}