前回の続きです。
前回は001 Yokan Party（★4）が難しそうで002 Encyclopedia of Parentheses（★3）をやってみたのですが、もっと簡単そうな★2のものもあったので★2からやってみることにしました。
004 Cross Sum（★2）
内容は簡単そうだけどそんなに簡単なわけがないから何かあるんだろう…と思っていましたが、単純に作るとTLE（計算時間オーバー）になる問題でした。
競技プログラミングでは、計算時間や消費メモリ容量が定められており、その中で処理できるプログラムを作るということがポイントのようです。
010 Score Sum Queries（★2）
これも004と同様に単純に作るとTLEになってしまうため、工夫が必要でした。
022 Cubic Cake（★2）
これはTLEにはならなかったのですが、Pythonの場合、大きな数字の扱いに苦労しました。
Python勉強中のため良く知らないということもありますが、調べてみたところPythonのintには上限がないようなので、ヒントの
オーバーフローに注意してください。
https://atcoder.jp/contests/typical90/tasks/typical90_v
は問題なかったのですが…
問題はPythonで大きな数の割り算を行うと、
999999999999999998/1 ⇒ 1000000000000000000
となってしうことでした。これを
999999999999999998//1 ⇒ 999999999999999998
と記述すれば良いことに気づくのに時間がかかりました。
Pythonの場合、int/intの計算をするとfloatになり、更にintは最大値がなく誤差もないのですが、floatだと誤差が発生するため、このような計算結果になってしまったようです。
int/intはintになると思っていたのですが、Pythonは違うようで、ここに引っかかってしまいました…
参考：Python3で巨大な浮動小数計算の結果が変だったので理由を調べてみた
コメント