Memo

Twitterに書くには長すぎることを書きます。Opinions are my own.

いろはちゃんコンテスト Day1 L - をあ ぷろぶれむ

問題: L - をあ ぷろぶれむ

  • 各 A_i から右側に区間を伸ばしていくと、ビットを新たに立て続けたものが黒板に書かれていくことになる。ここで、新たに立ったビットが0に戻ることはないため、 A_i の立っているビット数を B_i とすると、黒板に書かれる整数の候補は高々 \sum (61-B_{i}) しかない。そのため、黒板に書かれる整数を全てmapに入れても計算量は O(N \log N) となる。
  • 区間の左から順番に見て、現在見ている値 A_i を含む全区間 A_j | A_{j+1} | \ldots | A_i \ (1 \le j \le i) をmapに入れながら処理し続けていくことを考える。ここで、mapに入る整数の種類も上記と同様に考えると高々61種類しかないことがわかる。このことから、途中経過をmapに突っ込みながら探索しても間に合う。
map<ll, ll, greater<ll>> mp1;
unordered_map<ll, ll> mp2, mp3;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n, k; cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  rep(i, n) {
    mp2[0]++;
    for(auto& e: mp2) {
      ll p = e.first|a[i];
      mp3[p] += e.second;
      mp1[p] += e.second;
    }
    swap(mp2, mp3);
    mp3.clear();
  }

  for(auto& e: mp1) {
    k -= e.second;
    if (k <= 0) {
      cout << e.first << endl;
      return 0;
    }
  }
}

提出コード (715ms)

効率のよい全探索を書くと自然とこんなコードになる気がするが、計算量が O(N \log N) になっていることは非自明ではないだろうか。この記事でも最初は O(N^{2}) と書いていた。