yukicoder No.741 AscNumber(Easy)
問題
https://yukicoder.me/problems/no/741
10進数表示をしたときに桁が昇順に並んでいる数字を AscNumber とする。
10N 未満の AscNumber がいくつあるか求めよ。
考え方
[0, 9] の数字から重複を許して N 個選んだ時の数を昇順に並べると1つの AscNumber になる。全単射の関係になっており、よって AscNumber の数の個数は、 [0, 9] の数字から重複を許して N 個選ぶ場合の数と同じである。
よって が解になる。
ポイント
- 対応で数える
類題
雑記
桁DPでも解けますが、再帰で呼び出すと Stack Overflow になります。