AtCoder ABC 169 B - Multiplication 2 を、Rubyで最後まで掛け算して解いた

問題はこちら。掛け算の順序を工夫することで、Rubyで十分に速く解けた。

N個の整数 A1,...,Anが与えられます。
A1 * ... * An を求めてください。
ただし、結果が 10**18 を超える場合は、代わりに '-1' を出力してください

制約
* 2 <= N <= 10**5
* 0 <= Ai <= 10**18
* 入力は全て整数である。

B - Multiplication 2

解説はこんな感じ。

Ai に 0 が含まれる場合、答えは 0 です。そうでない場合を考えます。 64bit 整数でそのまま掛け算を行うとオーバーフローします。倍精度浮動小数点数で計算を行う と精度が足りません。多倍長整数で最後まで計算すると TLE します。したがって何らかの工夫が 必要です。 Python などの多倍長整数が使える言語や、128bit 整数が使える環境であれば「積が 10**18 が超え た時点で -1 を出力する」とすることで解くことができます。

「多倍長整数で最後まで計算すると TLE します」とあるんだけど、掛け算の方法を工夫することでACできた。この解き方をしている人が少なそうだったので記事を書いてみる。コンテスト中に提出したコードから不要な部分を除くとこんな感じ。いつも通りRubyで書いた。

# Nと空白区切の入力値を数値の配列で返却する
def gets_n_and_i_list()
 return gets.chomp.to_i, gets.chomp.split(" ").map(&:to_i)
end
N, a_list = gets_n_and_i_list

a_list.sort!
total = 0
loop do
 if a_list.size == 1
   total = a_list[0]
   break
 end
 a_list = a_list.each_slice(2).map { |a, b| b ? a * b : a }
end

puts total > 10**18 ? -1 : total

最大でも238msで計算が終わった。ポイントは2つあって、最初に配列をソートしていることと、配列の要素を1つずつ掛けるのではなく要素数2の配列にSliceして、それをかけ合わせていくことを繰り返していること。

このアイディアはもともと↓のQiitaで紹介されていたもので、掛け算の順序を変えることで、速度が大きく異なることが解説されている。大きな数値と小さな数値の掛け算では、概ね大きい数値の桁数に比例して時間が増加するとあった。

掛け算の順序問題 in Ruby - Qiita

これは↓の問題を解いているときに、階乗の計算(このときは N! * M!)をする必要があって、そのときに知った。

C - Reconciled?

普通にRubyで書くと階乗はこんな感じで書けるけど、これだと遅くてTLEして困っていた。

(1..N).inject(&:*)

高速化する方法ないのかなーとと思って調べてみて行き着いたのが、上述のQiitaの記事だった。上述の記事で書いてある通り、かなり速度に差がある。すごいなーと思って印象に残っていた。

今回は、最初は普通に掛け算してTLEした。Rubyだと N <= 10**5 でTLEしちゃうことけっこうあって、他の言語だと普通に解けるけどRubyだと高速化しないといけないタイプの問題なんだろうなと思った。

B問題だし力技で解きつつ多少高速化するかー、この方法を使ってみた。でも、解説を読むとそんなことはなかった。ごめん、Ruby。

ちなみにRubyの数値は基本的にオーバーフローしなくて、IntergerにFixnum(固定長整数), Bignum(多倍長整数)が統合されている。桁が大きい分にはほとんど意識する必要がなくて素敵。