card game for twoという問題を解いたのでメモ。

どこがポイントなのかとかも記載する。

問題の内容

1枚以上のN枚のカードがあって、カードには数字が書いてある。アリスとボブが、アリス→ボブの順に1枚ずつ、交互にカードをとっていく。このとき、アリスとボブがとるそれぞれカードは、書かれている数字の和が最大になるようにカードをとっていく。カードを最後までとったら、アリスはボブより何点多く得点できるかを出力する。

解答

N枚のカードの枚数を格納する変数をNとする。
Nを入力から受け取り変数Nに格納する。
N枚のカードを格納する配列sを準備する。
カードの数字を入力から受け取り配列sに格納する。
sに格納したカードを数字の大きい順にソートする。
ソート関数を実行すると数字の小さい順に並ぶので、これをリバース関数で逆にして、大きい順に並べる。
アリスとボブが交互にカードをとるので、大きい順に並べたカードを交互にとることでそれぞれカードの数字の和を最大にできる。
アリスがとるカードを入れる配列をsum_aとする。
ボブがとるカードを入れる配列をsum_bとする。
ループを使って配列sに格納しているカードをそれぞれの配列に入れていく。
アリス→ボブの順に交互にカードをとるので、アリスがカードを入れる順番は奇数になる。ボブは偶数になるので、ループのカウンタが奇数のときはsum_aにカードを入れ、偶数のときはsum_bに入れるようにする。偶数は2で割った余りが0なのを利用する。奇数は2で割った余りが1なのを利用する。
最後までカードを格納したら、sum_a - sum_bを出力する。

カードが1枚の時はそのままカードに書かれている数字を出力することが最大値の出力になる。上記の処理と根本的に異なるので、カードが1枚のときと1枚ようにする。以上のときで処理を分けるようにする。

以上のような文章を作成し、ソースコードを作成、入出力のテストをして提出したソースコードは下記。

#include <bits/stdc++.h>
using namespace std;
int main() {
       int N;
       cin >> N;
       vector<int> s(N);
       for(int i = 0; i < N; i++){
               cin >> s.at(i);
       }
       if(N == 1){
               cout << s.at(0) << endl;
       }
       sort(s.begin(), s.end());
       reverse(s.begin(), s.end());
       int sum_a = 0;
       int sum_b = 0;
       if(N > 1){
               for(int i = 0; i < N; i++){
                       if(N > 1 && i%2 == 0){
                               sum_a += s.at(i);
                       }
                       if(N > 1 && i%2 == 1){
                               sum_b += s.at(i);
                       }
               }
               cout << sum_a - sum_b << endl;
       }
       return 0;
}

vector、sort、reverseといったSTLを使うことで問題がだいぶ解きやすくなったことを実感しています。stlを活用することで自分で実装するよりも予期せぬバグとかも起こりにくくなる気がするので、atcoderで問題を解くときにSTLをどんどん活用していきたいと思います。