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

問題

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

制約

• 
• 
• 

考え方

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

Submission #4144232 - 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;
                }
            }

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

               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