本サイト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)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/06/Python-300x169.png)
次の問題へ
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/09/atcoder-300x254.png)
前の問題へ
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/09/atcoder-300x254.png)
一覧へ
![](https://tysonblog-whitelabel.com/wp-content/uploads/2021/09/atcoder-300x254.png)
コメント