概要

\(N\) 個の部屋の室温をある整数 \(T\) に統一する際、各部屋の広さ \(S_i\) を重みとした絶対誤差の総和 \(\sum S_i |P_i - T|\) を最小化する問題です。これは統計学における「加重中央値」を求める問題に帰着されます。

考察

1. 目的関数の性質

最小化したい関数 \(f(T) = \sum_{i=1}^{N} S_i |P_i - T|\) について考えます。 もしすべての \(S_i\) が \(1\) であるならば、この関数を最小にする \(T\) は \(P_i\) の中央値になることが知られています。 本問では各 \(P_i\) に重み \(S_i\) がついているため、加重中央値（重み付き中央値）を求めることになります。

2. なぜ中央値なのか

関数 \(f(T)\) は凸関数（下に凸なグラフ）であり、その傾きは \(T\) を増加させたときに以下のように変化します。 - \(T\) を \(1\) 増やしたとき、現在の \(T\) より小さい \(P_i\) を持つ部屋のコストは \(S_i\) ずつ増え、大きい \(P_i\) を持つ部屋のコストは \(S_i\) ずつ減ります。 - つまり、傾きが負から正に転じるポイント（累積の重みが全体の半分を超える場所）が最小値となります。

3. \(T\) が整数であるという制約

問題文には「\(T\) は整数」という制約がありますが、関数の折れ曲がる点（傾きが変わる点）はすべて入力の \(P_i\)（整数）の位置にあります。したがって、加重中央値となる \(P_k\) は必ず整数であり、そのまま最適な \(T\) として採用できます。

アルゴリズム

1. 各部屋の情報を温度 \(P_i\) と広さ \(S_i\) のペアとして取得し、温度 \(P_i\) の昇順にソートします。
2. 全部屋の広さの合計 \(W = \sum S_i\) を計算します。
3. ソートした順に広さ \(S_i\) を累積していき、累積和が \(W/2\) 以上になった瞬間の温度 \(P_k\) を目標温度 \(T\) とします。
4. 求めた \(T\) を用いて、各部屋のコストの総和 \(\sum S_i |P_i - T|\) を計算して出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 部屋のソートに \(O(N \log N)\) かかります。その後の累積和の計算とコストの計算は \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • \(N\) 個の部屋の情報をリストに保持するために必要です。

実装のポイント

• 高速な入出力: \(N\) が最大 \(150,000\) と大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 加重中央値の判定: 累積和を current_w とすると、current_w * 2 >= total_w という条件（分母を払った形）で判定することで、浮動小数点の誤差を避けつつ「半分以上」を正確に判定できます。

• 大きな値の扱い: 最終的なコストは非常に大きな値になる可能性がありますが、Python は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # Fast I/O: read all input at once and split by whitespace
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        line = next(it)
    except StopIteration:
        return
    
    N = int(line)
    
    # The problem asks to minimize the function f(T) = sum(S_i * |P_i - T|)
    # where T is an integer. This is a weighted version of the median problem.
    # Since f(T) is a convex, piecewise linear function with corners at integer 
    # coordinates P_i, the minimum value will be achieved at one of the P_i.
    
    rooms = []
    # Each room has a size S_i and a temperature P_i
    for _ in range(N):
        try:
            s = int(next(it))
            p = int(next(it))
            rooms.append((p, s))
        except StopIteration:
            break
            
    # Sort the rooms by temperature P_i to find the weighted median
    # This operation is O(N log N)
    rooms.sort()
    
    # Calculate the total weight (sum of all sizes S_i)
    total_weight = sum(r[1] for r in rooms)
    
    # The weighted median target_t is the first temperature P_i where the 
    # cumulative weight reaches or exceeds half of the total weight.
    cumulative_weight = 0
    target_t = rooms[0][0]
    for p, s in rooms:
        cumulative_weight += s
        if cumulative_weight * 2 >= total_weight:
            target_t = p
            break
            
    # Calculate the minimum total cost using the found target_t
    # Total cost = sum(S_i * |P_i - target_t|)
    min_total_cost = 0
    for p, s in rooms:
        min_total_cost += s * abs(p - target_t)
        
    # Output the result as an integer
    sys.stdout.write(str(min_total_cost) + '\n')

if __name__ == '__main__':
    solve()

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