AtCoder Beginners Selection ABC088B – Card Game for Twoをpythonで解いてみた

本サイトABC088B – Card Game for Twoへは以下から

問題:Card Game for Two

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

制約

  • N は 1 以上 100 以下の整数
  • ai(1≤i≤N)は 1 以上 100 以下の整数

入力

入力は以下の形式で標準入力から与えられる.

N
a1 a2 a3 ... aN

出力

両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

入力例 1

2
3 1

出力例 1

2

最初, Alice は 3 が書かれたカードを取ります. 次に, Bob は 1 が書かれたカードを取ります. 得点差は 3 – 1 = 2 となります.

入力例 2

3
2 7 4

出力例 2

5

最初, Alice は 7 が書かれたカードを取ります. 次に, Bob は 4 が書かれたカードを取ります. 最後に, Alice は 2 が書かれたカードを取ります. 得点差は, 7 – 4 + 2 = 5 点となります.

入力例 3 

4
20 18 2 18

出力例 3

18

解答例

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

cards.sort(reverse=True)

alice_score = 0
bob_score = 0

for i in range(N):
    if i % 2 == 0:
        alice_score += cards[i]
    else:
        bob_score += cards[i]

print(alice_score - bob_score)

解説

この問題は、AliceとBobが最大の得点を目指してカードを選ぶというシナリオを考えるものです。最適な戦略とは、常に最も大きな数が書かれているカードを選ぶことです。したがって、最初にカードを降順にソートし、交互にカードを選ぶことで、この戦略をシミュレートできます。

以下は、この問題を解くためのアプローチです。

  • 入力の受け取り:
    • int(input())を使用して、カードの枚数Nを受け取ります。
    • list(map(int, input().split()))を使用して、各カードに書かれている数のリストaを受け取ります。
  • カードのソート:
    • リストaを降順にソートします。
  • 得点の計算:
    • AliceとBobの得点を初期化します。
    • ソートされたリストaを順番に処理し、AliceとBobが交互にカードを選ぶようにします。Aliceが最初にカードを選び、次にBobが選びます。このプロセスをリストの終わりまで繰り返します。
  • 結果の出力:
    • Aliceの得点からBobの得点を引いた結果を出力します。

以下は、このアプローチを実装したPythonのコードです。

# 入力の受け取り
N = int(input())
a = list(map(int, input().split()))

# カードを降順にソート
a.sort(reverse=True)

# 得点の計算
alice_score = sum(a[i] for i in range(0, N, 2))
bob_score = sum(a[i] for i in range(1, N, 2))

# 結果の出力
print(alice_score - bob_score)

次の問題へ

前の問題へ

一覧へ

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

この記事を書いた人

雇われのシステムエンジニアです。
普段は車載ECUのセキュリティー分野に従事しております。

■保有資格
Salesforce 認定 Platform アプリケーションビルダー
Salesforce 認定 Platform デベロッパー

コメント

コメントする

目次