AtCoder practice contest B - Interactive Sorting
問題概要
N個のボールがあり,どの2つのボールの重さも異なる.
Q回のクエリが可能.各クエリでは2つのボールの重さを比較することができる.
ボールを軽い順にソートせよ.
制約
(N, Q) = (26, 1000), (26, 100), (5, 7) のいずれか.
解法
(N, Q) = (26, 100) の場合
ボール[0], ボール[1],...,ボール[M-1]がソートされているとする.
ここにボール[M]を挿入するために必要なクエリの回数をQ[M]とおく.
ボール[M/2]とボール[M]を比較し,
ボール[M/2] > ボール[M] の場合: ボール[0],...,ボール[M/2 - 1]にボール[M]を挿入する.
ボール[M/2] < ボール[M] の場合: ボール[M/2 + 1],...,ボール[M - 1]にボール[M]を挿入する.
よって,Q[M] = Q[M/2] + 1
Q[1] = 1
Q[2] = Q[3] = 2
Q[4] = Q[5] = ... = Q[7] = 3
Q[8] = Q[9] = ... = Q[15] = 4
Q[16] = Q[17] = ... = Q[31] = 5
26個のボール全てを挿入するのに必要なクエリの回数は
Q[1] + Q[2] + ... + Q[25] = 1 + 2*2 + 3*4 + 4*8 + 5*10 = 99 (<= Q = 100)
(N, Q) = (5, 7) の場合
上と同じ方法でやるとクエリはQ[1] + ... + Q[4] = 8 回必要になってしまう.
平均情報量に関する貪欲法を用いる.
各クエリにおいて,
ボール[x]とボール[y]を比較して得られる平均情報量が最大になるように
(すなわち,条件付確率 P(ボール[x] < ボール[y] | これまでのクエリで得た関係式) が1/2に最も近くなるように)
xとyを決める.
このアルゴリズムが最適である保証はないが,
N! = 120 通り全てのテストケースを与えて,
実際に7回以下のクエリでソートできることを確かめると,うまくいく.
#include <bits/stdc++.h> #define REP(i,n) for (int i=0;i<(n);++i) #define N_MAX 26 using namespace std; typedef pair<int, int> pii; int N, Q; string balls; vector<pii> relations; // (x, y) in relations <=> x < y void insertBall(int first, int last, char ball) { int mid = first + (last - first) / 2; printf("? %c %c\n", balls[mid], ball); fflush(stdout); string ans; cin >> ans; if (ans == ">") { if (last - first == 1) { balls.insert(first, 1, ball); } else { insertBall(first, mid, ball); } } else if (ans == "<") { if (last - first <= 2) { balls.insert(last, 1, ball); } else { insertBall(mid + 1, last, ball); } } } void solve_N26() { balls = "A"; for (char ball = 'B'; ball <= 'Z'; ++ball) { insertBall(0, balls.size(), ball); } cout << "! " << balls << endl; } bool satisfies_relations(int a[]) { for (pii rel: relations) { if (a[rel.first] >= a[rel.second]) { return false; } } return true; } void solve_N5() { while (true) { // find (query_i, query_j) s.t. d = 2 * q * abs(Probability(ball[query_i] < ball[query_j] | relations) - 1/2) is minimized // where q = # { a | a: a permutation of {0,1,...,N-1} that satisfies relations } int query_i; int query_j; int d_min = INT_MAX; int q = 0; int p[N_MAX][N_MAX]; // p[i][j] = # { a | a: a permutation of {0,1,...,N-1} that satisfies relations and a[i] < a[j] } // Probability(ball[i] < ball[j] | relations) = p[i][j] / q REP(i, N) REP(j, N) p[i][j] = 0; int a[N_MAX]; REP(k, N) a[k] = k; do { if (satisfies_relations(a)) { ++q; REP(i, N) REP(j, N) { if (a[i] < a[j]) ++p[i][j]; } } } while (next_permutation(a, a + N)); if (q == 1) { break; } REP(i, N) REP(j, N) { int d = abs(2 * p[i][j] - q); if (d_min > d) { d_min = d; query_i = i; query_j = j; } } printf("? %c %c\n", 'A' + query_i, 'A' + query_j); fflush(stdout); string ans; cin >> ans; if (ans == "<") { relations.push_back(pii(query_i, query_j)); } else if (ans == ">") { relations.push_back(pii(query_j, query_i)); } } int a[N_MAX]; REP(i, N) a[i] = i; do { if (satisfies_relations(a)) { vector<pii> v; REP(i, N) v.push_back(pii(a[i], i)); sort(v.begin(), v.end()); cout << "! "; REP(i, N) printf("%c", 'A' + v[i].second); cout << endl; break; } } while (next_permutation(a, a + N)); } int main(void) { cin >> N >> Q; if (N == 26) { solve_N26(); } else if (N == 5) { solve_N5(); } return 0; }
N = 5 の場合のアルゴリズムを一般のNに対して適用したとき,
必要なクエリの回数をf(N)とおくと,N <= 9 までの値は以下の通り.
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
f(N) | 0 | 1 | 3 | 5 | 7 | 10 | 13 | 17 | 20 |