第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

第5回 ドワンゴからの挑戦状 予選 に参加しました．

B - Sum AND Subarrays

問題

beta.atcoder.jp

考察

まず累積和を使って全ての部分列の和を求めます．

この部分列の和の集合の中から 個選んで，その論理積の最大値を求めるわけですが，最初に取りうる値の最大値を考えてみます．

自然数 と の論理積は より大きくなることはありえないので
最大値は部分列が全て だったときに, になります.

論理積の性質より，これ以上部分列の最大値が大きくなることはありません．

より だから, は 未満です．
また， and であれば, は のビットが1であることがわかります．

したがって，部分和の集合が大きいビットを個持っていれば，それ以外を除外する．

という操作を まで繰り返し，最後に残った数が共通で持っているビットの和が答えです．

コード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

/* 解答ここから！ */

int main() {
  ll n, k;
  cin >> n >> k;

  vector<ll> a(n), sum(n+1, 0);
  rep(i,n) {
    cin >> a[i];
    sum[i+1] = sum[i] + a[i]; // 累積和を作る
  }

  vector<ll> num;
  /* 累積和から部分列の和を計算 */
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      ll tmp = sum[j] - sum[i-1];
      num.pb(tmp);
    }
  }

  vector<ll> pw;
  ll tt = 1;
  /* 2の累乗を計算(オーバーフローに注意) */
  for (int i = 1; i <= 40; ++i) {
    pw.pb(tt);
    tt *= 2;
  }

  ll res = 0;
  /* 2^40 から調べていく */
  for (int i = 39; i >= 0; --i) {
    ll cnt = 0, target = pw[i];
    vector<ll> tmp;
    for (auto itr : num) {
      /* 対象のビットが立っていれば, 部分列の和との論理積はそのビットが持つ重みになるはず */
      if ((itr & target) == target) {
        cnt++;
        tmp.pb(itr);
      }
    }
　/* 部分列の和がk個以上あればそれ以外を除外 */
    if (cnt >= k) {
      num = tmp; // これできるんだね(メモリとかどうなってるんだろ)
      res += target;
    }
  }

  cout << res << endl;
}

Submission #3683421 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選