Code Formula 2014 予選A : C - 決勝進出者

なかなか面白い問題だった。
http://code-formula-2014-quala.contest.atcoder.jp/tasks/code_formula_2014_qualA_c

問題

大量の人間が参加する大会があり、N回の予選でK人の決勝進出者を選びたい。

N回の予選それぞれの上位K位のIDが与えられるので、以下の手順で決勝進出者を決める。

1. 予選順位が高い順に選ぶ。
2. 最高順位が同着の人が複数いたら、早い予選でその順位を取った方が優先される。
3. K人が確定するまで上記処理を繰り返す。

決勝進出確定者には、N回の予選完了を待たず確定した時点で進出したことを伝えたい。
N回の予選それぞれ終了段階で決勝進出が確定した人のIDを列挙せよ。

解法

i回目の予選でj位を取った人の総合順位をj*N+iと考えるとこの(j*N+i)の小さい順に上位K人を選べば上記進出者決定のアルゴリズムと一致する。
予選を行うたびに(j*N+i)位の位置にIDを埋め、上位K位に入っている人を決勝進出確定者として選べばよい。
決勝進出確定者がその後の予選でも上位入賞する可能性があるが、２回目以降の(j*N+i)位の登場は１人としてカウントしないようにしておく。

int N,K,L;
int MM[1000010];
int F[1000010];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K;
	L=K;
	
	
	FOR(i,N) {
		FOR(j,K) cin>>x,MM[j*N+i]=x;
		j=0;
		vector<int> NN;
		
		FOR(y,N*K) {
			if(F[MM[y]]==1) continue;
			if(++j>L) break;
			if(MM[y]>0) {
				NN.push_back(MM[y]);
				F[MM[y]]=1;
			}
		}
		sort(NN.begin(),NN.end());
		FOR(j,NN.size()) {
			_P("%d",NN[j]);
			if(j!=NN.size()-1) _P(" ");
		}
		_P("\n");
		L-=NN.size();
	}
}

まとめ

初めてのタイプの問題設定で楽しめた。