AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、48の問目である「 I will not drop out（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【048 – I will not drop out（★3）】
考察
考えた内容の概要
この問題は、与えられた時間内で最大の得点を得るための戦略を求める最適化問題です。試験にはN問あり、各問題には満点がA_i点、部分点がB_i点あります。部分点は満点より小さく、満点の半分より大きいです。また、1分かけると部分点を取ることができ、さらに1分かけると満点を取ることができます。合計でK分の時間が与えられたとき、得られる合計得点の最大値を求めます。
考えたことの内容
各問題について、部分点を得るまでにかかる時間は1分、満点を得るまでにかかる時間は2分となります。したがって、時間を効率的に使うためには、部分点と満点の差（すなわち、追加で1分を使って得られる点数）が大きい問題から解くのが良いでしょう。これは、同じ時間（1分）を使うなら、得られる点数が多いほうが良いからです。
実装した内容
この考察に基づいてPythonのコードを実装しました。まず、各問題の部分点と満点との差を計算し、それらをリストに保存します。そして、そのリストを降順にソートします。これにより、追加で1分を使って得られる点数が大きい問題から順に並べられます。最後に、リストの先頭からK個の要素（つまり、K分で得られる最大の得点）を合計して出力します。
コード
N,K = map(int, input().split())
box = []
boxa = []
for i in range(N):
A,B = map(int, input().split())
sabun = A-B
box.append(B)
box.append(sabun)
box.sort(reverse=True)
print(sum(box[:K]))
コメント