백준18484 Eight Sins

작성일 | In

문제 링크

  • http://icpc.me/18484

풀이

그냥 이분 탐색을 하면 $N\lceil \log_2 K \rceil = 3\,000$번의 쿼리를 사용하게 됩니다. 수가 오름차순이라는 점을 이용해서 쿼리 횟수를 줄여야 합니다.

정답이 존재할 수 있는 구간 $[1, K]$을 크기가 $B$인 구간 $K/B$개로 분할합시다. $A_i \leq tB$를 만족하는 가장 큰 $t$를 찾은 다음, $t$번째 구간에서만 이분 탐색을 진행하는 방식으로 답을 구할 것입니다. $a_i < a_{i+1}$을 만족하기 때문에 구간의 번호는 단조 증가합니다.
쿼리 횟수를 계산해 봅시다. 구간을 총 $K/B-1$번 탈출하고, 이분 탐색을 시작하기 전에 매번 1번씩 현재 구간을 인식하고, 매번 이분 탐색에서 $\lceil \log_2 B \rceil$번의 쿼리를 사용합니다. $B$를 잘 정해서 $K/B-1 + N + N \lceil \log_2 B \rceil$를 최소화해야 합니다.

$f(x) = N-1 + K/x + N \log_2 x$의 도함수는 $f’(x) = -K/x^2 + N/x\ln 2 = \frac{Nx/\ln 2 - K}{x^2}$이고 $x = K \ln 2/N$일 때 최소가 됩니다. $B = K/N$ 또는 $2K/N$ 정도로 잡으면 2599번의 쿼리로 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, K;
map<ll, int> cache[111];

int Ask(int idx, ll x){
    if(auto it=cache[idx].find(x); it != cache[idx].end()) return it->second;
    cout << x << endl;
    char res; cin >> res;
    return cache[idx][x] = string("<=>").find(res) - 1;
}

ll End(ll block){
    return K * block / N;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1, j=1; i<=N; i++){
        while(j < N && Ask(i, End(j)) == 1) j++;
        if(Ask(i, End(j)) == 0) continue;
        ll l = End(j-1) + 1, r = End(j);
        while(l <= r){
            ll m = (l + r) / 2;
            int res = Ask(i, m);
            if(res == 0) break;
            if(res == 1) l = m + 1;
            else r = m - 1;
        }
    }
}