AtCoder Beginner Contest 121 過去問 (A~C)
参照
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_)