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

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

環境&対象

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

  • macOS Big Sur 11.3
  • Xcode 12.5

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

overflow が天敵

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

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

特に 順列組み合わせ

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

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

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

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

回避策

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

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

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

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

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

組み合わせ計算ではオーバーフローに気をつける
  • 階乗計算は(思うよりも)オーバーフローになりやすい
  • 漸化式等を使った計算で計算途中の数値の大きさを抑える

AtCoder にチャレンジするなら

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

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です