JOI 予選 2008 C - カードゲーム(AOJ 0523) (5Q, 難易度 4)

ちょっと実装が大変なので、頑張って実装しよう！

• 問題へのリンク

問題概要

太郎君と花子さんが大富豪を模したゲームをする。

の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のようなゲームをする。最初の手番は太郎君である。

• 手番の者が持っているカードのうち、最小の数の書かれたカードを場に出す
• それ以降は、手番が移っていき、自分の持っているカードのうち、場に出ている最新のカードの数よりも大きいような、最小の数の書かれたカードを出す
  • 出せない場合はパスとし、場に出ているカードはなくなった上で、手番が入れ替わる
• 太郎君または花子さんのいずれかの手持ちのカードがなくなった瞬間にゲームを終了する

ゲームが終了したときに、相手の持っているカードの枚数が、そのプレイヤーの得点となる。太郎君と花子さんのゲーム終了後の得点を求めよ。

制約

• 

考えたこと

制約における の上限値が 100 と小さいので、愚直な実装で構わない。だが、その愚直な実装が案外難しい。ここでは、次のような関数を定義することにした（C++）。

// cards の数のうち、aite よりも大きい最小の数を返す（存在しない場合は 0 を返す）
// cards から、その数を除去する（存在しない場合は何もしない）
int choose(vector<int> &cards, int aite = 0) {
    int res;
    for (int i = 0; i < cards.size(); i++) {
        if (cards[i] > aite) {
            res = cards[i];
            cards.erase(cards.begin() + i);
            return res;
        }
    }
    return 0;
}

ここで、引数 cards に対しても「場に出したカードの数を除去する」という操作を行うため、参照渡しにしている。

このような関数を用意しておけば、シミュレーションは比較的簡単に書ける。パスする場合であっても「相手が 0 という数のカードを場に出した」とみなすこととする（ただし、手持ちのカードの枚数は減らない）。そうすれば、パスした次の手番のプレイヤーの視点では「自分の手持ちの最小の数のカードを出せば良い」ということになる。

コード

#include <bits/stdc++.h>
using namespace std;

// cards の数のうち、aite よりも大きい最小の数を返す（存在しない場合は 0 を返す）
// cards から、その数を除去する（存在しない場合は何もしない）
int choose(vector<int> &cards, int aite = 0) {
    int res;
    for (int i = 0; i < cards.size(); i++) {
        if (cards[i] > aite) {
            res = cards[i];
            cards.erase(cards.begin() + i);
            return res;
        }
    }
    return 0;
}

int main() {
    int N;
    cin >> N;
    vector<int> taro(N), hanako;
    for (int i = 0; i < N; i++) cin >> taro[i];
    sort(taro.begin(), taro.end());
    for (int i = 1; i <= N * 2; i++) {
        // 1, 2, ..., 2N のうち taro に含まれないものを hanako に挿入する
        if (find(taro.begin(), taro.end(), i) == taro.end()) hanako.push_back(i);
    }

    bool is_taro_turn = true;
    int num = 0;
    while (!taro.empty() && !hanako.empty()) {
        if (is_taro_turn) {
            num = choose(taro, num);
            is_taro_turn = false;
        } else {
            num = choose(hanako, num);
            is_taro_turn = true;
        }
    }
    cout << hanako.size() << endl;
    cout << taro.size() << endl;
}