【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【６問目】

こんにちは！サトシです！

 

この記事では、「AtCoderに登録して最初に解くべき１０問（AtCoder Beginners Selection）」の６問目「Card Game for Two」をめちゃくちゃ分かりやすく解説していきます。

 

それでは、「Card Game for Two」の解説をしていきます！

【競プロ】最初に解くべき過去問１０問をPythonで分かりやすく解説します！【AtCoder】こんにちは！サトシ（@satoshi365_blog）です！ この記事では、「競技プログラミング（AtCoder）に登録し...

６問目「Card Game for Two」で身につくスキル

この問題では、こんなスキルが身につきます。

先に、これがどのようなスキルなのかを説明します。

 

sort() の使い方

sort() を使うと、リストの中の数値や文字列を並び替えることができます。

例えば、このように書くと、リスト [1, 4, 2, 3] を小さい順に並び替えられます。

a = [1, 4, 2, 3]
a.sort()
print(a)   #[1, 2, 3, 4] と出力

 

また、下のように書くと、大きい順に並び替えることもできます。

a = [1, 4, 2, 3]
a.sort(reverse=True)
print(a)   #[4, 3, 2, 1] と出力

 

スライスの使い方

スライスを使うと、リストから要素を自由に取り出せます。

例えば、下のように書くと、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] の [7, 8, 9] だけを取り出せます。

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(a[6:9])   #[7, 8, 9] と出力

 

また、a[6:] や a[:3] のように数字を省略すると、最後（または最初）まで取り出せます。

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(a[6:])   #[7, 8, 9, 10] と出力
print(a[:3])   #[1, 2, 3] と出力
print(a[:])   #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] と出力

 

a[1:8:2] のように書くと「1つ飛ばしで取り出す」こともできます。

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(a[1:8:2])   #[2, 4, 6, 8]と出力

# a[1:8] は [2, 3, 4, 5, 6, 7, 8] と出力する

 

６問目「Card Game for Two」の解説

この順番で解説していきます。

それでは見ていきましょう。

 

問題文

 

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

制約
・N は 1 以上 100 以下の整数
・a_i ( 1 ≤ i ≤ N ) は 1 以上 100 以下の整数

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

N
a₁ a₂ a₃ … a_N

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

ABC088B – Card Game for Twoより引用

 

入力例と出力例

入力例

出力例

２人が自分の得点を最大化するようにカードを取ったら、Alice は「５０、３０、１０」を、Bob は「４０、２０」のカードを取ります。

つまり、Alice の得点は９０点、Bob の得点は６０点です。

この場合は、Alice は Bob より３０点多く取っているので、「30」を出力します。

 

解答例

n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

解説

大きい順に並べると、Alice が取るカードは [::2]、Bob が取るカードは [1::2] となることを使って解いていきます。

 

例えば、[10, 40, 20, 50, 30] というカードを大きい順に並び替えると、[50, 40, 30, 20, 10] になります。

Alice と Bob は交互にカードを取っていくので、Alice が取るカードは [50, 30, 10]、Bob が取るカードは [40, 20] です。

[50, 30, 10] は [::2]、[40, 20] は [1::2] と書けば取り出せるのです。

 

では、コードを詳しく解説していきます。

 

まずは、n を受け取ります。そして、a を全部リストで受け取ります。

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

 

数字が大きい順にカードを並び替えます。

a.sort(reverse=True)

 

sum(a[::2]) で Alice が取ったカードの数の合計を求めます。同じように、sum(a[1::2]) で Bob が取ったカードの数の合計を求めます。

Alice の得点から Bob の得点を引けば、「Alice は Bob より何点多く取るか」がわかります。

print(sum(a[::2]) - sum(a[1::2]))

 

 

まとめとして、もう一度プログラムを確認してみましょう。

n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

 

これで「２人が最適な戦略を取った時に、Alice が Bob より何点多く取るか」を求めることができました。

まとめ

もし分からない点などありましたら、気軽にTwitterなどでご質問ください＾＾

少しでも参考になれば嬉しいです！