概要

各生徒について、「高橋君より点数が高いならその差を加える、そうでなければ \(0\) を加える」というルールをそのまま合計すればよい問題です。

考察

生徒 \(i\) に対する悔しさは、問題文の定義そのまま

• \(A_i > X\) なら \(A_i - X\)
• \(A_i \le X\) なら \(0\)

です。
したがって、全員についてこの値を足し合わせれば答えになります。

例えば \(X = 60\)、生徒の点数が \([55, 80, 60, 75]\) のとき、

• \(55\) 点の生徒: 高橋君以下なので \(0\)
• \(80\) 点の生徒: \(80 - 60 = 20\)
• \(60\) 点の生徒: 同点なので \(0\)
• \(75\) 点の生徒: \(75 - 60 = 15\)

合計は \(0 + 20 + 0 + 15 = 35\) です。

この問題では、各生徒を 1 回ずつ見るだけで十分です。
\(N \le 5 \times 10^5\) なので、全員を順番に確認する \(O(N)\) の方法なら十分高速に間に合います。

逆に、不要に複雑な処理をしたり、各生徒について何度も計算し直したりすると無駄です。この問題は定義通りに素直に実装するのが最も簡単で確実です。

アルゴリズム

1. 答えを表す変数 ans を \(0\) で初期化する。
2. 各生徒の点数 \(a\) について以下を行う。
   • もし \(a > X\) なら、ans += a - X
   • そうでなければ何もしない
3. 最後に ans を出力する。

これで、全生徒に対する悔しさの合計が求まります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 条件は「高いとき」だけなので、if a > X: と書けば十分です。

• 同点のときは悔しさは \(0\) なので、a >= X ではなく a > X である点に注意しましょう。

• 提示コードでは高速入力のために sys.stdin.buffer.read() を使っていますが、処理内容自体は単純な 1 回の走査です。

  ソースコード

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
N, X = data[0], data[1]
ans = 0
for a in data[2:2 + N]:
    if a > X:
        ans += a - X
print(ans)

---

この解説は gpt-5.4-high によって生成されました。