問題
問題文
空の箱があります。
髙橋君は以下の $2$ 種類の魔法を好きな順番で好きな回数使えます。
・魔法 A ：箱の中にボールを $1$ つ増やす
・魔法 B ：箱の中のボールの数を $2$ 倍にする
合計 $120$ 回以内の魔法で、箱の中のボールの数をちょうど $N$ 個にする方法を $1$ つ教えてください。なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。
魔法以外の方法でボールの数を変化させることはできません。
制約
・$1 \le N \le 10^{18}$
・入力は全て整数
回答
回答1 (AC)
魔法の操作が例えば ABABBA の場合、箱の中のボールの数は 0 → 1 → 2 → 3 → 6 → 12 → 13 と変化しますが、これを２進表現で記すと 0 → 1 → 10 → 11 → 110 → 1100 → 1101 となり、数字の並びと文字の並び (最初の A だけ 1, 残りは BAS=1, B=0 とみなす) が対応していることがわかります。そこで $N$ の２進展開求め、1 と 0 の並びから魔法を決めていけば良いでしょう。コードは以下のようになりました。
abc216c-1.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int64_t n;
cin >> n;
vector<int> d;
while ( n>0 ) {
d.push_back(n%2);
n /= 2;
}
cout << "A";
for ( int i=(int)d.size()-2; i>=0; i-- ) {
cout << "B";
if ( d.at(i)==1 ) {
cout << "A";
}
}
}
$N$ が $n$ ビットの時、このコードは $n$ 個の A と最大 $n-1$ 個の B を出力します。$N$ の最大値 $10^{18}$ は60ビットなので、このコードが出力する文字の個数は最大119個であり、「120個以内」という条件をギリギリクリヤしていることがわかります。
調べたこと
AtCoder の解説 → 公式解説
回答1と同じ方針です。
AtCoder の解説 → 公式解説
２進展開を逆から使用する解法でした。
AtCoder の解説 → ユーザ解説
２進展開を逆から使用する解法でした。