ABC177C - Sum of product of pairsを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 177 C - Sum of product of pairsをCommon Lispで解いてみました。

まず問題文を見ます。
数列$A$から数を2つ選んで掛け算をしてその合計を$10^9+7$で割った余りを求める問題です。
問題がシンプルで、計算量が$O(N^2)$になる全探索しかないように見えます。
$N \le 10^3$であれば間に合いますがどうか。

次に制約を見ます。
$N \le 2 \times 10^5$なので全探索では間に合いません。他の方法を考える必要があります。

出力例1の下にある式を眺めていると、式を変形できそうなことに気が付きました。
$A_i$でまとめると、以下のようになります。

$1 \times (2 + 3) + 2 \times (3)$

これは、$A_i \times A_{i+1}からA_Nまでの合計$になっています。
$A_{i+1}からA_Nまでの合計$は、最初に$A$全体の合計を計算しておき、そこから$A_i$を引くことで計算量$O(1)$で求められます。

以上より、以下の手順で解きます。

1. $A$の合計を計算する
2. $A$の合計から$A_1$を引く
3. $A_1$に$A$の合計をかけたものを答えに足す
4. 2、3を$A_{N-1}$まで繰り返す
5. 答えの剰余を計算して出力する

(let* ((n (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (loop with sum-a = (reduce #'+ a)
        with answer = 0
        for i from 0 below (1- n)
        for ai = (aref a i)
        do (decf sum-a ai)
           (incf answer (mod (* ai sum-a) (+ (expt 10 9) 7)))
        finally
           (format t "~A~%" (mod answer (+ (expt 10 9) 7)))))
  

式を変形できることに気づいたことで解くことができました。