問題: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; } } } } }