AtCoder ABC169 B-Multiplication2 解説

問題文
\(N\)個の整数\(A_i、\dots、A_n\)が与えられます。
\(A_i \times\dots\times A_n\)を求めてください。
ただし、結果が\(10^{18}\)を超える場合は、’\(-1\)’を出力してください。

制約
・\(2 \le N \le 10^5\)
・\(0 \le A_i \le 10^{18}\)
・入力はすべて整数である。

問題文のまま\(N\)個の整数の積を計算してそれを\(10^{18}\)を比較するという実装をすると，long longでもオーバーフローしてしまって正しい答えを導けません．

そこで公式の解説にあるように実装しました．まずはソースコードから．

#include <iostream>
#include <vector>

int main() {
  int n; std::cin >> n;
  long long mx = 1e18; // 10^18
  long long m = 1;     // 積の値格納用
  std::vector<long long> a(n); // N個の整数読み込み用
  for (int i = 0; i < n; ++i) {
    // Nこの整数の中に一つでも0があれば答えは0
    std::cin >> a[i];
    if (a[i] == 0) {
      std::cout << 0 << std::endl;
      return 0;
    }
  }
 
  for (int i = 0; i < n; ++i) {
    if (mx / m < a[i]) {
      std::cout << -1 << std::endl;
      return 0;
    }
    m *= a[i];
  }

  std::cout << m << std::endl;
  return 0;  
}

ミソは17行目です．i個目の整数までの積の値が\(mx(10^{18})\)を超えるかどうかの判定する際に，\(mx\)の値を(i-1)個目までの積の値で割ったものとi個目の整数を比較しているところです．つまり\(mx \lt m \cdot a_i\)とする代わりに \(\frac{mx}{m} \lt a_i\)をしているところです．こうすることによりオーバーフローを防ぎ正しく値を比較することが出来ます．

切り捨てても正しい答えが導けるの

公式の解説も，そのほかのいろいろな解説もここまでだったのですが，僕は一つ疑問に思いました．\(\frac{mx}{m}\)の値は切り捨てられているけど正しい結果が導けるのかという疑問です．

実はこれ冷静に考えるときちんと正しい結果が導けるのです．

示すことは\(\frac{mx}{m}\)と\(a_i\)の比較結果と\(\lfloor\frac{mx}{m}\rfloor\)と\(a_i\)の比較結果が同じ値になることです．\(\frac{mx}{m}\)の計算で余りがないときは正しい結果が導けることは明白なので余りが出る時を考えてみます．

\(mx = m \cdot q + r\)とする．\(0 \le r \lt m\)より\(0 \le \frac{r}{m} \lt 1\)
\((i)\) \(\lfloor\frac{mx}{m}\rfloor(=q) \lt a_i\)の時
\(q\)も\(a_i\)も整数だから\(a_i-q \ge 1\)が成り立つ．
\(q\)を移行して\(a_i \ge q + 1 > q + \frac{r}{m} = \frac{mx}{m}\)となる．

\((ii)\) \(\lfloor\frac{mx}{m}\rfloor(=q) \ge a_i\)の時
\(\frac{mx}{m} \gt \lfloor\frac{mx}{m}\rfloor \ge a_i\)となる．
以上\((i)(ii)\)から\(\frac{mx}{m}\)と\(a_i\)の比較結果と\(\lfloor\frac{mx}{m}\rfloor\)と\(a_i\)の比較結果は同じ値になる．

解説は以上となります．間違いや意見があれば言っていただけると嬉しいです．

切り捨てとか切り上げとかめちゃくちゃ苦手だったんですが，今回の問題を解くことを通して苦手意識が薄まったような気がします．