先週の土曜日にAtCoderのコンテストに参加した感想
AtCoder Beginner Contest
先週の土曜日にAtCoderのプログラミングコンテストに参加しました。前回も参加したんですが、Dクラスの問題は解くことができませんでした。
今回もCクラスの問題までしか解けなかったんですが、時間があればDクラスの問題も解けたと思います。
D - Binomial Coefficients
今回のDクラスの問題は二項係数に関する問題でした。二項係数は組み合わせやを展開したときの係数で使うことがあると思います。実際に二項係数は、 と表すことができるので、階乗のプログラムを作ることができれば、求めることができます。
しかし、この問題では二項係数を求めずに解くことができます。二項係数といえばパスカルの三角形を思い出すことができます。パスカルの三角形を観察すると、二項係数の最大値はが奇数のときはまたはになり、が偶数のときは、になります。
問題はint型ではなくlong型で数値を扱う必要がありました。int型よりも巨大な数値が入力されると思うので、long型にすべきでした。 今度は時間内にDクラスの問題を解けるように頑張りたいです。