AGC018B Sports Festival

問題概要

 
N人がM種類のスポーツについて好きな順位を持っています。

参加者は、スポーツ大会が開かれた場合に一番好きなスポーツのみに参加します。

参加者が最大になるゲームの参加者の最大値が最小になるように実施するゲームを設定する問題です。

考察

いろいろ考えましたが自力では解法に辿り着けず解説ACです。

全ゲームを実施する場合に最多参加者となるゲームを調べ、次にそのゲーム以外のゲームを実施した場合の最多参加者となるゲームを調べ、というように順にすべてを調べます。

やり方がわかれば実装はできました。

実装では、各人毎の好きな順のゲームの配列　N.1　～　N,M の最初にくるゲームに参加するとして参加者をカウントします。

最大参加者のゲームが決まったら、配列中のそのゲームのところを－１にして、カウントする際に飛ばすようにしました。

提出コード

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

int N,M;
int FS[310][310];
vector<int>K;

int main(){
cin>>N>>M;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin>>FS[i][j];
}
}
for(int i=1;i<=M;i++){
K.push_back(i);
}
int eachmaxcnt=0;
int maxcnt=300;
int C[310];
int temp=0;

//ゲームの種類分回す
for(int i=0;i<M;i++){

//各ゲームの参加者数を初期化
for(int i=1;i<=M;i++){
C[i]=0;
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
//最初にでてくるゲームの参加者を加算
if(FS[i][j] != -1){
C[FS[i][j]]++;
break;
}
}
}

//最大参加者数を求める
eachmaxcnt=0;
for(int i=1;i<=M;i++){
if(eachmaxcnt<C[i]){
eachmaxcnt=C[i];
temp=i;
}
}

//最大参加者数の更新
maxcnt=min(maxcnt,eachmaxcnt);

//最大参加者のゲームを-1にする
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(FS[i][j]==temp){
FS[i][j]=-1;
} 
}
}
}

cout<<maxcnt<<endl;
return 0;
}

その他

最初はゲーム数を減らしていくときに残っているゲームの配列をもって一つづつ減らしていくことを考えていました。
この方法でもできましたが少し冗長です。

もっともこのやり方を考える中でvectorの特定の要素を削除する方法を新たに学びました。

vector<int>K;
  for(int i=1;i<=M;i++){
    K.push_back(i);
  }

  for(int i=1;i<=M;i++){
    K.push_back(i);
  }

 while(K.size() !=0){

　//処理　最大参加者のゲームをtempで持つ
　//配列の中でtempと一致する要素を削除する
    K.erase(remove(K.begin(),K.end(),temp),K.end());
  }