Kazun の競プロ記録

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

AtCoder Beginner Contest 254 B問題 Practical Computing

AtCoder ABC ABC254 B問題 200 pts

問題

提出解答

Submission #32204853 - AtCoder Beginner Contest 254

問題の概要

次で定義される2重添字数列 $a=(a_{i,j})~(i \geq 0, 0 \leq j \leq i)$ について, $0 \leq i \lt N, 0 \leq j \leq i$ についての $a_{i,j}$ を全て求めよ.

$j=0$ または $j=i$ のとき, $a_{i,j}=1$ .
$1 \leq j \lt i$ のとき, [tex: a_{i,j}=a_{i-1,j-1}+a_{i-1,j}}.

制約

$1 \leq N \leq 30$

解法

問題文に $a_{i,j}$ の求め方が書いているので, これをそのままプログラムに落とし込めば良い.

ここで, 以下のことに注意すること.

添字が2重なので, 第1要素と第2要素のうち, どっちが $i$ で, どっちが $j$ なのかを混同しないこと.
プログラミング言語によっては多次元配列ではない, ジャグ配列 (長さが異なる配列の配列) を認めていない場合がある.

なお, この問題の $a_{i,j}$ は二項係数 $\dbinom{i}{j}$ と一致する.