こんにちは!(^^)!
今回は、AtCoder Beginners Selectionの７問目、Card Game for Twoの解説をしていきたいと思います！
Card Game for Two
【問題文】
N枚のカードがあります。i枚目のカードにはa¡という数が書かれています。AliceとBobは、これらのカードを使ってゲームを行います。ゲームでは、AliceとBobが交互に1枚ずつカードを取っていきます。Aliceが先にカードを取ります。2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
【制約】
・Nは1以上100以下の整数
・a¡(1≦¡≦N)は1以上100以下の整数
【入力】
入力は以下の形式で標準入力から与えられる。
N
a₁ a₂ a₃ ・・・ 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点となります。
【解答例】
N=int(input())
A=list(map(int,input().split()))
A.sort()
Alice=0
Bob=0
for i in range(N//2+1):
try:
Alice+=A.pop()
Bob+=A.pop()
except:
pass
ans=Alice-Bob
print(ans)それでは解説していきます！
まず1行目でカードの枚数をNに代入し、2行目ですべてのカードの数をリストAに代入しています。ここで使用しているmap()関数については、AtCoderに挑戦しよう①で詳しく解説していますので、復習したい方はこちらからご覧ください！
リストAに格納されている値は順番がバラバラであるため、sort()関数を使って昇順に並び替えをしています。sort()関数では、引数に何も設定しなければ昇順に、(reverse=True)を設定すれば降順にリストを並び替えることができます。
そして、AliceとBobの得点の初期値、0点を設定します。
その次のfor文では、例外処理を組み込んでコードを書いています。
この繰り返し処理では、pop()を用いてリストAから値を取り出し、AliceとBobの得点に追加していくという処理をしています。pop()については、この記事の最後で解説をしているので、そちらもぜひご覧ください！
繰り返し回数を表すrange()の引数には、(N//2+1)を入力しています。一度の繰り返しにつきAliceとBobの2回リストAから値を取り出すので、Nの半分の回数だけ繰り返せばよいのですが、Nが奇数の場合、最後の値がリストに残ってしまうため、(N//2+1)としています。
しかし、range()の引数を(N//2+1)とした場合、Nが偶数だった時、最後の繰り返しの時はすでにリストAは空であるので、AliceとBobに追加する値がなく、エラーとなってしまいます。また、Nが奇数の時も、最後の繰り返し時はBobに追加する値がなくエラーとなります。
そこで、例外処理try~exceptを用います。
例外処理では、エラーが起きる可能性のあるコードをtryの後に書くことで、もしエラーが起きた場合、エラーを表示するのではなく、その場合の処理をexcept後のコードで指定することができます。
今回は、エラーを表示させたくないだけなので、exceptの後にはpassとだけ入力しています。
こうして、入力されたカードの数をすべてAliceとBobに順番に追加することができました。最後に、AliceからBobの値を引いて二人の得点の差を出し、print()によって出力すれば完了です。
pop()
今回の問題で用いたpop()メソッドの解説をしたいと思います。
pop()を用いることによって、箱から物を取り出すようにリストから要素を抜き取ることができます。書式は以下の通りです。
リスト.pop(抜き取る位置)この抜き取る位置には、そのリストのインデント番号を入力します。また、引数を省略すると末尾の要素を抜き取ります。以下に例を示します。
>>> animals=["dog","cat","cow","sheep"]
>>> pet=animals.pop(1)
>>> pet
'cat'
>>> animals
['dog', 'cow', 'sheep']ここでは、animalsというリストのインデント番号1の要素、つまり”cow”をpop(1)によって取り出して、petに代入しています。要素を取り出したため、元のanimalsから”cow”の要素が消えています。
終わりに
いかがでしたか？
AtCoder Beginners Selectionももう半分を超えているので、もう少し頑張っていきましょう！
ではまた(^^)/
次の記事