けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

SoundHound 2018 本戦 A - Feel the Beat (300 点)

区間 AtCoder unrated公式コン AtCoder300点

区間の重なりを求める処理、結構久しぶりなん。

問題へのリンク

問題概要

2 で何回か割ると 140 以上 170 未満になる正の整数を「よい数」と呼ぶ。

C 以上 D 未満の整数のうち「よい数」は何個あるか求めよ。

制約

  • 140 \le C < D \le 10^{15}

考えたこと

まともにカウントすると間に合わない。

  • [140, 170) と [C, D) との交わりの長さ
  • [280, 340) と [C, D) との交わりの長さ
  • [560, 680) と [C, D) との交わりの長さ
  • ...

をすればよい。区間の交わりを求める問題は典型で

[a, b) と [p, q) の交わりは、交わるなら [max(a, p), min(b, q)) になる (これらの大小関係を見て、逆なら交わらない)

という感じになるのでこれを利用するなり。計算量は O(\log{D})。

#include <iostream>
using namespace std;

long long C, D;
int main() {
  cin >> C >> D;
  long long res = 0;
  long long left = 140, right = 170;
  for (int i = 0; i < 60; ++i) {
    long long tmp = min(D, right) - max(C, left);
    if (tmp > 0) res += tmp;
    left *= 2, right *= 2;
    if (left > 1000000000000000LL) break;
  }
  cout << res << endl;
}