Three-person team working

解説

この問題は愚直に解くと$O(N^3)$ですが 数式をいじると$O(N)$になる問題です。

解法を$2$つ示します。

解法$1$

包除原理で解けます。$A$ の和の$3$ つの積を $S$ とすると

$\ S = (A_1 + A_2 + A_3 + ⋯ + A_N)*(A_1 + A_2 + A_3 + ⋯ + A_N)*(A_1 + A_2 + A_3 + ⋯ + A_N)$

これを解くと求めたい式 $T$は

$\ S =$

$\ (A_1^{3} + A_2^{3} + ⋯ + A_N^{3})$　　

$\ + 3 * \sum_{i=1}^{N} \sum_{j=1}^{N} A_i^{2}*A_j (i \neq j) \\$

$\ + 6 * T$

$1$項目は愚直，$2$項目は以下のように展開すると$O(N)$ で算出できる。

$\ \sum_{i=1}^{N} A_i^{2} ( \sum_{j=1}^{N} A_j \ - A_i )\$

よって求めたい式$T$は$S$から不要部分を引き、$6$で割ると算出できる。

解法$2$

式で考える。

$\ S_i$ を 学生$\ i (1 \leq i \leq N)$　以上$N$以下の学生間において、 $2$人組の全ての組み合わせのパフォーマンスの和とすると 求めたい数値は

$\ A_1*S_2 + A_2*S_3 + A_3*S_4 + ⋯ + A_{N-2} * S_{N-1}$

$\ S_i$は$\ O(N)$で算出できる。

よって 累積和をあらかじめ計算しておくと$\ O(N)$で計算できる。