競技プログラミング

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

プログラミング

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

 

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

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

 

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

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

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

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

身につくスキル
  • sort() の使い方
  • スライスの使い方

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

 

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] と出力する

 

6問目「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 より何点多く取るかを出力してください。

ABC088B – Card Game for Twoより引用

 

入力例と出力例

入力例

5
10 40 20 50 30

出力例

30

2人が自分の得点を最大化するようにカードを取ったら、Alice は「50、30、10」を、Bob は「40、20」のカードを取ります。

つまり、Alice の得点は90点、Bob の得点は60点です。

この場合は、Alice は Bob より30点多く取っているので、「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]))

 

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

まとめ

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

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

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です