2021年8月20日に開催された AtCoder Beginner Contest 215（ABC215） に参加しました。

AtCoder Beginner Contest 215 – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は
・結果: 4完（A,B,C,D） 0WA
・順位: 1857 / 8537
・パフォーマンス: 1162
・レーティング: 652 → 715
でした。

B問題について

問題等は以下のリンクよりご確認ください。

B – log2(N)

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

まずは計算量の予測について。

\(N\)の最大値は\(N^{18}\)で、\(2^{60}\)より小さいです(\(2\)進数にしたときの桁数の見積もりについては【2のn乗をざっくりと把握する】にメモしています)。

すなわち、\(0 \leq k \leq 60\)と少ないので全部試すことができます。

今回はコンテストでは以下のコードを提出しACしました。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll, ll>;
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  ll N;
  cin >> N;

  ll ans = 0;
  ll current = 2;
  while (current <= N) {
    current *= 2;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

B問題をbit演算でACする

解説ではbit演算を利用した解法が紹介されていました。

bit演算の復習を兼ねてbit演算を使ってACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll, ll>;
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  ll N;
  cin >> N;

  ll K = 0;
  while ((1LL << K) <= N) {
    K++;
  }
  cout << K - 1 << endl;
  return 0;
}