yukicoder No.47 ポケットを叩くとビスケットが２倍 解説

問題文

解説

まず、仮に$N=5$だった時を考える。
すると、答えは1→2→4→5となるだろう。
また、$N=19$だった時を考える。
すると、答えは1→2→4→8→16→19
まず、これを見てクッキーは全部2倍にすると最適になるとわかるだろう。
そして、No.46同様追い越しても作り出した分に関しては考えなくて大丈夫なシステム。よってあり得る答えをどんどん2倍してNより大きいかの判定をすればOK。
一応実行時間を計算すると$O(logN)$。当然余裕。
解説では、書きやすさのため左シフト演算というものを使っている。
$x<<y$とかくと、$x*2^y$という意味になる。
よって$x$を1にすれば$2^y$が計算できるというわけだ。

C++での解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;cin>>n;
  for(int i=0;;i++)
    if((1<<i)>=n){
      cout<<i<<endl;
      return 0;
    }
}