B - log2(N) Editorial by physics0523


この問題には様々な解法があります。今回はいくつかの解法を説明していくので、コンテスト中に正解できた方も是非他の解法を検討してみてください。
なお、この解説での実装例は全て C++ で示します。予めご了承ください。

  1. 基本的な解法
  2. 対数を利用した解法と数値誤差
  3. 整数の bit表現 を利用した解法

1. 基本的な解法

まず、 \(k\) を大きくしていくごとに、明らかに \(2^k\) は大きくなっていきます。このことから、ある整数 \(k\) までは \(2^k \le N\) が成立し、その値より大きな \(k\) については \(2^k>N\) となることが分かります。
これより、 \(k\) の値を \(1\) ずつ大きくしていくループを書くことによって、答えを求めることができます。
なお、 \(k\) を大きくしていくループの中で \(2^k\) を要領よく求めていくことで、計算量を抑えることができます。

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  long long val=1;
  for(long long i=0;i<=60;i++){
    if(val>n){
      cout << i-1 << '\n';
      break;
    }
    val*=2;
  }
  return 0;
}

2. 対数を利用した解法と数値誤差

\(2^k \le N\) を対数を使って変形すると、 \(k \le \log_2(N)\) と変形できます。よって、 \(\log_2(N)\) の小数点以下を切り捨てて整数として出力しても正解できるはずです。
しかし、以下のコードは WA となってしまいます。

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  cout << floor(log2(n)) << '\n';
  return 0;
}

不正解となる原因は精度不足です。具体的には以下のケース(\(N=2^{59}-1\))で精度不足を起こします。(WA: 59, AC: 58)

576460752303423487

誤差を回避する方法として、 \(64\)bit 浮動小数点型よりも精度の高い型を用いるという方法があります。先ほどのコードを以下のように修正すると、この問題に正解することができます。

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  cout << floor(log2((long double)n)) << '\n';
  return 0;
}

しかし、精度が高い型であるからといって、万能であるわけではありません。もしこの問題の制約が \(N \le 2 \times 10^{18}\) であれば、以下のテストケースについて修正した後のコードでも不正解となります。(WA:60, AC:59)

1152921504606846975

競技プログラミングにおいて、整数性のある問題に対して整数性を外して実数で処理することには危険が伴います。整数性のある問題はなるだけ整数型で処理することをおすすめしますが、どうしても実数型が必要な際は注意して取り扱いましょう。

3. 整数の bit表現 を利用した解法

整数を \(2\) 進数で表現することを考えましょう。
例えば \(6=110_{(2)}, 15=1111_{(2)}\) というように変換できます。
ここで、 \(2^{k} \le N < 2^{k+1}\) という不等式は、 \(2\) 進数で以下のように変換できます。
\(1 \underbrace{ 00 \dots 0 }_{ k }\ _{(2)} \le N < 1 \underbrace{ 00 \dots 0 }_{ k+1 }\ _{(2)}\)
これを利用して、以下のような解法を導くことができます。

  • \(N\) を(先頭に \(0\) をつけずに) \(2\) 進数に変換したときに、 \(N\)\(k\) 桁となる(すなわち、 \(N\)\(2\) 進数に変換したときに最も上の位にくる \(1\) が下から数えて \(k\) 桁目に存在する)なら、答えは \(k-1\) である。

この解法の実装の方針は色々と存在しますが、 bit 演算を利用すると楽に実装できます。(ただし、一番下の位を \(0\) 桁目と取り扱うことに注意してください。)

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  for(int i=60;i>=0;i--){
    if(n&(1ll<<i)){cout << i << '\n';break;}
  }
  return 0;
}

posted:
last update: