問題文にかかれている通り、各 \(i\) について問題を解く次のようなアルゴリズムを考えてみます。

for i = 1 to N:
  sum = 0
  for j = 1 to N:
    if A[j] > A[i]:
      sum += A[j]
  ans[i] = sum

このアルゴリズムは \(\Theta(N^2)\) 時間かかるため、実行時間制限に間に合わせることは困難です。より効率の良い解法を考えましょう。

以下では、まず \(A\) の要素が相異なる場合を考えます。

もし \(A\) の要素が降順に並んでいれば、各 \(i\) に対する問題の答えは \(i\) の昇順に効率よく求めることができます。すなわち、例えば \(A=(8,6,5,3,1)\) であれば、

• \(i=1\) のとき\(A_1=8\) より大きな要素の和は \(0\)
• \(i=2\) のとき\(A_2=6\) より大きな要素の和は \(8\)
• \(i=3\) のとき\(A_3=5\) より大きな要素の和は \(8+6\)
• \(i=4\) のとき\(A_4=3\) より大きな要素の和は \(8+6+5\)
• \(i=5\) のとき\(A_5=1\) より大きな要素の和は \(8+6+5+3\)

となることから、次のようなアルゴリズムにより \(O(N)\) 時間で求めることができます。

sum = 0
for i = 1 to N:
  ans[i] = sum
  sum += A[i]

このアルゴリズムの肝は、\(A\) の降順に処理することで「自分より大きな要素」の集合が単調に増加し、差分だけを更新すればよい、というところです。\(A\) が降順でないときも、降順になるようなindexの順で処理すれば同様のことができます。すなわち、例えば \(A=(3,8,6,1,5)\) であれば

• \(i=2\) のとき\(A_2=8\) より大きな要素の和は \(0\)
• \(i=3\) のとき\(A_3=6\) より大きな要素の和は \(8\)
• \(i=5\) のとき\(A_5=5\) より大きな要素の和は \(8+6\)
• \(i=1\) のとき\(A_1=3\) より大きな要素の和は \(8+6+5\)
• \(i=4\) のとき\(A_4=1\) より大きな要素の和は \(8+6+5+3\)

という順に考えれば解けます。この順序を得るためには、例えば \((A_i,i)\) のペア(タプル)をソートするという方法があります。

value_index = [(A[1], 1), (A[2], 2), ..., (A[N], N)]
value_index を降順にソートする
sum = 0
for k = 1 to N:
  Ai, i = value_index[k]
  ans[i] = sum
  sum += Ai

ソートに \(O(N\log N)\) 時間かかるため、この解法は \(O(N \log N)\) 時間になります。

\(A\) に同じ値が存在するときも、上で例示したアルゴリズムの sum の更新のタイミングに注意することで同様に解くことができます。より簡単な実装は、「値とindexの組」の代わりに、「値と”indexのリスト” の組」で扱うことです。詳細は以下の Writer解を確認してください。

Writer解(C++)

Writer解(Python)