AtCoder ABC 088 B – Card Game for Two Python解説

スポンサーリンク

Card Game for Two

N 枚のカードがあります.i 枚目のカードには,ai という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.

2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

AtCoder Beginner Contest 「Card Game for Two」

問題文にある最適な戦略とはカードの数が大きい順に取ったときということです。
なので今回やるべきことは、カードを大きい順に並べ替える、Aliceから交互にカードを取る、AliceとBobの合計点の差を求めることになります。

n = int(input())
a = list(map(int, input().split()))

a = sorted(a, reverse=True)

alice = 0
bob = 0

for i in range(n):
    if i % 2 == 0:
        alice += a[i]
    else:
        bob += a[i]
        
print(alice - bob)

カードを大きい順に並べ替えるにはソートをreverse=Trueにすることで降順にすることができます。
続いてif文でAliceが最初にカードを取るようにし、カードの点を足していきます。

最後にAliceとBobの合計点の差を求めて完了です。