AtCoder Beginner Contest 187 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：25分

問題設定にて与えられている値の条件が「1≤N≤2*10**5,1≤Ai,Bi≤2*10**9」なので二重ループは適用できません。
ということは1重ループで実行できるように発想の転換が必要です。

  1. scoreは現時点での高橋さんの票-青木さんの票です
  2. 高橋さんが演説しなかった場合を初期値にとります（score）
  3. 高橋さんが演説した場合「青木さんの票が高橋さんに移動分+青木さんの票の減少分+高橋さんの票増加分」（＝Delta）がscoreに加算されます
  4. Deltaはソートで影響票数が多い分に（O(nlog(n))）
  5. scoreが0を上回った時の演説回数を出力

これを実装します。

import numpy as np
N = int(input())
AB = np.array([list(map(int, input().split())) for i in range(N)])
# Takahashi - Aoki
score = (-1)*sum(AB[:,0])
Delta = AB[:,0]+AB[:,0]+AB[:,1]
count = 0
DeltaReverse = np.sort(Delta)[::-1]

for rd in DeltaReverse:
  count += 1
  score += rd
  if score>0: 
    break
print(count)

ACでした！