Official
A - AABCDDEFE Editorial by maspy
ヒント → https://atcoder.jp/contests/arc153/editorial/5482
[1] \(6\) つ組の問題への帰着
美しい整数の 10 進法表記は,問題タイトルのように 1 桁の数字 A,B,C,D,E,F を用いて AABCDDEFE と書けるものです.ただし A は 0
以外です.
さらに,整数 AABCDDEFE の大きさと,\(6\) つ組 (A,B,C,D,E,F) の辞書順は一致するので,本問は次の問題に帰着できます:
1 桁の数字からなる \(6\) つ組 (A,B,C,D,E,F) (ただし A は
0
ではない)のうちで,辞書順について小さい方から \(N\) 番目のものを求めよ.
[2] 解法 1
[1] のような \(6\) つ組は全部で \(9\times 10^5\) 通りしかなくて,時間内にすべて列挙することが可能です.そのあとで \(N\) 番目の要素を出力すればよいです.
[3] 解法 2
\(N\) 番目だけを直接得ることもできます.この際,\(6\) つ組 (A,B,C,D,E,F) をさらに \(6\) 桁の整数 ABCDEF に対応させて考えるとより簡潔に実装できます.
posted:
last update: