AtCoder Beginner Contest405振り返り

ABC3完答でしたがC問題に時間がかかり低調なパフォーマンスでした。 パフォーマンス287、新Rating356（△8）。

C問題 提出コード

atcoder.jp

普通に実装するとO(N²)になるので配列の合計値を利用することで計算量を削減する実装を思いつくことができました。 思いついたのはいいのですが思考に時間がかかりすぎました。

#!/usr/bin/env ruby
n = gets.to_i
a = gets.split.map(&:to_i)
sum = a.sum
ans = 0
(0..n-2).each do |i|
  sum -= a[i]
  ans += a[i] * sum
end
puts ans

C問題 公式解説動画の別解

正方形のマスで考えて配列の合計値の2乗-対角線/2が答えになる。 この考え方は全く思いつかなかったので今後に活かすために覚えておきたいです。

#!/usr/bin/env ruby
n = gets.to_i
a = gets.split.map(&:to_i)
sum = a.sum
sum2 = a.map{ |n| n ** 2 }.sum
ans = (sum ** 2 - sum2) / 2
puts ans