Codeforces #55 (div2) D "Team Arrangement"

問題:http://codeforces.com/problemset/problem/59/D

ラクティス.

チーム数,各人のスコアによる順位,決定後のチーム編成および優先順位を求めるべき人が与えられる.ある集団を3人1組のチームに分けるとき,まず,スコアが高かった順に,1.リーダーを決める,2.リーダーが持つ優先順位にしたがって残りの2人を決定する,という手順を用いる.このとき,指定された人の優先順位を求める.

優先順位を求めるべきチームを編成中チームとする.まず,各チームのリーダー以外はリーダーが持つ優先順位によって自動的に編成されるため,優先順位は任意である.次に,リーダーの優先順位を求めるとき,編成済チームは編成中チームに影響を与えない.どこにあろうと選択できないからである.同時に,編成前チームに含まれる人たちは編成中チームに含まれる人たちよりも後でなければならない.よって,編成済の人たち,編成中の人たち+編成前の人たちをそれぞれソートして小さい順番にマージすることで,辞書順で最初となる優先順位を求めることができる,らしい.wikipediaの安定結婚問題の項目にあるGale-Shapleyアルゴリズムみたいなもの?

コード

import java.util.*;

// copy
public class D_TeamArrangement {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(), teamNum = 3, memberNum = n * teamNum;
		int[] r = new int[memberNum + 1];
		for (int i = 0; i < memberNum; ++i) {
			r[s.nextInt()] = i;
		}
		int[][] teams = new int[n][teamNum];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < teamNum; ++j) {
				teams[i][j] = s.nextInt();
			}
		}
		int k = s.nextInt();
		l: for (int i = 0; i < n; ++i) {
			for (int j = 0; j < teamNum; ++j) {
				if (teams[i][j] == k) {
					int result[] = new int[memberNum - 1];
					boolean isMax = true;
					for (int jj = 0; jj < teamNum; ++jj) {
						if (r[teams[i][jj]] < r[teams[i][j]]) {
							isMax = false;
						}
					}
					if (!isMax) {
						for (int ii = 1; ii < memberNum; ++ii) {
							result[ii - 1] = ii < k ? ii : ii + 1;
						}
					} else {
						int a[] = new int[i * teamNum];
						for (int ii = 0, p = 0; ii < i; ++ii) {
							for (int jj = 0; jj < teamNum; ++jj) {
								a[p++] = teams[ii][jj];
							}
						}
						int b[] = new int[(n - i) * teamNum - 1];
						for (int ii = i, p = 0; ii < n; ++ii) {
							for (int jj = 0; jj < teamNum; ++jj) {
								if (teams[ii][jj] != k) {
									b[p++] = teams[ii][jj];
								}
							}
						}
						Arrays.sort(a);
						Arrays.sort(b, 0, teamNum-1);
						Arrays.sort(b, teamNum-1, b.length);
						for (int p = 0, ap = 0, bp = 0; p < result.length;) {
							result[p++] = bp >= b.length
									|| (ap < a.length && a[ap] < b[bp]) ? a[ap++]
									: b[bp++];
						}
					}
					System.out.println(Arrays.toString(result).replaceAll(
							"[\\[\\],]", ""));
					break l;
				}
			}
		}
	}
}