Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 263 C問題 Monotonically Increasing

AtCoder ABC ABC263 C問題 300 pts

問題

提出解答 1

提出解答 2

問題の概要

全ての要素が $1$ 以上 $M$ 以下であるような長さ $N$ の狭義単調増加な整数列を求めよ.

制約

$1 \leq N \leq M \leq 10$

解法1

次のアルゴリズムによって正解できる.

整数列のキュー $Q$ を $Q=( (1), (2), \dots, (M) )$ とする.
以下の操作をが空出ない限り繰り返し続ける.
- $Q$ から先頭にある列 $A$ を取り出す.
- $A$ の長さが $N$ ならば $q$ を出力する .
- の長さが未満ならば, の真っ向をとして, の順に以下を行う.
  - $A$ の末尾に $k$ を追加した列を $B$ としたとき, $B$ を $Q$ の末尾に追加する.

ここで, 条件を見たす整数列の個数は $\dbinom{M}{N}$ 個であり, 最大でも $\binom{10}{5}=252$ であるから十分高速である.

解法2

python では itertool 内にある combinations を利用すれば一発である.