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 までの値は以下の通り．

N123456789
f(N)0135710131720