AtCoder Beginner Contest 127 D – Integer Cards をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 127 D – Integer Cards

問題を読んで最初に思いついたのは、優先度付きキューを用いたシミュレートだったが、制約が \(1 \le N \le 10^5, 1 \le M \le 10^5 \)で、最悪 NM 回行うことを考えると間に合わなさそう。なので、真面目に考察を行う必要がある。

カードに書かれた数字を書き換えると考えると一見面倒くさそうだが、新たにカードを引き、その際に一番数字の小さいカードを捨てる、と考えると見通しが立てやすいかも。

# AtCoder Beginner Contest 127 D - Integer Cards
# https://atcoder.jp/contests/abc127/tasks/abc127_d
# tag: 考察

# 最大効率でカードの交換を行った場合、結局のところ
# 最初に持っている数字 + 書き換え後の数字 の集合から
# 上位 N 枚のカードを選んだのと同じ状態になる。

# というわけで、全てのカードを数字ごとに整理しなおし、
# 上位 N 枚の数字の合計を求めることにする。
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    changes = [list(map(int, input().split())) for _ in range(M)]

    # カードの数字ごとに何枚あるかを保存
    cnt = dict()

    # 最初に持っているカードを数える
    for a in A:
        if a not in cnt:
            cnt[a] = 0
        cnt[a] += 1

    # 書き換え後のカードをカウントに加える
    for b, c in changes:
        if c not in cnt:
            cnt[c] = 0
        cnt[c] += b

    # 数字を大きい順にソート
    cards = list(cnt.keys())
    cards.sort(reverse=True)

    # N 枚になるまで大きい数字から順番に取る
    taken = 0
    result = 0
    for card in cards:
        n = cnt[card]
        if taken + n < N:
            result += card * n
            taken += n
        else:
            n = N - taken
            result += card * n
            break

    print(result)

main()

abc127_d.py view raw

関連

コメントを残すコメントをキャンセル