概要

各生徒について「高橋君より何点高いか」を計算し、その合計を求める問題です。
具体的には、各 \(A_i\) に対して \(\max(0, A_i - X)\) を足し合わせれば答えになります。

考察

悔しさの定義は次の通りです。

• \(A_i > X\) なら \(A_i - X\)
• それ以外なら \(0\)

つまり、生徒ごとの寄与は \(\max(0, A_i - X)\) と同じです。
したがって、全体の悔しさは

\[ \sum_{i=1}^{N} \max(0, A_i - X) \]

で求まります。

重要な気づき

各生徒の悔しさは他の生徒と独立です。
そのため、配列を左から1回見るだけで合計できます（累積するだけ）。

素朴なアプローチについて

この問題では、全探索（全員を順に見る）自体が最適です。
余計なソートや二重ループは不要で、むしろ計算量が増えてしまいます。
\(N \le 5 \times 10^5\) なので、1回走査の \(O(N)\) 解法が安全です。

例えば \(X=70\), \(A=[65, 80, 70, 90]\) のとき：

• 65 は高くないので 0
• 80 は \(80-70=10\)
• 70 は同点なので 0
• 90 は \(90-70=20\)

合計は \(0+10+0+20=30\) です。

アルゴリズム

1. \(N, X\) を入力する。
2. 点数列 \(A\) を読む。
3. ans = 0 で初期化。
4. 各 a について：
   • a > X なら ans += a - X
   • それ以外は何もしない
5. ans を出力。

提示コードはこの手順をそのまま実装しています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を map で順次処理しており、追加メモリは定数）

実装のポイント

• 条件は「高いときのみ」なので a > X（>= ではない）に注意。

• sys.stdin.readline を使うと大量入力でも高速に処理できます。

• A = map(int, input().split()) としておくと、配列を作らずに順次処理できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, X = map(int, input().split())
    A = map(int, input().split())
    ans = 0
    for a in A:
        if a > X:
            ans += a - X
    print(ans)

if __name__ == "__main__":
    main()

---

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