たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】AtCoder Beginner Contest 169 - B - Multiplication 2

f:id:c_taquna:20200115005201p:plain

ABC169 のB問題の反省です

本記事のテーマ

ABC169で解けなかった問題の振り返りです。今回はB問題についてです。

コンテストへのリンク

atcoder.jp

B問題

問題概要

  • N個の整数がA_1,...A_Nが与えられる
  • A_1 x ... x A_N を求めよ
  • 計算結果が 1018 を超えるときは-1を出力せよ

ポイント

下記に記載されているC#の整数数値型では、for文でN回掛け算しようとするとオーバーフローしてしまうケースが存在する。なので、計算→判定の順番にすると正確に計算できない。

docs.microsoft.com

解法

Biginteger構造体を使用する。

docs.microsoft.com

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の公式回答を確認してみると良いかと思います。