ABC127_D(Integer Cards) - プログラムのお勉強メモ

問題

AtCoder Beginner Contest 127 - D

考えたこと

少ない数値を大きい数値に変換し続ければ良い
カードをソートして, 入力値を二分探索, その中で小さい方から更新していけば良さそう？
制約もだし行けそうな気がする
- 先にオチを言うと TLE でした

実装(TLE)

import bisect
from collections import deque
 
n, m = [int(x) for x in input().split()]
a_l = [int(x) for x in input().split()]
a_l.sort()
a_l = deque(a_l)
 
 
for i in range(m):
    b, c = [int(x) for x in input().split()]
    idx = bisect.bisect_left(a_l, c)
 
    for _ in range(min(idx, b)):
        a_l.insert(idx, c)
        a_l.popleft()
 
print(sum(a_l))

再考察

insert が O(N) だった気がするのでこれが敗因と思われる
やりたいことは以下の通り
- 入力値より小さい値を持つ idx を探す
- idx の小さい方から b個までの間を新しい値で更新する
- 確かPythonってスライス処理も遅かった記憶が...
- 詰まる -> 仕方がないので解説を見る

解説を見ての気づき

もしかして単純に追加して最後にソートすればよかった？ -> 駄目でした. 流石に浅はか
やはり解説通り入力を全部読み込んで大きい順番にソートしてから n 個取るのが良さそう
書き換え部分が (書き換え回数, ポイント) の tuple 形式になっているため, できれば初期値も tuple にしたい
collections.Counter で tuple の形にして, 書き換え部分と辞書型のまま結合, sortかければ行けそう

改めての実装

from collections import defaultdict
from collections import Counter

n, m = [int(x) for x in input().split()]
a_l = [int(x) for x in input().split()]
a_l_d = Counter(a_l)

input_dict = defaultdict(int)

for i in range(m):
    b, c = [int(x) for x in input().split()]
    input_dict[c] += b

a_l_d.update(input_dict)
new_d = sorted(a_l_d.items(), reverse=True)

ans = 0
for point, count in new_d:
    ans += point * min(count, n)
    n = max(0, n-count)

    if n == 0:
        break

print(ans)

上記コードで無事に AC
list の insert と slice は知ってたけど駄目ですね