概要

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

考察

重要な気づき

1. \(R\) の候補は有限個で十分小さい: 標識の座標は \(-100 \leq X_i \leq 100\) の範囲にあるため、\(R\) を \(100\) より大きくしても新たに照らされる標識は増えません。一方、電力コスト \(R^2\) は増え続けるため、\(R > 100\) は常に \(R = 100\) より効果が悪くなります。したがって、\(R = 0, 1, 2, \ldots, 100\) の \(101\) 通りだけ調べれば十分です。

2. 全探索で間に合う: \(R\) の候補が高々 \(101\) 通り、標識が高々 \(100\) 個なので、すべての組み合わせを調べても \(101 \times 100 = 10{,}100\) 回程度の計算で済みます。

具体例で確認

例えば、標識が座標 \(3\) に重要度 \(20\)、座標 \(-5\) に重要度 \(50\) にあるとします。

• \(R = 0\): 効果 \(= 0 - 0 = 0\)
• \(R = 3\): 座標 \(3\) の標識が照らされ、効果 \(= 20 - 9 = 11\)
• \(R = 5\): 両方照らされ、効果 \(= 70 - 25 = 45\)
• \(R = 10\): 両方照らされるが、効果 \(= 70 - 100 = -30\)

このように、\(R\) を大きくしすぎるとコストが重要度の合計を上回り、効果が下がります。

R = 0 が最適な場合

すべての \(R \geq 1\) で効果が負になることもあり得ます。問題文にある通り \(R = 0\) では効果が \(0\) 以上になるため、答えは常に \(0\) 以上です。初期値を \(0\) にしておけば正しく処理できます。

アルゴリズム

1. 全標識の座標と重要度を読み込む。
2. 効果の最大値 best を \(0\) で初期化する（\(R = 0\) で最低でも \(0\) 以上が保証されるため）。
3. \(R = 0, 1, 2, \ldots, 100\) のそれぞれについて：
   • \(|X_i| \leq R\) を満たす標識の重要度の合計を計算する。
   • 効果 \(= (\text{重要度の合計}) - R^2\) を求める。
   • best より大きければ更新する。
4. best を出力する。

計算量

• 時間計算量: \(O(R_{\max} \times N)\)（\(R_{\max} = 100\) なので \(O(100 \times N)\)、実質 \(O(N)\) と見なせる）
• 空間計算量: \(O(N)\)（標識の情報を保持する分）

実装のポイント

• best の初期値を \(0\) にする: \(R = 0\) のとき効果は \(0\) 以上であることが保証されているため、初期値を \(0\) にしておけば、すべての \(R\) で効果が負の場合でも正しく \(0\) が出力されます。

• abs(x) <= R の判定: 街灯は原点を中心に左右対称に照らすため、標識の座標の絶対値が \(R\) 以下かどうかで判定します。

• \(R\) の探索範囲は \(0\) から \(100\) で十分: 座標の絶対値の最大が \(100\) なので、それ以上の \(R\) を試す必要はありません。

  ソースコード

N = int(input())
signs = []
for _ in range(N):
    x, p = map(int, input().split())
    signs.append((x, p))

best = 0
for R in range(0, 101):
    total = sum(p for x, p in signs if abs(x) <= R)
    effect = total - R * R
    if effect > best:
        best = effect

print(best)

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