[AtCoder] Swift を使って解く時に気をつけること（組み合わせ計算のオーバーフロー）

⌛️ < 1 min.

AtCoder の問題を解く時に気をつけること

Sponsor Link

環境＆対象

以下の環境で動作確認を行なっています。

おそらく、常識だと思いますが、明示的に言われないと気づきにくいと思うので、記事にしてみました。（ほとんど自分向けのメモです）

AtCoder では、扱う数字が Int32 に収まらない問題がたまにあります。

通常のアプリ開発では、オーバーフローすることがほとんどないので、気をつけてコードを書かないとハマります。

特に、順列・組み合わせの問題では計算方法に気をつけないと、overflow の嵐になります。

例えば、\(21!\) は、UInt64 に収まらない数字です。つまり、エラーになります。

問題としては、「２１文字の文字列を組み替えて出来上がる文字列について・・・」というのは、特に珍しく無い気がします。実際はもっと大きい数字をよく見ます。

このような時に、階乗を使用した \(_nC_i\) を計算しようとするとすぐに overflow になってしまいます。

もちろん、最終的に保持したい数字が UInt64.max を越えている場合は、対応が難しいです（が、そのような問題が出るとは思えません。）

大抵の場合は、\(nCi\) の場合のように(階乗となっている分子に対して、分母部分もあるケースであり)結果としての値は、より小さくなることが期待できるときがあります。

そのような時には、漸化式を利用した計算を使うことが必要となります。

つまり、\(\frac{n!}{(n-k)!k!} \) では計算せずに、\(_nC_k = _{n-1}C_{k-1} + _{n-1}C_k \) を使うということです。

組み合わせ計算ではオーバーフローに気をつける

以下の本が、定番本です。

リンク

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

Sponsor Link