概要

高橋君の点数 \(X\) と \(N\) 人の生徒の点数 \(A_i\) が与えられたとき、\(A_i > X\) となる生徒についてのみその差分 \(A_i - X\) を計算し、その合計（悔しさの総和）を求める問題です。

考察

この問題で求められている「悔しさ」は、各生徒 \(i\) について以下のように定義されています。 - \(A_i > X\) のとき： \(A_i - X\) - \(A_i \leq X\) のとき： \(0\)

これは、数学的には \(\max(0, A_i - X)\) と書くこともできます。

重要なポイント

• 各生徒を独立に処理できる: ある生徒の点数が高橋君の点数より高いかどうかは、他の生徒の点数には依存しません。したがって、生徒 \(1\) から \(N\) まで順番にチェックしていけばよいです。
• 制約の確認: 生徒の数 \(N\) は最大で \(5 \times 10^5\) です。1人ずつ順番に計算を行う \(O(N)\) のアルゴリズムであれば、制限時間内に十分間に合います。

具体例

例えば、高橋君が \(50\) 点 (\(X=50\))、他の生徒が \([40, 60, 50, 80]\) 点の場合を考えます。 1. \(40\) 点の生徒： \(40 \leq 50\) なので、悔しさは \(0\) 2. \(60\) 点の生徒： \(60 > 50\) なので、悔しさは \(60 - 50 = 10\) 3. \(50\) 点の生徒： \(50 \leq 50\) なので、悔しさは \(0\) 4. \(80\) 点の生徒： \(80 > 50\) なので、悔しさは \(80 - 50 = 30\) 合計は \(0 + 10 + 0 + 30 = 40\) となります。

アルゴリズム

1. 悔しさの合計を保持する変数 total_regret を \(0\) で初期化する。
2. \(N\) 人の生徒の点数を一つずつ確認するループ（繰り返し処理）を行う。
3. 各点数 score について、もし score > X であれば、 total_regret に score - X を加算する。
4. ループ終了後、 total_regret を出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度ずつ走査するため、 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の点数をリストに格納して保持する場合、 \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入力: \(N\) が \(5 \times 10^5\) と比較的大きいため、Pythonでは sys.stdin.read().split() を使って入力を一括で読み込むことで、実行時間を短縮しています。

• 条件分岐: if score > x: という条件式を用いることで、問題文にある「\(A_i > X\) のときのみ計算する」というルールを素直に実装できます。

  ソースコード

import sys

def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    x = int(input_data[1])
    a = map(int, input_data[2:])
    
    total_regret = 0
    for score in a:
        if score > x:
            total_regret += score - x
            
    print(total_regret)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。