山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

先週の土曜日にAtCoderのコンテストに参加した感想

AtCoder Beginner Contest

先週の土曜日にAtCoderプログラミングコンテストに参加しました。前回も参加したんですが、Dクラスの問題は解くことができませんでした。

今回もCクラスの問題までしか解けなかったんですが、時間があればDクラスの問題も解けたと思います。

D - Binomial Coefficients

D - Binomial Coefficients

今回のDクラスの問題は二項係数に関する問題でした。二項係数は組み合わせや (a + b)^{n}を展開したときの係数で使うことがあると思います。実際に二項係数は、  {}_{n} \mathrm{C}_{k} = \dfrac{n!}{k!(n-k)!} と表すことができるので、階乗のプログラムを作ることができれば、求めることができます。

しかし、この問題では二項係数を求めずに解くことができます。二項係数といえばパスカルの三角形を思い出すことができます。パスカルの三角形を観察すると、二項係数の最大値は nが奇数のときは k= \lfloor \dfrac{n}{2}\rfloor + 1または k= \lfloor \dfrac{n}{2}\rfloor + 2になり、 nが偶数のときは、 k = \dfrac{n}{2}になります。

問題はint型ではなくlong型で数値を扱う必要がありました。int型よりも巨大な数値が入力されると思うので、long型にすべきでした。 今度は時間内にDクラスの問題を解けるように頑張りたいです。