B - Practical Computing Editorial by m_99
解法
問題文の記述に従って \(a_{i,j}\) の値を求めていくことにします。
- 各 \(i\) \((0\leq i \leq N-1)\) について、\(A_i\) の長さは \(i+1\) である。
という記述より、各数列(プログラム上では配列)を適切なサイズにします。
記述に素直な書き方をするとこのようになるでしょう。
vector<vector<int>> a(N);
for(int i=0;i<N;i++){
a[i] = vector<int>(i+1);
}
あるいは、今回の問題では配列を \(N \times N\) サイズで作っても問題ないため、そのように作って一部だけ使うことにしても良いです。
vector a(N,vector<int>(N));
続いて、
各 \(i,j\) \((0\leq i \leq N-1, 0 \leq j \leq i)\) について、\(A_i\) の \(j+1\) 番目の値 \(a_{i,j}\) は次のように定められる。
- \(j=0\) または \(j=i\) の時、\(a_{i,j}=1\)
- それ以外の時、\(a_{i,j} = a_{i-1,j-1} + a_{i-1,j}\)
という記述に従って \(a_{i,j}\) の値を求めていきます。
「 \(j=0\) または \(j=i\) の時、\(a_{i,j}=1\) 」という部分に関しては、\(a_{i,j}\) を求める時にまず「\(j=0\) または \(j=i\) 」という条件を満たすかどうかを調べ、満たすならば \(a_{i,j}=1\) とすれば良いです。
「それ以外の時、\(a_{i,j} = a_{i-1,j-1} + a_{i-1,j}\) 」とありますが、これは \(a_{i,j}\) を求めるにあたって \(a_{i-1,j-1}\) と \(a_{i-1,j}\) を先に求める必要があるということを示唆しています. よって、\(i=0,1,\ldots\) の順に \(a_{i,j}\) を求めるようなループ文を書くと良いでしょう。 (なお、 \(i=0\) の場合は \(a_{i-1,j-1}\) 等が存在しませんが、\(i=0\) の場合の \(j\) として考えられるものは \(j=0\) のみなので \(j=0\) または \(j=i\) の時に該当し、問題ないことが確かめられます。)
実装例
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
vector a(N,vector<int>(N));
for(int i=0;i<N;i++){
a[i] = vector<int>(i+1);
}
for(int i=0;i<N;i++){
for(int j=0;j<i+1;j++){
if(j==0||j==i)a[i][j] = 1;
else{
a[i][j] = a[i-1][j-1] + a[i-1][j];
}
}
}
for(int i=0;i<N;i++){
for(int j=0;j<i+1;j++){
if(j!=0)cout<<' ';
cout<<a[i][j];
}
cout<<endl;
}
return 0;
}
余談
本問で問われている数の並びはパスカルの三角形と呼ばれるものです。\(a_{n,r}\) の値は \({}_nC_r\)、 すなわち \(n\) 個のうちから \(r\) 個選ぶ方法の個数に等しいことが知られています。
posted:
last update: