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: