POJ 1323 Game Prediction

問題

N人にM枚ずつカードが配られる。カードには1〜N*Mまでの数字が書かれており、重複はない。各人は毎ターン一枚のカードを場に出し、一番数字の大きいカードを出した人がそのターンの勝ちになる。あなたに配られたカードがわかっているとき、あなたが最低何回勝てるか求めよ。

やりかた

N人でゲームをやっているというよりも、自分のカード以外のカードをすべて持っている一人のプレイヤーと勝負すると考えたほうがわかりやすい。

まず手持ちのカードで一番大きいものから出して行って、出した時点でそれより大きいカードを相手が持っているなら負け、持っていなければ勝ちと数えていけばいい。

以下ソース。

int main(int argc, char **argv){
  int N, M, round = 0;
  while(cin >> N >> M, N + M){
    round++;
    vector<int> mine, others;
    for(int i = 0; i < M; i++){
      int a;
      cin >> a;
      mine.push_back(a);
    }
    sort(mine.rbegin(), mine.rend());

    for(int i = N * M; i >= 0; i--)//自分のカード以外を列挙する
      if(count(ALL(mine), i) == 0)
	others.push_back(i);

    int cnt = 0, opp = 0;
    for(int i = 0; i < M; i++){
      if(mine[i] > others[opp])//自分の最も大きいカードが相手のそれを上回る場合
	cnt++;
      else//自分の最も大きいカードが相手のそれを下回る場合、相手はそのカードを使う
	opp++;
    }
    cout << "Case " << round << ": " << cnt << endl;
  }
  return 0;
}