Lost Root [Codeforces Round #523 (Div. 2) F]

http://codeforces.com/contest/1061/problem/F

N頂点の完全K分木がある。
この木について
「? a b c」頂点a,c間に頂点bがあるか
「! s」頂点sが木の根であると答える
というクエリが60*N回までできる。
正しく根を答えよ。

前提知識

• 乱択アルゴリズム

解説

http://codeforces.com/contest/1061/submission/46097877

まずは完全K分木の深さを求めよう（関数getdpt）。
　
この問題は乱択で解く。
何を乱択するかと言うと、a,cである。
a,cを乱択して、どちらも葉であり、かつ、a,cの経路に根を通るa,cを探す。
a,cが条件を満たすものであるかは、a,c以外の頂点をbとして質問をする。
条件を満たすならば、Yesと帰ってくるのが、dpt*2-1個あるはずである。
　
乱択でa,cが特定できたら、その経路上のどこかに根がある。
経路上の頂点を配列vに入れておく。
これをソートするのだが、隣接する2項目(x,y)がask(a,x,y)=Yesを満たすようにソートする。
こうすると、経路上のaからbに向けた順のソートになるので、dpt-1番目が根となる。

int N, K;
//---------------------------------------------------------------------------------------------------
map<tuple<int, int, int>, int> memo;
int ask(int a, int b, int c) {
    if (a > c) swap(a, c);
    auto id = make_tuple(a, b, c);
    if (memo.count(id)) return memo[id];

    printf("? %d %d %d\n", a + 1, b + 1, c + 1);
    fflush(stdout);

    string s; cin >> s;
    if (s == "No") return memo[id] = 0;
    return memo[id] = 1;
}
//---------------------------------------------------------------------------------------------------
void answer(int x) {
    printf("! %d\n", x + 1);
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
int getdpt() {
    int tot = 1, leave = 1, dpt = 0;
    while (tot < N) {
        leave *= K;
        tot += leave;
        dpt++;
    }
    return dpt;
}
//---------------------------------------------------------------------------------------------------
int done[2010][2010];
void _main() {
    cin >> N >> K;

    int dpt = getdpt();
    rep(i, 0, N) done[i][i] = 1;

    rep(_, 0, 1010) {
        int a = getrand(0, N - 1);
        int c = getrand(0, N - 1);
        if (done[a][c]) continue;
        done[a][c] = done[c][a] = 1;

        vector<int> v;
        rep(i, 0, N) if (i != a and i != c) if (ask(a, i, c)) v.push_back(i);
        if (v.size() == dpt * 2 + 1 - 2) {
            sort(all(v), [&](int x, int y) {
                if (ask(a, x, y)) return 1;
                return 0;
            });

            answer(v[dpt - 1]);
            return;
        }
    }
}