AtCoderログ：0020 - ABC 068 B

問題

問題文

高橋君は $2$ で割れる数が好きです。
正整数 $N$ が与えられるので、$1$ 以上 $N$ 以下の整数のうち、最も $2$ で割れる回数が多いものを求めてください。答えは必ず $1$ つに定まります。
なお、$2$ で割っていき、何回あまりが出ずに割れるかを、$2$ で割れる回数と呼ぶことにします。
例えば
・$6$ ならば、$6$ -> $3$ で、$1$ 回 $2$ で割れます。
・$8$ ならば、$8$ -> $4$ -> $2$ -> $1$ で、$3$ 回 $2$ で割れます。
・$3$ ならば、$0$ 回 $2$ で割れます。

制約

・$1 \le N \le 100$

収録されている問題セット

• AtCoder に登録したら次にやること [第03問類題]

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #011

回答1 (AC)

整数 $n$ を受け取った後、変数 $i$ を $1$ から $n$ まで変化させ、$i$ が $2$ で割り切れる回数 division を求める、最終的にその最大値を出力するようにしました。$2$ で割り切れる回数の最大値 dmax とそれを実現する整数値を imax に保持しています。コードは以下のようになりました。

abc068b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  int dmax = -1, imax = 1;
  for ( int i=1; i<=n; i++ ) {
    int m = i, division = 0;
    while ( m%2==0 ) {
      division += 1;
      m        /= 2;
    }
    if ( division>dmax ) {
      dmax = division;
      imax = i;
    }
  }

  cout << imax << endl;
}

回答2 (AC)

$2$ で割り切れる回数が $0$ 回の整数は奇数です。$2$ で割り切れる回数がちょうど $1$ 回である整数は、$2$ で割り切れるが $4~(=2^2)$ では割り切れない整数です。$2$ で割り切れる回数がちょうど $2$ 回である整数は、$4~(=2^2)$ で割り切れるが、$8~(=2^3)$ では割り切れない整数です。
この問題で与えられる整数 $N$ に対し、$2^m \le N < 2^{m+1}$ となる $m$ が見つかったとすると、$1$ 以上 $N$ 以下の整数のうち $2$ で割り切れる回数が最も多い整数は $2^m$ となります。つまりこの問題は、上記のような整数 $m$ を求めれば良いことがわかります。ここで $m$ は $m=\lfloor \log_2{N} \rfloor$ と表せるので、コードは以下のようになりました。

abc068b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  cout << pow(2,floor(log2(n))) << endl;
}

調べたこと

AtCoder の解説 → ユーザの解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答2と同じ方針でした。

学んだこと

• C++の標準ライブラリ (log2, floor, pow)

リンク

• 前の記事 → AtCoderログ：0019 - ABC 082 B
• 次の記事 → AtCoderログ：0021 - ABC 210 に参加しました