AtCoder Beginner Contest 127 D - Integer Cards - 思考のジャンプ幅が狭いなら，飛ぶ回数で補えばいいじゃない！！

f:id:hiro_kato:20190526161433j:plain

結論

すべての数字（書き換えの前後を区別せず）に対して，大きいものから $N個$ を選んで合計を取る．
計算量を減らすための工夫として，各数字とその個数をペアで管理するようなデータ構造（プライオリティ・キュー，辞書（連想配列）など）を用いる．

はじめに

AtCoderで出題された問題を復習しています．
公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います．

想定読者

解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

AtCoderのレートで緑下位．

記事の特徴

なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．
試行錯誤した過程から，得られた前提知識や着眼点を言語化していきます．
間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．
- 連絡先：@k_hiro1818

問題のリンク

D - Integer Cards (400点)

発想・解法とそれらを引きだすための方法・解釈

最初の一歩は?

サンプルにしたがって，手元で計算してみる．
整数 $C_{j}$ が整数 $A_{i}$ より大きく，かつ，使った回数が $B_{j}$ 回より少なければ書き換えることができ，整数の合計値の最大値を大きくできる．
書き換えるときは， $C_{j}$ が大きなものから順番に使うとよさそう（貪欲法のアプローチ）．

考察のキモ（Key Insight）は?

すべての数字（書き換えの前後を区別せず）に対して，大きいものから $N個$ を選んで合計を取る．
数字をそのまま配列などで管理するとデータ量が多くなる（最大で $O(N + BM)=10^{10}$ ）．このため，各数字とその個数をペアで管理するようなデータ構造（プライオリティ・キュー，辞書（連想配列）など）を用いるとよい．

どうしたら思いつけそうか?

ある値 $i$ から別の値 $j$ に「書き換える」という操作を，数字の集合全体から「選択」する，という視点の転換．
データのうち，重複している部分はないか?（=何かの方法でまとめられないか?）

解法の妥当性は?

操作の順番そのものは，結果に影響しない．
$A_{i}$ を小さな値で2回以上書き換えるくらいなら，最初から大きな値を使えばよい．
使える回数（枚数）が， $0からB_{j}$ 回までとなっているところがミソ．ちょうど $B_{j}$ 回という条件なら，別解を考える必要がありそう（要検証）

実装のポイントは?

データの管理にcollections.Counter()を使用．数字をキーに割り当て，個数を値として保持している．
数字(キー)で降順に並び替えるため，Sorted()とlambda式を併用．

docs.python.org

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    from collections import Counter

    n, m = map(int, input().split())
    a = Counter(list(map(int, input().split())))

    for i in range(m):
        bi, ci = map(int, input().split())
        a[ci] += bi

    cards = sorted(a.items(), key=lambda x: x[0], reverse=True)
    ans = 0

    for number, count in cards:
        if n > count:
            ans += number * count
            n -= count
        else:
            ans += number * n
            print(ans)
            exit()


if __name__ == '__main__':
    main()

試行錯誤した過程

書き換えの条件を列挙して，書き換える部分だけを切り出そうとした
- $max(C_{j})$ が $min(A_{i})$ よりも小さければ，そのまま．
書き換える個数と合計を条件分岐で管理しようとした（考察と実装それぞれに時間を要した）
- 数列 $A$ に対して，ある数字 $C_{j}$ が入る位置を二分探索で調べようとした．
- また， $B_{j}$ 回， $A$ の書き換えていない回数との最小値を取れば，書き換えられる回数を求められると思ったが，条件の考慮が不足していた．