ABC 401-500/ABC451D - Concat Power of 2 - 競技プログラミング用 知識集積所

---

問題

ABC451D

必要知識

B以下レベルの内容は省略

• 考察問題
• 深さ優先探索※

考え方

考察問題、というか、全部列挙して何個くらいになるかを上から見積もる数学問題。
問題は10^9「以下」という指定だが、10^9そのものがよい数ではないので、「未満」だと思っても問題ない。

同じ桁数の2の冪乗は最大4つしかない。
そこで、例えば002000103という9文字の文字列を

• 4桁のものの小さい方から2番目
• 2桁のものの小さい方から1番目
• 1桁のものの小さい方から3番目

をくっつけた7桁の数、すなわち2048164と解釈すると考える。
すると、10^9未満の良い数は、全て0から4までの数字を9個並べた文字列に割り当てられる。
よって、その個数は多くとも5^9≒195万個。
000000040のように対応する良い数が存在しない例や000000100と000000124のように同じ数に複数割り当てられることがあるため、実際の個数はそれよりもやや少なくなる。

ということで、全部列挙しても問題なさそうなので、

• とりあえず10^9未満の2の冪乗を全部列挙（30個）
• 深さ優先探索※などで10^9未満の良い数を全部作る
• ソートして、重複を削除する
• 指定された順番の数を答える

でよい。

解答例

解答例

注意点

別解