【Python】AtCoder Beginner Contest 121 A,C問題解答・解説

A問題 White Cells
C – Energy Drink Collector

A問題 White Cells

H,W = map(int, input().split())
h,w = map(int, input().split())

print((H-h)*(W-w))

H,W = map(int, input().split())

h,w = map(int, input().split())

print((H-h)*(W-w))

C – Energy Drink Collector

方針

M本のドリンクを購入したい。i番目の店ではA円のドリンクをB本購入できる。

M本購入するために必要な最小金額を求める問題。

入力値の内、Aは値段、Bはその店で購入できるドリンクの本数になる
[A,B]、つまり[値段、本数]となるようにリストを作る
値段の小さい順にソートする
購入本数がM本になるまで、値段の小さい順から値段×本数を合算する
numに購入した数を保存し、ansに購入金額を保存している

解答

n,m=map(int,input().split())
A=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,b])                 #[値段、本数]のリスト
A.sort()                          #先頭の要素が値段なので、何も指定しなくても値段の小さい順にソートされる
num=0                             #購入本数
ans=0                             #購入金額
for i in range(n):                #[3]
  if m>num+A[i][1]:               #[1] 購入したいM本が、(これまでの購入本数)＋(i番目のお店で購入できる本数)より大きい場合
    ans += A[i][0]*A[i][1]        #ansに値段×本数を加える
    num += A[i][1]                #購入本数を加える
  else:                           #[2]購入したいM本よりも、(これまでの購入本数)＋(i番目のお店で購入できる本数)が大きい場合
    ans += A[i][0]*(m-num)        #値段×(M本-これまでの購入本数)、つまり値段×残り本数をansに加える
    print(ans)
    exit()

n,m=map(int,input().split())

A=[]

for i in range(n):

a,b=map(int,input().split())

A.append([a,b]) #[値段、本数]のリスト

A.sort() #先頭の要素が値段なので、何も指定しなくても値段の小さい順にソートされる

num=0 #購入本数

ans=0 #購入金額

for i in range(n): #[3]

if m>num+A[i][1]: #[1] 購入したいM本が、(これまでの購入本数)＋(i番目のお店で購入できる本数)より大きい場合

ans += A[i][0]*A[i][1] #ansに値段×本数を加える

num += A[i][1] #購入本数を加える

else: #[2]購入したいM本よりも、(これまでの購入本数)＋(i番目のお店で購入できる本数)が大きい場合

ans += A[i][0]*(m-num) #値段×(M本-これまでの購入本数)、つまり値段×残り本数をansに加える

print(ans)

exit()

[1]i番目のお店のドリンクを全て購入してもM本に届かない場合

Bはその店でできる本数の上限です。

これまでの購入本数とBを足した数が、購入したいM本よりも小さければ、

i番目のお店でのドリンクの値段×本数をansに加えています。

[2]i番目のお店のドリンクを全て購入するとM本以上になる場合

i番目のお店で購入できるドリンクの数と、これまでの購入本数を合計するとM本を超えてしまう場合です。

(M本)-(これまでの購入本数)がi番目のお店で買わなければならない本数となります。

その値段を加えて、printで出力し、exit()でプログラムを終了します。

[3]ループ回数の設定について

問題文より、与えられた入力で必ずM本のドリンクを買うことができるとあるので、ループの最大値はお店の数、つまりn回数となります。

実際には1つのお店で複数本のドリンクを購入できるので、すべてのお店を回る前に必要な本数を購入できてしまうことが多いです。

そのため、[2]で必要な本数がそろったときにはexit()でプログラムを終了しています。