けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

最初、罠に引っかかった

問題へのリンク

問題概要

長さ  N の数列  a_{0}, \dots, a_{N-1} が与えられる。これらの連続する区間の総和を書き出していく ( \frac{N(N+1)}{2} 個ある)。

これらの中から  K 個選んで AND をとった値として考えられる最大値を求めよ。

制約

  •  1 \le N \le 1000

嘘貪欲

とりあえず  N \le 1000 なので、 \frac{N(N+1)}{2} 個の整数を選んでくることはできる。それらを改めて  s_{0}, s_{1}, \dots, s_{M} とする。

で、 K 個選ぶ方法を最適化するなんてのは、とりうる解法はそんなに多くない。なんらかの尺度で良い順に選ぶとか、そういう Greedy になることがほとんど (最近他のパターンとして Alien DP があるのを知った)

で、最初は「単純に  M 個の中から大きい順に  K 個でいいんじゃないかな」と思ってしまった。というのも、AND をとるというのは基本的に値がどんどん小さくなってしまう。なので、なるべく大きい数同士で AND をとるのがいいんじゃないかなと。

しかし、例外があった。 K = 3 s

  • 1000
  • 1001
  • 0111
  • 0110
  • 0101

とかの場合、大きい順にやると 0 になってしまう。でも、下 3 個を選べば 100 になる。

上の桁から辞書順 Greedy

この手の問題は二進数で考えるのが定石だった。上の桁から順番に 1 にできるかどうかを見ていく Greedy でよかった。

  • まず、 d = 60 とかにして、 d 桁目に 1 が立っているのが  K 個あったら、AND 和の  d 桁目も  1 にできるので、そうすることにする (そして  d 桁目が 1 でないものは捨てる)
  •  K 個未満だったら、 d 桁目を 1 にすることは諦めて、とくに捨てることはしない

という風にすればよい。そして捨てられずに残ったやつで、次は  d-1 桁目について同じことをして...という風にすれば OK。計算量は  O(N^{2}\log{S})

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<long long> a;

int main() {
    cin >> N >> K;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<long long> S(N+1, 0);
    for (int i = 0; i < N; ++i) S[i+1] = S[i] + a[i];
    
    vector<long long> v;
    for (int i = 0; i < N; ++i)
        for (int j = i+1; j <= N; ++j)
            v.push_back(S[j] - S[i]);

    long long res = 0;
    vector<bool> dame(v.size(), false);
    for (int d = 60; d >= 0; --d) {
        int num = 0;
        for (int i = 0; i < v.size(); ++i) {
            if (dame[i]) continue;
            if (v[i] & (1LL<<d)) ++num;
        }
        if (num >= K) {
                res += (1LL<<d);
                for (int i = 0; i < v.size(); ++i) {
                    if ( !(v[i] & (1LL<<d)) ) dame[i] = true;
                }
        }
    }
    cout << res << endl;
}