ABC149 B問題 Greedy Takahashiを解く
数学的問題として紹介されていたのでABC149 B問題を解いてみます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】 - Qiita
こちらの記事で数学的問題として紹介されていたので解こうと思いました。
高橋君は A 枚、青木君は B 枚のクッキーを持っています。
高橋君は以下の行動を K 回繰り返します。
もし高橋君がクッキーを 1 枚以上持っているなら、高橋君のクッキーを 1 枚食べる。
そうでなく、もし青木君がクッキーを 1 枚以上持っているなら、青木君のクッキーを 1 枚食べる。
高橋君も青木君もクッキーを持っていないなら、何もしない。
高橋君と青木君が最終的に持っているクッキーの枚数をそれぞれ求めてください。
計算量とか何も気にせずにKでループを回して解くと、ハマります。
Kは最大でって余裕で億を超えてるオーダーなので、普通に計算結果は返ってきません。
例えば、以下はハマるパターン。
A, B, K = list(map(int, input().split())) for _ in range(K): if A >= 1: A -= 1 continue if B >= 1: B -= 1 continue ans = " ".join([str(A), str(B)]) print(ans)
ちょっと考えると、ループ回さなくても計算すると導き出せることがわかります。
先にAのクッキーを消費するので、AとKの大きさを比較してKがAより小さければAのクッキーだけを消費して高橋くんのクッキーは(A - K)枚、青木くんのクッキーはそのままB枚。
KがAより大きければ、高橋くんのクッキーは0枚で、青木くんのクッキーはB - (K - A)枚。
の場合は高橋くんも青木くんもクッキーはなくなって0です。
A, B, K = list(map(int, input().split())) if A >= K: A = A - K print(f"{A} {B}") exit() K = K - A if B > K: B = B - K print(f"0 {B}") exit() print("0 0")