naoya_t@hatenablog

いわゆるチラシノウラであります

〈LeetCode過去問〉[WeeklyContest 100 C] 898. Bitwise ORs of Subarrays

agwたんが

なおや氏なら2分で解きそうな問題、意外とよいやつあった
https://leetcode.com/problems/bitwise-ors-of-subarrays/

とか煽るので見てみた

(WeeklyContest 100 C)

2分では解けなかったけど割とすぐに方針が立った

  • ✗ 作れない数を列挙して2^30から引く?いや無理(多すぎる)
  • ✗ xorとandに分解するのとか、ビット反転させて考えたりとかも無理(計算量を落とせない)
  • ○ こういうのって多分bit毎に分けて何かやる
  • ○ 5万ってことはNlogNで解けるってことだよな、てことは各地点からのにぶたんに落とせるのか
  • ◎ ああなるほど、ORの値って高々30回しか変えられない

というわけで

  • ビットごとに出現回数の累積を取っておいて、
  • ある地点(5万箇所全部試す)から
  • 各ビット(高々30)について、k→k+1になるポイントをにぶたんして
    • (そういうポイントがないならそのビットは変わらない)
  • その地点から始まる部分列がとりうるORの値を1つずつ生成していく
    • ある地点からは高々1+30通りの数しかORで作れない
      • ので全部作ってsetに入れて数えて答える

→AC

// マクロいろいろ略

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        int L = A.size(), B = 1;

        int a_max = *max_element(ALL(A));
        for (int m=1,b=1; m<INT_MAX; m<<=1,++b) {
            if (a_max >= m) B=b;
            else break;
        }

        vvi acc(B, vi(L+1));
        rep(b,B) acc[b][0] = 0;
        rep(i,L){
            for(int b=0,m=1; b<B; ++b,m<<=1){
                if (A[i] & m) {
                    acc[b][i+1] = acc[b][i] + 1;
                } else {
                    acc[b][i+1] = acc[b][i];
                }
            }
        }

        set<int> possible_nums;
        for (int from=0; from<L; ++from) {
            int a0 = A[from];
            possible_nums.insert(a0);

            vector<ii> changes;
            for(int b=0,m=1; b<B; ++b,m<<=1){
                if (a0 & m) continue;
                int k = acc[b][1+from];
                auto it0 = acc[b].begin()+1+from;
                auto it = lower_bound(it0, acc[b].end(), k+1);
                if (it == acc[b].end()) continue; // not found
                int ix = (int)(it - it0);
                changes.emplace_back(ix, m);
            }
            sort(ALL(changes));
            int c = changes.size();
            rep(i, c) {
                int at=changes[i].first, m=changes[i].second;
                assert((a0 & m) == 0);
                a0 |= m;
                if (i == c-1 || changes[i+1].first > at) possible_nums.insert(a0);
            }
        }

        return possible_nums.size();
    }
};

おまけ

agwたんの図解ツイート