Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選:B - Sum AND Subarrays(400)

問題

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b

制約

  • 2 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9
  • \displaystyle 1 \leq K \leq \frac{N(N+1)}{2}

考え方

まず部分列のすべての和を O(N^2) で求めておく。bitの最大値は最上位ビットから貪欲に決めていけば良い。 i ビット目について k つ以上の数が存在するとき、i ビット目が 1 である数のみが解の候補の対象になる。そうして 0 ビット目まで確認して残っている数のうち、k つの論理積をとった数が解になる。

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

どこに着目して考察するべきだったか

上位ビットから順に貪欲に決めていく。

何がバグっていたか

計算量の見積もりが甘かった。以下のような実装でも間に合うと思っていた。かなり無駄な実装になっている...orz

           List<Long>[] g = new ArrayList[64];
            g = Stream.generate(ArrayList::new).limit(64).toArray(List[]::new);
            int[] bit = new int[64];
            for (long l : set) {
                for (int i = 63; i >= 0; i--) {
                    if ((l >> i & 1) == 1) {
                        bit[i]++;
                        g[i].add(l);
                    }
                }
            }
 
            List<Long> list = new ArrayList<>();
            int idx = 63;
            for (int i = idx; i >= 0; i--) {
                if (bit[i] >= k) {
                    list = new ArrayList<>(g[i]);
                    break;
                }
            }

こんな感じで上から i ビット目で k つ以上の数が存在する時はループから抜けるべきであった。

               bit = new int[m];
                g = Stream.generate(ArrayList::new).limit(m).toArray(List[]::new);
                for (int i = idx; i >= 0; i--) {
                    for (long l : list) {
                        if ((l >> i & 1) == 1) {
                            bit[i]++;
                            g[i].add(l);
                        }
                    }
                    if (g[i].size() >= k) {
                        list = new ArrayList<>(g[i]);
                        break;
                    }
                }

得た知見

計算量がギリギリのときは、雑な実装にしない(?)

類題

D - IntegerotS