第7話 2人用カードゲーム

はじめに

　こちらでは，競技プログラミングコンテストサイトAtCoderの常設コンテスト「AtCoder Beginners Selection」に筆者が挑戦します．記事には，筆者が作成したコード(使用言語はPython)と簡単な解説を載せますので，プログラミング初心者の方の参考になれば幸いです．なお，この記事では，Pythonの詳細な文法については解説致しませんので，そちらに関しては関連記事および文献等を参照して頂きたく存じます．

問題(ABC088B - Card Game for Two)

　N 枚のカードがあります．i枚目のカードには，a_i という数が書かれています．Alice と Bob は，これらのカードを使ってゲームを行います．ゲームでは，Alice と Bob が交互に 1 枚ずつカードを取っていきます．Alice が先にカードを取ります．
2 人がすべてのカードを取ったときゲームは終了し，取ったカードの数の合計がその人の得点になります．2 人とも自分の得点を最大化するように最適な戦略を取った時，Alice は Bob より何点多く取るか求めてください．

コード(解答例)

N = int(input())
numbers = list(map(int, input().split()))

# バブルソート
for i in range(N):
    for j in range(N-i-1):
        if numbers[j] < numbers[j+1]:
            numbers[j], numbers[j+1] = numbers[j+1], numbers[j]

Alice_score = sum(numbers[::2])
Bob_score = sum(numbers[1::2])

print(Alice_score - Bob_score)

解説

　N枚のカードをリストとして表現し，降順にソートします．このようにすることで，リストのインデックスが偶数(0,2,4…)の要素はAliceが取るカードとなり，インデックスが奇数(1,3,5…)の要素はBobが取るカードとなります．スライスを用いて，AliceとBobそれぞれの得点を求め，最後に差を取ることで，求めるべき答えが得られます．