前提・実現したいこと
以下に挙げるアルゴリズム問題の解き方(考え方)を教えていただきたいです。
※動的計画法を使用すると解けるそうです。
問題
1度しか使用されていない数字が1種類のみである3桁以上の正の整数を「Bナンバー」と定義します。
例:
116155 -> 1度しか使用されていない数字は「6」のみなので、Bナンバーです。
176155 -> 1度しか使用されていない数字は「6」と「7」の二つあるので、Bナンバーではありません。
166155 -> 1度しか使用されていない数字は一つもないので、Bナンバーではありません。
整数を0から昇順に数えた時、
1番目に登場するBナンバーは 「100」
2番目に登場するBナンバーは 「101」
3番目に登場するBナンバーは 「110」
となります。
問題:
3京(3 * (10 ^ 16))番目のBナンバーを求めてください。
補足情報
- 上記問題は3~5年前(曖昧です)に参加したどこかのCTFで出題されていた問題です。
出題元のサイトが見つけられなかったため、ここで質問させていただきました。
細部は異なるかもしれませんが問題の趣旨には誤りないはずです。
- 当時のサイトのヒントに「動的計画法を使用する」とあったため、アプローチとして動的計画法を使用するのは間違いないと思います。
※ほかのアプローチでもよいので解法がわかる方は回答いただけるとありがたいです。
- CTFの開催期間は1カ月程度だったはずなので、少なくともその期間以内に解が出せるアルゴリズムでの解法をご教示願います。
(自分が当時挑戦したときは試算した計算時間が年単位になってしまって諦めました…)
その他
- 解き方だけでなくコードも提示していただけるとさらにありがたいです。
- Python3のコードだとさらにさらにありがたいです。
- 上記の問題が出題されていたCTFの詳細についてご存じの方がいらっしゃいましたら併せて情報提供いただけると助かります。
以上、よろしくお願いいたします。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/06/19 15:00