AtCoder Beginner Contest 169 B-Multiplicationの振り返り

愚直に実装した場合に起きる問題

　・Python：オーバーフローは起こらないが、計算量O(N^2)でTLEになってしまう。

　・C++：計算量は大丈夫だが、オーバーフローにより誤った計算結果になる。

＊オーバーフロー（桁あふれ）とは？？
 数値型の変数について、己が持てる最大値を超えること。
これが起きるとぐちゃぐちゃな数字が変数に入ってしまうため、正しい数値が得られなくなる。
（例）A1～A3に10^9が入っている場合、A1×A2の段階では10^18でlong long型にギリギリ間に合う。しかし、A3がここに掛け算されるとオーバーフローし想定外の数値が入る。この後に10^18との間で大小比較を行っても、正しい結果が得られない。

　【オーバーフローへの対処法】

①Pythonなどオーバーフローの心配がない言語で書く
②int 128型に変換する

正解のために求められる能力

　・Pythonの場合：　TLEへの対処力（正しい順序で判断処理を行い計算量を減らす）

　・C++の場合：　オーバーフローへの対処力 or 正しい順序で判断処理を行う力

入力値に０が含まれる場合に、正しい処理方法を実装できるかが勝利を分けた模様（なみだ）

解答例１（この順番で行うのが重要！）

①入力全読み込み　→　②Aに0が含まれるか判断　→　③順番に掛け算を行い、積が10^18を超えるか判断

・②がなかったら・・・「Aに0を含んでいるケースで、誤った出力結果をしてしまう」

（例）A1とA2に10^18、A3に0が入っていた場合を考えてみる！このとき、A1×A2×A3は0になるはず。
しかし③のみで判断していると、A1×A2の段階で10^18を超えたことにより-1を出力してしまう結果に。

解答例２（よりスマートに見える）：

①入力全読み込み　→　②Aを小さい順に並び替え　→　③順番に掛け算を行い、積が10^18を超えるか判断

まとめ　

・今回のPythonでTLEが発生した理由は、普通に掛け算していくと計算結果は最大10^50000まで取りうるため計算量がO(N^2)になるから。

・そこで計算量を減らすための工夫が必要になるが、以下の２通りが多くみられる。

【方法１】
①入力値のいずれかに０があるかを判断し、あれば０を出力してプログラムを終了
②順番に掛け算し、10^18を超えているかを逐次判断。超えたら-1出力しプログラム終了

【方法２】
①入力値を小さい順にソートする
②順番に掛け算し、10^18を超えているかを逐次判断。超えたら-1出力しプログラム終了

・入力値のいずれかに０を含む場合は、他の入力値がどんなに大きかったとしても計算結果は０になることを想像できたかがカギでした。むずかしかった泣いちゃうほぼ泣いた