概要

街灯の照らす範囲Rを非負整数で選び、照らされた標識の重要度の合計から電力コストR²を引いた値「効果」を最大化する問題です。

考察

効果を計算する式は \(\left(\sum_{|X_i| \leq R} P_i\right) - R^2\) です。標識の数Nが最大100と小さいため、すべての可能性のあるRを試すことが考えられます。しかし、Rの取り得る値は理論上無限に存在するため、全探索は不可能です。

重要な観察として、効果が変化するのは標識の座標の絶対値付近のみです。なぜなら、Rが標識の座標の絶対値を超えた瞬間にその標識が照らされるようになり、効果が増加するからです。したがって、候補となるRは標識の座標の絶対値とその+1の値、およびR=0に限定できます。

アルゴリズム

1. 候補となるRの集合を初期化（必ずR=0を含める）
2. 各標識について、その座標の絶対値と絶対値+1を候補に追加
3. 各候補Rについて、効果を計算
   • すべての標識をチェックし、|X_i| ≤ R なら重要度を加算
   • 合計重要度からR²を引いて効果を算出
4. 計算した効果の最大値を求める

計算量

• 時間計算量: \(O(N^2)\)
  • 候補の数は最大で \(2N+1\) 個（約200個）
  • 各候補についてN個の標識をチェックするため
• 空間計算量: \(O(N)\)
  • 標識の情報を格納するためのメモリ

実装のポイント

• 候補となるRの集合には重複を避けるためsetを使用

• Rは非負整数なので、負の値はスキップ

• 効果は常に0以上となることが保証されているが、明示的なチェックは不要（問題文より）

• 標識の座標が負の場合もあるので、絶対値で比較する必要がある

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    signs = []
    for i in range(1, n + 1):
        x, p = map(int, data[i].split())
        signs.append((x, p))
    
    max_effect = 0
    candidates = set()
    candidates.add(0)
    
    for x, p in signs:
        candidates.add(abs(x))
        candidates.add(abs(x) + 1)
    
    for R in candidates:
        if R < 0:
            continue
        total = 0
        for x, p in signs:
            if abs(x) <= R:
                total += p
        effect = total - R * R
        if effect > max_effect:
            max_effect = effect
            
    print(max_effect)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。