AtCoderをPythonで取り組んだ振り返り(ABC437 A~C)

どうもこんにちは！

今週のコンテストはCまで完答、振り返りもCまで。
Dは素直に実装するともちろんTLEで計算量の落とし方がわからず。解説を見るに累積和を使うところまではできていたんですが2分探索でa-bが正の値になるか負の値になる境界を見つけることができてなかったです。

問題と公式の解説のリンク

問題は以下のリンクから。

A - Feet -

問題

与えられた整数a,bを使って、aフィートbインチは何インチかを回答する問題。

考え方とコード

単純に計算した結果を出力。

a,b = map(int,input().split())
print(a*12+b)

B - Tombola -

問題

要素数がwの整数列がh個あるとします。
与えられるn個の整数が整数列ごとに何個含まれているか数え、その最大値を出力する問題。
例えば整数列が1, 2, 3, 4、与えられた整数が2,3,5の3個だとすると、この整数列に含まれる個数は2個となります。

考え方とコード

与えられた整数が整数列ごとに含まれるかを確認して、最終結果のうち最大の数を出力するとしました。

h,w,n = map(int,input().split())
g = []
for _ in range(h):
    tmp = list(map(int,input().split()))
    g.append(tmp)

ans = [0] * h
for _ in range(n):
    b = int(input())
    for i in range(h):
        if b in g[i]:
            ans[i] += 1

print(max(ans))

C - Reindeer and Sleigh 2 -

問題

n匹のトナカイと1個のソリがあるとし、トナカイをソリを引く役とソリに乗る役に分けて、ソリを動かすことを考えます。
トナカイ1匹ごとに重さwと力pが与えられます。ソリを引くトナカイの力の総和がソリに乗っているトナカイの重さの総和以上のときに動かせるとすると、最大何匹のトナカイを乗せられるかを出力する問題。
なお1つの問題で複数のテストケースが与えられ、テストケースごとにトナカイの匹数とそれぞれのw,pが与えられます。

考え方とコード

wとpの総和が大きいほどソリを動かすことに対しての影響が大きいので、最初は全員ソリに乗った状態から総和が大きいトナカイから順にソリを動かす役に移して条件を満たすかを確認するようにしました。
実装に当たってはトナカイのリストをw+pが大きい順にソートして処理をしています。

t = int(input())

for _ in range(t):
    n = int(input())
    reindeer = []
    wtotal,ptotal = 0, 0
    ans = n
    
    for _ in range(n):
        w,p = map(int,input().split())
        reindeer.append((w,p))
        wtotal += w

    reindeer.sort(reverse=True,key=lambda x:x[0]+x[1])
    for i in range(n):
        ptotal += reindeer[i][1]
        wtotal -= reindeer[i][0]
        ans -= 1
        if ptotal >= wtotal or ans == 0:
            break
        
    print(ans)

2025年のコンテストの参加は今回が最後。次回は1/10のコンテストからの予定です。
ではでは。