最初、罠に引っかかった

問題概要

長さ $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;
}

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

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

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

問題概要

制約

嘘貪欲

上の桁から辞書順 Greedy