Single Round Match 416 Div1 Easy

後で書く

問題は「与えられた整数Nと2進数表記で立っている1の数が同じで、かつNより大きな最も小さい整数を答えなさい」というもの。まず1000とか1111とかのことを漠然と考えて「1000の時は10000と2倍になるから+1しながら探すとタイムアウトするなぁ」と思う。次に「1111の次は11110かと思いきや10111だなぁ。簡単じゃないなぁ」と凹む。

しばらく漫然と考えてすっきりしないので規則性を理解するまで書き出してみる

ふむふむ。要するに「一番低い位置にある01の並びを見つけて10に変える」「変えた位置より下の桁はどんなならびになっていてもNより大きいので、000111と下の桁に1を集める」ということを理解。

最初Nにいくつ1が立っているか計算したけどそれって必要なかった。

class NextNumber {
public:
  vector<int> vecize(int N){
    vector<int> buf;
    while(N){
      buf += N % 2;
      N /= 2;
    }
    return buf;
  }
  int getNextNumber(int N) {
    vector<int> input = vecize(N);
    size_t KETA = input.size();
    input += 0;
    int diff = 0;
    for(size_t i=0; i<KETA; i++){
      if(input[i] == 1 && input[i + 1] == 0){
	diff = 1ULL << i;
	break;
      }
    }
    int LOW = N & (diff - 1ULL);
    vector<int> lower = vecize(LOW);
    int wlow = accumulate(lower.begin(), lower.end(), 0);
    return N + diff - LOW + (1ULL << wlow) - 1;
  }
...

そしてレーティングは7ポイント下がってしまった。厳しい。Easy問題はささっと解けなきゃ先に進めないなぁ。22分で解いたんだがそれじゃ遅すぎるそうな。