AtCoder Regular Contest 161 B問題 Exactly Three Bits
問題
提出解答
(※ C++ での提出) atcoder.jp
問題の概要
以下の正の整数
で以下を満たすものは存在するか? 存在するならばそのような整数のうちの最大値を求めよ.
を
進法表記したときに現れる
の個数がちょうど
である.
個のマルチテストケース
制約
解法
条件を満たす のうち, 最小の正の整数は
なので,
の範囲では存在しないとなる.
以降では とする.
を
以下の非負整数で,
進法表記したときに現れる
の個数がちょうど
であるような非負整数のうち, 最大であるようなものと定義する (存在しない場合は
).
このとき, 次のようにして場合分けすることによって, 帰納的に導くことができる.
の場合,
以下の正の整数は存在しないので,
である.
の場合,
を
以下を満たす整数として,
である.
が奇数のとき,
の位をどうするかで場合分けすることにより,
となる.
が偶数のとき,
の位をどうするかで場合分けすることにより,
となる.
これにより, 求めるべきは である. また,
に出てくる引数の候補は
個であるので,
を
時間で求めることができる.
これは 個のテストケースの下では, 高速な言語を使用することによって, 正解することができる.