【AtCoder】【C#】AtCoder Beginner Contest 169 - B - Multiplication 2
ABC169 のB問題の反省です
本記事のテーマ
ABC169で解けなかった問題の振り返りです。今回はB問題についてです。
コンテストへのリンク
B問題
問題概要
- N個の整数がA_1,...A_Nが与えられる
- A_1 x ... x A_N を求めよ
- 計算結果が 1018 を超えるときは-1を出力せよ
ポイント
下記に記載されているC#の整数数値型では、for文でN回掛け算しようとするとオーバーフローしてしまうケースが存在する。なので、計算→判定の順番にすると正確に計算できない。
解法
Biginteger構造体を使用する。
BigInteger 型は、理論上の値が上限または下限を持たない、任意の大きい整数を表す不変の型です。
なので、このようにオーバーフローを考慮する場合は今までlong
とかで書いていた部分をBigintegerに変更します。ちなみに、Bigintegerを使用するときはusing System.Numerics
を忘れないようにしてください。
var N = BigInteger.Parse(Console.ReadLine()); var A = Console.ReadLine().Split().Select(BigInteger.Parse).ToArray(); if (A.Contains(0)) { Console.WriteLine(0); return; } BigInteger res = 1; for (int i = 0; i < N; i++) { res = res * A[i]; if (1000000000000000000 < res) { Console.WriteLine(-1); return; } } Console.WriteLine(res);
反省
除算を使用した求め方もあるそうなので、AtCoderの公式回答を確認してみると良いかと思います。