概要

\(N\) 個の部屋の室温を同一の整数値 \(T\) に統一するとき、重み付き絶対偏差の総和 \(\sum S_i \times |P_i - T|\) を最小化する問題です。これは重み付き中央値を求めることで解けます。

考察

重要な気づき：重み付き中央値が最適

まず、重みがすべて \(1\) の場合を考えましょう。\(\sum |P_i - T|\) を最小にする \(T\) は、\(P_i\) たちの中央値であることが知られています。

本問では各部屋に広さ \(S_i\) という重みがついています。直感的には、部屋 \(i\) の広さが \(S_i\) ということは「\(P_i\) という温度の部屋が \(S_i\) 個ある」と解釈できます。このとき最適な \(T\) は、重み付き中央値（weighted median）になります。

素朴なアプローチではなぜダメか

\(P_i\) の値域が \(-10^9\) から \(10^9\) と非常に広いため、すべての整数 \(T\) を試すと \(O(2 \times 10^9)\) 通りとなり、到底間に合いません。

どう解決するか

最適な \(T\) は必ずいずれかの \(P_i\) の値になります（重み付き絶対偏差の和は区分線形関数で、折れ点は \(P_i\) の位置にあるため）。さらに、重み付き中央値の性質から、候補を \(1\) つに絞り込めます。

アルゴリズム

1. ソート: 部屋を温度 \(P_i\) の昇順にソートする。
2. 重み付き中央値の探索: 重みの合計 \(W = \sum S_i\) を求め、ソート順に重み \(S_i\) を累積していく。初めて累積重みが \(W / 2\) 以上になった位置の温度 \(P_i\) が重み付き中央値。
3. コスト計算: 重み付き中央値とその前後（\(T-1, T, T+1\)）でコストを計算し、最小値を出力する。

具体例

部屋が 3 つで、\((S, P) = (3, 10), (1, 20), (2, 30)\) の場合：

• \(P\) の昇順にソート → \((3,10), (1,20), (2,30)\)
• 総重み \(W = 3 + 1 + 2 = 6\)
• 累積重み: \(3 \to 4 \to 6\)。初めて \(\geq 6/2 = 3\) となるのは累積 \(3\) の時点 → \(T = 10\)
• コスト: \(3 \times |10-10| + 1 \times |20-10| + 2 \times |30-10| = 0 + 10 + 40 = 50\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。中央値の探索とコスト計算はそれぞれ \(O(N)\)）
• 空間計算量: \(O(N)\)（部屋の情報を格納）

実装のポイント

• 重み付き中央値の条件: 累積重み \(\times 2 \geq\) 総重みとなった最初の位置を中央値とする。これは「左側の重みの合計が全体の半分以上になる最小の \(P_i\)」を見つけている。

• 前後の候補もチェック: 整数制約や境界条件での微妙なずれに備え、\(T\) の候補として中央値の \(\pm 1\) も試して安全を確保している。ただし理論的には重み付き中央値そのものが最適。

• 高速入力: sys.stdin.buffer.read() を用いて入力を一括読み込みすることで、\(N\) が大きい場合でも高速に処理できる。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    rooms = []
    for i in range(N):
        s = int(input_data[idx]); idx += 1
        p = int(input_data[idx]); idx += 1
        rooms.append((p, s))
    
    # Sort by temperature
    rooms.sort()
    
    # The optimal T is the weighted median of P_i with weights S_i
    # For weighted median: find the smallest P such that cumulative weight >= total_weight / 2
    
    total_weight = sum(s for _, s in rooms)
    
    # Find weighted median
    cumsum = 0
    median_idx = 0
    for i, (p, s) in enumerate(rooms):
        cumsum += s
        if cumsum * 2 >= total_weight:
            median_idx = i
            break
    
    # The optimal T is at or near rooms[median_idx][0]
    # Since T must be integer and P_i are integers, the weighted median P value works
    # But let's check the candidate and neighbors to be safe
    
    T_candidate = rooms[median_idx][0]
    
    def compute_cost(T):
        return sum(s * abs(p - T) for p, s in rooms)
    
    best = compute_cost(T_candidate)
    for delta in [-1, 0, 1]:
        cost = compute_cost(T_candidate + delta)
        if cost < best:
            best = cost
    
    print(best)

solve()

この解説は claude4.6opus-thinking によって生成されました。