AtCoderログ：0053 - ABC 088 B

問題

問題文

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

制約

・$N$ は $1$ 以上 $100$ 以下の整数
・$a_i~(1 \le i \le N)$ は $1$ 以上 $100$ 以下の整数

収録されている問題セット

• AtCoder に登録したら次にやること [第06問]

• AtCoder Beginners Selection

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #010

回答

回答1 (AC)

このゲームでは、自分が取ったカードの数の合計が自分の得点になるので、「最適な戦略」のもとでは、Alice も Bob もその時の場にある最大の値が書かれたカードを取ります。カードの値を配列 a() で受け取った後、これを大きい順 (降順) にソートすると、0 番目のカードは Alice、1 番目のカードは Bob、2番目のカードは Alice、3番目のカードは Bob ...が取ることになるので、それぞれの得点の合計を計算し、最後にその差を出力すれば良いでしょう。コードは以下のようになりました。

abc088b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }

  sort( a.rbegin(), a.rend() );

  int ascore = 0, bscore = 0;
  for ( int i=0; i<n; i++ ) {
    if ( i%2==0 ) {
      ascore += a.at(i);
    } else {
      bscore += a.at(i);
    }
  }
  cout << ascore-bscore << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

こちらも回答と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0052 - ABC 212 B