AtCoder ABC 167 B – Easy Linear Programming Python解説

2021年12月25日

スポンサーリンク

Easy Linear Programming

1 が書かれたカードが A 枚、0 が書かれたカードが B 枚、 -1 が書かれたカードが C 枚あります。
これらのカードから、ちょうど K 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最大値はいくつですか。

AtCoder Beginner Contest 「Easy Linear Programming」

問題を見て、累積和で解こうと思っていたのですが、入力例3の実行時間が掛かりすぎて諦めました。
そういうわけで、Kの大きさで場合分けをしていきます。

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

if k <= a:
    print(k)
    
elif a < k <= a + b:
    print(a)
    
else:
    print(a - (k - (a + b)))

カードの数の和が最大値になるには、1が書かれたAのカード、Bのカード、Cのカードの順に取っていった場合です。あとはKの枚数で場合分けをしていきます。

Kの枚数がAのカード枚数より少なければ答えはK。同様に、Kの枚数がA枚以上、A+B枚以下なら答えはA(Bのカードの数字は0の為)。
そして、Kのカード枚数がA+B以上、A+B+C以下なら、A – ( K – ( A + B ) )が答えになります。

AtCoderB問題

Posted by cheese