AtCoder Beginner Contest 121 過去問 (A~C)

参照

atcoder.jp

A問題

2分くらい。

H,W = map(int, input().split())
h,w = map(int, input().split())
print(H*W-(H*w+W*h-h*w))

B問題

3~5分くらい。

n,m,c = map(int, input().split())
b = list(map(int, input().split()))
a = [list(map(int, input().split())) for j in range(n)]
 
count_ = 0
for i in range(n):
  sum_=0
  for j in range(m):
    sum_+=a[i][j]*b[j]
  if sum_>-c: count_+=1
print(count_)

C問題

目的の本数のジュースを購入するのに最小となる値段を求めます。
最初、Sort(ソート)は二重ループという勘違いをしていたせいで、
Sortを用いないアルゴリズムを模索していたのですが、
どうしても思いつかず・・・。50分経過。。。

調べるとSortの計算量はO(nlog(n))です。
qiita.com

1≤N,M≤10**5なので,
O(nlog(n))の計算量にはTLEにもならず済みます。
Sortが使えるとなるとアルゴリズムはパッと思い浮かびました。

計算量の復習はしっかりしておかないと本番で痛い目に合います・・・。

n,m = map(int, input().split())
a_b = [list(map(int, input().split())) for i in range(n)]
 
a_b.sort()
sum_,all_ = m,0
for j in range(n):
  if sum_>=a_b[j][1]:
    sum_-=a_b[j][1]
    all_+=a_b[j][1]*a_b[j][0]
  elif sum_<a_b[j][1]:
    all_+=sum_*a_b[j][0]
    sum_-=sum_
print(all_)