Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【第5回 ドワンゴからの挑戦状 予選 B Sum AND Subarrays】本当に400点なのか?

XORを扱う問題は多いけどANDを扱う問題は少ない。大変良く出来た問題だと思ったのでまとめ。

B - Sum AND Subarrays

問題

長さNの数列が与えられる。(N=103)

この数列のうち、範囲[l,r]の和はN(N-1)/2個あるが、この中からK個選び、ANDをとりたい。その時の最大値はいくつか?

方針

Nが小さいのと、XORならいざしらずANDなので、もとの組成には意味なしと考えて、とりあえず累積和を使ってN(N-1)/2個を全列挙。Aiとする。

その中で大きい順は明らかに間違いだが、大きいやつを一つとって、そいつと他のやつらとのANDをとり、大きい順にK個とれば答えっぽいものは求まるのでは?とサンプルは通したが本番テストケースでほぼ全滅。

正しい方針は、「そのK個のANDは、定義どおり共通するビット」だから「答えとなる数値xは、Ai&x=xとなるやつが少なくともK個ある」と言い換える。(問題の言い換え)

しかしそのまま全探索することは出来ないから、上位のビットから貪欲に検査していくという方針をとる。例えば、すごく大きな1000...とANDをとれるものがK個あるならば、明らかに答えは1000...以上であり、0111...などはもはや調べる意味がない。このような方針で、上位からビットを決めていく。大体40桁くらいであり、一回の検査でO(N2)だから間に合う。(実装の工夫)

実装

fn solve() {
    input!{
        N:usize,K:usize,
        a:[i64;N],
    }
    let mut cumsum=cumsum1(&a);
    let mut cand=vec![];
    for i in 0..N {
        for j in 0..N {
            if j>i {
                cand.push(cumsum[j+1]-cumsum[i]);
            }
        }
    }

    let mut ans = 0;
    for i in (0..40).rev() {
        let n = ans + (1<<i);
        let mut k=0;
        for &c in &cand {
            if c&n==n {
                k+=1;
            }
        }
        if k>=K {
            ans += (1<<i);
        }
    }
    println!("{}",ans);
}

考察

400埋めで出てきたけど、ABCの400とは単位が違うのか?