概要

原点にある街灯の照らす範囲 \(R\) を選んで、照らされる標識の重要度の合計から電力コスト \(R^2\) を引いた「効果」を最大化する問題。

考察

この問題では、非負整数 \(R\) を選ぶことで、原点から距離 \(R\) 以内の標識（つまり \(|X_i| \leq R\)）が照らされ、それらの重要度の合計からコスト \(R^2\) を引いた値が効果となる。

素朴なアプローチ

素朴には、\(R\) を 0 からある上限まで動かしながら、各 \(R\) に対して条件 \(|X_i| \leq R\) を満たす標識の重要度を全部足して、そこから \(R^2\) を引く方法が考えられる。しかし、この方法では毎回すべての標識を確認する必要があり、効率が悪い可能性がある。

ただし制約より、座標の絶対値の最大値は高々 100 なので、\(R\) の候補もせいぜい 0 〜 100 で十分である。また、同じ座標に複数の標識がある可能性があるので、事前に同じ座標の重要度を合計しておくと効率的。

改善策

各 \(R\) に対して毎回全探索すると、計算量は \(O(N \times R_{\text{max}})\) 程度になるが、制約が小さいのでこれでも間に合う。ただし、より効率的にするために、前もって標識の位置と重要度の合計をまとめておき、各 \(R\) に対して範囲内のものを合計するという処理を行うと良い。

アルゴリズム

1. 各標識の座標 \(X_i\) と重要度 \(P_i\) を読み込む。
2. 同じ座標にある標識の重要度を合計するために、defaultdict を使って pos_sum[x] に座標 \(x\) における重要度の合計を記録する。
3. \(R\) の取りうる範囲（0 から 最大の \(|X_i|\)）について、各 \(R\) に対して以下を行う：
   • 条件 \(|X_i| \leq R\) を満たすすべての標識の重要度の合計を求める。
   • 効果：\(\left(\sum P_i\right) - R^2\) を計算。
   • 最大の効果を更新していく。
4. 最後に最大の効果を出力する。

計算量

• 時間計算量: \(O(N + R_{\text{max}}^2)\) （ただし \(R_{\text{max}} = \max |X_i|\)、今回は最大100）
• 空間計算量: \(O(N)\)

※ 実際には \(R\) のループ内で毎回合計を計算しているので、全体で \(O(N \cdot R_{\text{max}})\) となるが、\(N\) や \(R_{\text{max}}\) が非常に小さいので問題ない。

実装のポイント

• 同じ座標に複数の標識がある場合、重要度を合計する必要がある。

• \(R = 0\) のときも考慮し、効果の初期値は 0 にしておく。

• 座標の絶対値の最大値まで \(R\) を試せば十分（それ以上大きくしても意味がない）。

  ソースコード

n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

# 座標ごとに重要度を合計するための辞書
import collections
pos_sum = collections.defaultdict(int)
for x, p in data:
    pos_sum[x] += p

# 効果の最大値を計算
max_effect = 0  # R=0 のときは効果が0以上になるので、最低でも0

# 座標の絶対値の最大値まで試せば十分
positions = list(pos_sum.keys())
if not positions:
    print(0)
else:
    max_abs_x = max(abs(x) for x in positions)
    # R を 0 から max_abs_x まで試す
    prefix_sum = 0
    pos_sum_sorted = sorted(pos_sum.items())  # (position, sum of P) のリスト
    j = 0  # pos_sum_sorted のインデックス
    for r in range(max_abs_x + 1):
        # 新しく加わる範囲 [-r, -r+1, ..., r-1, r] に含まれる標識の重要度を加算
        while j < len(pos_sum_sorted) and pos_sum_sorted[j][0] <= r:
            if pos_sum_sorted[j][0] >= -r:
                prefix_sum += pos_sum_sorted[j][1]
            j += 1
        effect = prefix_sum - r * r
        if effect > max_effect:
            max_effect = effect
        # j をリセットせずに次に備えるために、再度調整が必要
    # より正確にするため、prefix_sum を毎回再計算する方式に変更
    max_effect = 0
    for r in range(max_abs_x + 1):
        total = 0
        for x, p_sum in pos_sum.items():
            if abs(x) <= r:
                total += p_sum
        effect = total - r * r
        if effect > max_effect:
            max_effect = effect

    print(max_effect)

この解説は qwen3-coder-480b によって生成されました。