Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] B. "Or" Game

問題

codeforces.com

解法

一回 x を掛け算すると x は 2 以上なのでビットは 1 以上左にシフトします。

よって, 一つの数に集中的に x を掛け算するのが良いです(もしバラバラに x を掛け算すると, 左にシフトする数が少なくなるので不利)。

ということで, すべての a[i] について, x を k 回掛け算するのを試します。
a[i] を k 回掛け算した場合の a[0] | a[1] | ... | a[n-1] の値を確かめるには, 以下のようにします。

まず, すべての a[i] の j ビット目の値(0 か 1 です)を調べ, cnt[j][i] に覚えておきます。
また, 数列 a 全体の j ビット目の値の合計を cnt2[j] に覚えておきます。
で, a[i] に x を k 回掛け算するときは, cnt2[j] - cnt[j][i] が 1 以上ならば, j ビット目の値は a[i] 以外の値の or で反映されるので a[i]*x^k に 1<

const int MAXN = 200200;
ll a[MAXN];
int cnt[31][MAXN], cnt2[31];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k, x;
    cin >> n >> k >> x;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < 31; j++) {
            if ((a[i]>>j)&1) {
                cnt[j][i] = 1;
                cnt2[j] += 1;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll tmp = a[i];
        for (int j = 0; j < k; j++) tmp *= x;
        for (int j = 0; j < 31; j++) {
            if (cnt2[j]-cnt[j][i] > 0) tmp |= 1ll<<j;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}