Arithmetic Progression [Codeforces Round #538 (Div. 2) E]

https://codeforces.com/contest/1114/problem/E

インタラクティブ問題。
初項X0, 交差D, 項数Nの数列がある。
この数列がランダムな順で入った配列Aがある。
項数Nの情報と、以下のクエリを60回以下行うことで、X0,Dを見つけよ。

操作1 : 「? i」A[i]の要素を答える
操作2 : 「> x」xより大きい要素が存在するか答える

2≦N≦10^6
0≦x, A[i]≦10^9

前提知識

• 乱択アルゴリズム

解説

https://codeforces.com/contest/1114/submission/49735909

まずは二分探索を使って、数列の最大項を求めよう。
これは31回かかる（30回かも。よくわからないね）
　
次に交差を探すのだが、乱択アルゴリズムを使おう。
適当に29回操作1をして29個の項を得る。
目的の交差は得た項の差の約数のどれかになっているはずである。
なので、得た項の全ての差の最大公約数を取る。
すると、これが交差になっている（らしい）。
数学的な背景は全くわからないが、確かにこれで解くしかなさそうだし、twitterでもこのような情報が流れている。
　
最大項maと交差dが分かれば、初項はma - d * (N-1)なので、答えが求まった。
　
注意点が色々あるので注意

• 悪い乱数生成器を使うと通らない
• クエリの数は[0,10^9]にする必要がある

int debug = 0;
int N;
int a[1010] = { 14,24,9,19 };
int ma = -1;
//---------------------------------------------------------------------------------------------------
int ask1(int i) {

    printf("? %d\n", i + 1);
    fflush(stdout);

    if (debug) return a[i];

    int r; cin >> r;

    return r;
}
int ask2(int x) {
    printf("> %d\n", x);
    fflush(stdout);

    if (debug) return x < ma;

    int r; cin >> r;
    return r;
}
void answer(int x, int d) {
    printf("! %d %d\n", x, d);
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int ok = 0, ng = 1000000001;
    while (ok + 1 != ng) {
        int md = (ok + ng) / 2;
        if (ask2(md)) ok = md;
        else ng = md;
    }

    int ma = ng;
    vector<int> v;
    rep(i, 0, N) v.push_back(i);

    vector<int> w;
    w.push_back(ma);
    rep(i, 0, min(29,N)) {
        int j = getrand(0, N - 1 - i);
        int x = ask1(v[j]);
        w.push_back(x);

        swap(v[j], v[N - 1 - i]);
    }

    int g = 0;
    fore(x, w) fore(y, w) g = gcd(g, abs(x - y));

    int ans1 = ma - g * (N - 1);
    int ans2 = g;

    answer(ans1, ans2);
}