Codeforces Round 945 (Div. 2) D. Cat, Fox and Maximum Array Split

自力で解けたが、コンテスト時間内に間に合わなかった。

割と面白いので解説を書く。

解法

まず、 $N$ 回で $\max_{i} A_{i}$ を特定する。

次に、 $\max_{i} A_{i}$ の倍数を $\max_{i} A_{i} \times \left\lfloor \frac{N}{K} \right\rfloor$ まで調べれば良い。各判定は $K$ 回でできるので、全体で $\left\lfloor \frac{N}{K} \right\rfloor \times K ( \leq N)$ 回でできる。

#include "my_template.hpp"
using namespace std;

void solve() {
    auto query = [](int l, int x) -> int {
        printi("?", l, x);
        INT(r);
        return r;
    };
    auto answer = [](int m) -> int {
        printi("!", m);
        INT(res);
        return res;
    };
    INT(N, K);
    int mx = 1;
    REP(x, 1, N + 1) {
        int r = query(1, x * N);
        if (r == N) {
            mx = x;
        }
    }
    i64 ans = -1;
    REP(d, 1, N / K + 1) {
        int val = mx * d;
        int l = 1, ok = 1;
        REP(t, K) {
            if (l == N + 1) {
                ok = 0;
                break;
            }
            int r = query(l, val);
            if (r == N + 1) {
                ok = 0;
                break;
            } else {
                l = r + 1;
            }
        }
        ok &= l == N + 1;
        if (ok) {
            ans = val;
        }
    }
    int res = answer(ans);
    assert(res == 1);
    return;
}

int main() {
    INT(T);
    REP(T) solve();
    return 0;
}

考察

以下のような流れで考察したと思う。

$f(l, r)$ は $l$ を固定すると $r$ について単調増加であることに気づく。
答えを決め打てば判定は $O(K)$ でできることに気づく。
まず、部分問題として $K = N$ の場合を考える。 $N$ 回で初項を特定すればあとは各項が初項と一致するか判定すれば良い。 $K \lt N$ の場合でもとりあえず同じように初項を特定してみる。
次に、初項がわかっているときに何ができるか考える。区間幅を $2$ と決め打って、? 1 2 * A[0] を投げてみると、 $2$ が返ってきた場合は $A_0 \geq A_1$ がわかる。 $N + 1$ が返ってきた場合は $A_0 \lt A_1$ がわかるが、 $A_1$ の具体的な値はわからない。しかしこのように $A_{i} \lt A_{i+1}$ となるのは高々 $N$ 回で、区間が伸びるのも $N$ 回なので、 $2N$ 回で最大値が特定できる。最大値は使い道がありそうとなる。
並行して答えの上界を考える。鳩の巣原理より、長さが $\left\lfloor \frac{N}{K} \right\rfloor$ 以下であるような区間が必ず存在する。この区間に対する答えは $\max_{i} A_{i} \times \left\lfloor \frac{N}{K} \right\rfloor$ 以下である。さらに答えは $\max_{i} A_{i}$ の倍数になっているはずであり、以上より試すべき値が $\left\lfloor \frac{N}{K} \right\rfloor$ 通りしかないことに気づく。判定も含めて全体で $N$ 回でできる。
以上より $3N$ 回で答えはわかる。よく考えると最大値を特定するだけなら区間幅 $N$ に対してのクエリを行うイメージでやると $N$ 回でできる。よって $2N$ 回になった。

感想

インタラクティブ問題難しすぎる。典型手法のようなものを全く知らない気がする。