【競プロ精進ログ】ABC169-B

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC169-B「Multiplication 2」です。

ポイント

オーバーフロー対策をする問題でした。pythonでは多倍長整数がデフォルトで利用できるため，特に気をつける必要はないかもしれません。一方で，c++ではオーバーフローが起こりうる処理の前で「除算を使ったオーバーフロー判定」を行います。例えば，$A\times B$が$X$を超えるかどうかを判定したいときは，以下のようにして判定を行います。

除算を使うことで，実際にオーバーフローが起こりうる$A\times B$の演算を行わずしてオーバーフロー判定を行うことができます。

今回の問題で引っかかるポイントは，オーバーフローを起こしてから0が現れるパターンです。何も考えずに，乗算結果が$10^{18}$を超えたら-1 を出力するという条件分岐をしてしまうと，本来結果は0であるはずなのに答えは-1になってしまいます。

そこで，今回は数列を扱う基本であるソートを利用します。そうすることで，もし数列の中に0があれば数列の要素の最初は0になります。そうすることで，もし答えが0であればすぐに答えを出力するようにできます。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N;
ll A[110000];

int main(){
  cin >> N;
  rep(i, N) cin >> A[i];
  // ソートしておｋ
  sort(A, A + N);
  // もし最初の要素が0であれば乗算の結果として0を出力してreturnしてしまう
  if (A[0] == 0){
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1;
  rep(i, N){
    // 除算を利用したオーバーフロー判定
    if (A[i] > 1000000000000000000 / ans){
      cout << -1 << endl;
      return 0;
    }
    ans *= A[i];
  }
  cout << ans << endl;
}