More than 5 years have passed since last update.

ABC169のB問題にnumpy.prod()を使うと不正解になった件

Posted at 2020-08-15

B問題 https://atcoder.jp/contests/abc169/tasks/abc169_b

この問題を読んで、全部掛け算する、sumの掛け算版の関数があれば一発でできると思い、調べるとnumpy.prod()がそれにあたるということで、使ってみたら、WAでした。

で、普通にfor文で掛け算してAC。大きい数の掛け算は遅くなるそうなので、範囲超えたらすぐbreakするようにしています。

numpy.prodについて調査した。

調査用のjupyter notebookはgistで公開

最後の2セルを比較すると、1~20までの総積までは同じで、21からnumpy.prod()がズレているのが分かる。

numpyはC言語やfortranで実装されているそうなので、64bitの整数の符号ありの最大値9223372036854775807 を 1~20の総積2432902008176640000 で割った値が約3.8であるので、21以降でズレるというのは違和感がない。

その後1~20の総積に4を掛けてもズレたので、最大値が9223372036854775807というのもおそらく正しい。

bitがどう変化して負になったりするのか調べたらもっと確実なことが言えそうですが、競プロ的には総積はpythonの組み込みだけで真面目にやりましょうって感じで終わりです。