CODE FESTIVAL 2017 Final,I: Full Tournament

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_i

だいぶ時間使ったけどなんとか解けました。良問です。

順位表が求められればトーナメント上の順番は簡単に求まります。

順位表上でi番目がj番目よりも小さくならなければならない条件をi->jに辺を張った有向グラフG上で考えてみます。
Auを頂点uに書き込む値とすると、任意の辺e(v,u)についてAu < AvとなるようAを決めていく問題になりました。

ある頂点uから別のある頂点vへのpath上にある頂点の値cは、Au < c < Avを満たす必要があります。
すべてのpathとその上の頂点についてこの条件を求めれば、任意の頂点uについてAuはLu <= Au <= Ruでなければならない、つまりAuは(Lu, Ru)上になければならないのように、区間の形で条件が求まります。

そうしたら後はよくある点と区間を対応させる問題を解けば良くて(MlogM)(M=2^N)で計算できます。

こういう問題はやっぱり実験が大事ですね。でもただ実験するんじゃなくて見方を変えていろいろ手を動かすと思いつきやすいようです。

int N, A[MAX_N];
int L[MAX_N], R[MAX_N];
vector<pi> query[MAX_N];
bool ok[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, (1 << N)) L[i] = -1;
	rep(i, 0, (1 << N)) R[i] = inf;
	rep(i, 0, (1 << N)) {
		cin >> A[i]; A[i]--;
		if(A[i] != -1) ok[A[i]] = true;
	}
	if(A[0] != -1 && A[0] != 0) {
		cout << "NO\n";
		return;
	}
	if(A[(1 << N) - 1] != -1 && A[(1 << N) - 1] != (1 << N) - 1) {
		cout << "NO\n";
		return;
	}

	A[0] = 0; 
	A[(1 << N) - 1] = (1 << N) - 1;
	ok[0] = true; ok[(1 << N) - 1] = true;

	rep(i, 0, (1 << N)) {
		rep(j, 0, N) {
			if(!(i & (1 << j))) continue;
			MAX(L[i], L[i ^ (1 << j)]);
		}
		if(A[i] != -1) {
			if(L[i] >= A[i]) {
				cout << "NO\n";
				return;
			}
			else L[i] = A[i];
		}
	}
	rer(i, (1 << N), 0) {
		rep(j, 0, N) {
			if(i & (1 << j)) continue;
			MIN(R[i], R[i | (1 << j)]);
		}
		if(A[i] != -1) {
			if(R[i] <= A[i]) {
				cout << "NO\n";
				return;
			}
			else R[i] = A[i];
		}
	}
	rep(i, 0, (1 << N)) {
		if(L[i] >= R[i]) continue;
		query[L[i]].pb(pi(R[i], i));
	}

	set<pi> S;
	rep(i, 0, (1 << N)) {
		vector<pi>& vec = query[i];
		rep(j, 0, sz(vec)) S.insert(vec[j]);
		if(ok[i]) continue;
		if(S.empty()) {
			cout << "NO\n";
			return;
		}
		A[S.begin()->sec] = i;
		S.erase(S.begin());
		if(!S.empty() && S.begin()->fst <= i) {
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
	rep(i, 0, (1 << N)) {
		int tmp = 0;
		rep(j, 0, N) {
			if(!(i & (1 << j))) continue;
			tmp |= (1 << (N - 1 - j));
		}
		cout << A[tmp] + 1 << " ";
	}
	cout << "\n";
}