Topcoder SRM 711 Div.1 Easy - ConsecutiveOnes

問題概要

整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。

  • 0 <= n < 250
  • k <= 50

解法

1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、場合分けする。(1) k個の1で埋めた箇所が、元のnでも全部1である場合→上位の桁同様、下位の桁もnと同じ数で埋める(こうしないとnを下回ってしまう) (2) そうでない場合→下位の桁は全部0で埋めてOK (こうしてもnを下回らない)

感想

地味にややこしく見えるがビット操作に慣れてきて結構簡潔に書けた

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

class ConsecutiveOnes {
public:
    ll get(ll n, int k) {
        ll ans = 1LL << 59;
        ll a = (1LL << k) - 1;
        
        for (int i = 0; i <= 60-k; ++i) {
            ll tmp = n | (a << i);
            if (tmp != n)
                for (int j = 0; j < i; ++j)
                    tmp &= ~(1LL << j);
            ans = min(ans, tmp);
        }

        return ans;
    }
};