AOJ 1456 The Sparsest Number in Between (ICPC アジア 2024 B)

これ面白かった！　ABC-E で出題されて水色 Diff などがあり得そうな雰囲気。

• 問題へのリンク（仮）

問題概要

正の整数 が与えられる。

以上 以下の整数のうち、popcount が最小のものを求めよ。複数ある場合は、そのうちの最小の整数を求めよ。

制約

• 

考えたこと

まず最初に考えたことは、もし 以上 以下の整数であって、2 の冪乗であるものが存在したら、その popcount は 1 であり、 最小を達成するということだ。

そして、 以上 以下の整数であって、2 の冪乗であるものが存在するということは、 を二進法で表したときの桁数が異なるということでもある。たとえば、二進法で表した時に 、 のように桁数が異なるとき、 と順に見ていって桁数が上がる瞬間（この場合は ）に、2 の冪乗になっているのだ。

よって、 以上 以下の整数であって、2 の冪乗であるものが存在しないのは、二進法で表したときの の桁数が等しい場合だと言える。

ここまで考えると、 を二進法で表して考えると良いと考えられる。

二進法で考える

以降、 を二進法で表すことにする。 を左から見ていったとき、共通の部分は無視してもよい。たとえば、

• 
• 

としよう。このとき、左から最初の "101" は共通している。 以上 以下の整数はすべて、左から 3 桁が "101" であることに変わりない。よって、これを除外して考えて、あとから "101" を付け足すことにしよう。

そうすると、

• 
• 

についての問題になる。このとき、最上位の桁の値が、 の方は 0 で の方は 1 であることに注意しよう。

の最上位が 0 で の最上位が 1 の場合

こうして問題は、 の最上位が 0 で の最上位が 1 であるような問題に帰着された。まず のときは、答えは 0 なので、 としよう。

このとき、先の考察によって、popcount が最小であるものは、最上位が 1 で残りが 0 であるものだとわかる。ただし、これが popcount 最小であるもののうちの最小とは限らない。実際、上の例

• 
• 

において、答えは

となる。具体的には、 の最左の桁を として が答えとなる。

コード

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

int main() {
    long long a, b, res = 0;
    cin >> a >> b;

    for (int d = 61; d >= 0; d--) {
        bool a_flag = (a >> d) & 1;
        bool b_flag = (b >> d) & 1;

        if (a_flag && b_flag) {
            res += 1LL<<d;
            a -= 1LL<<d, b -= 1LL<<d;
        } else if (b_flag) {
            if (__builtin_popcountll(a) <= 1) res += a;
            else {
                int k = d;
                while (k >= 0 && !((a >> k) & 1)) k--;
                res += 1LL<<(k+1);
            }
            break;
        }
    }
    cout << res << endl;
}