AtCoder Beginner Contest 160 E を Python で
AtCoder Beginner Contest 160 E を Python で解説していきたいと思います。
コンテスト中には解けなかったのですが，後で時間をかけて考えることでなんとか解くことができました。
考え方が大事で，思いつけば処理時間もあまり長くならず，実装も簡単という問題になります。
それでは，まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_e
E – Red and Green Apples
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
あなたは、X 個の赤色のリンゴと Y 個の緑色のリンゴを食べようとしています。
あなたは A 個の赤色のリンゴを持っており、美味しさはそれぞれ p1,p2,…,pA です。
あなたは B 個の緑色のリンゴを持っており、美味しさはそれぞれ q1,q2,…,qB です。
あなたは C 個の無色のリンゴを持っており、美味しさはそれぞれ r1,r2,…,rC です。
無色のリンゴは食べる前に着色することで、赤色のリンゴもしくは緑色のリンゴと見なすことができます。
以上のリンゴの中から、できるだけ美味しさの総和が大きくなるように食べるリンゴを選びます。
0 個以上の無色のリンゴに適切に着色したとき、食べる X+Y 個のリンゴの美味しさの総和が最大でいくつになるか求めてください。
制約
- 1≤X≤A≤10^5
- 1≤Y≤B≤10^5
- 1≤C≤10^5
- 1≤pi≤10^9
- 1≤qi≤10^9
- 1≤ri≤10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y A B C
p1 p2 … pA
q1 q2 … qB
r1 r2 ... rC
出力
リンゴの美味しさの総和の最大値を出力せよ。
解説
赤いリンゴが A 個，緑のリンゴが B 個，赤と緑どちらとも見なせる無色のリンゴが C 個あり，この中から赤いリンゴを X 個，緑のリンゴを Y 個選び，その美味しさの最大値を求めよという問題です。
まずは赤いリンゴ，緑のリンゴ，無色のリンゴをそれぞれ美味しさの降順にソートしておきます。
すると，赤いリンゴは X 個しか選ばないので，最大でも赤いリンゴは X 個しかいりません。なので赤いリンゴの美味しさが X 番目より小さいものは捨てます。緑のリンゴも同様に Y 番目より小さいものは捨てます。
Python ではこれを以下のように実装できます。
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
p = p[:x]
q = q[:y]こうすることで，赤いリンゴが X 個，緑のリンゴが Y 個，無色のリンゴが C 個になりました。
あとはここから無色のリンゴを考慮して赤いリンゴを X 個，緑のリンゴを Y 個選べばよいのですが，例えば無色のリンゴの一番おいしいものの値が，赤いリンゴの一番おいしくないものの値よりも小さいとします。
このとき，赤いリンゴの一番おいしくないものを捨てて，無色のリンゴの一番おいしいものを赤いリンゴとみなせば，結局赤いリンゴを X 個選んだことになります。
これより，現在残っている赤いリンゴ X 個，緑のリンゴ Y 個，無色のリンゴ C 個 のなかから，最もおいしいものを上から X+Y 個選んで，その値の合計を出力してやればよいです。
従って，まず残りのリンゴをすべて合わせたリスト pqr を用意し，それを降順にソートして，上位 X+Y 個の値の合計値を出力します。
では，解答例を載せておきます。
解答例
x,y,a,b,c = map(int ,input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
p = p[:x]
q = q[:y]
pqr = p + q + r
pqr.sort(reverse=True)
yamm = sum(pqr[:x+y])
print(yamm)
いかがだったでしょうか。
コード自体は複雑な操作をしておらず，いたって簡単なものとなっていますが，解答するまでの考え方が難しいというような問題でしたね。
もし少しでも参考になったら，twitter でシェアをお願いします！
それでは！
