Problem F2 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/F2

hard 버전에서 easy 버전과 다른 부분은 문제 개수와 각 문제의 답을 찾은 후,

숨겨진 배열에서 찾은 위치의 0 값이 1로 변경되어 다음 문제가 진행된다는 점이다.

easy 버전에서 사용한 알고리즘 그대로 사용하게 되면 문제 개수 제한 ( 최대 6만 개 ) 에서 걸리게 된다.

이 문제를 해결하기 위해서는 이전에 했던 질문에 대한 답을 저장해 놓고 사용해야 한다.

하지만 문제를 해결할 때마다 해당 위치의 값이 1로 바뀌기 때문에 저장해 놓은 데이터도 변경해 주어야 한다.

내가 easy 버전에서 사용한 질문 방식으로는 이 변경하는 과정에서 시간 초과를 해결할 방법을 생각하지 못했고,

솔루션을 참고해서 솔루션에서 사용한 이진 탐색 방법을 사용했다.

내가 기존에 사용했던 질문 방식은 1 ~ r 범위의 원소 합을 구하여 계산하는 방식이었는데

여기서 사용할 방식은 이진 탐색 때 사용되는 left, right의 범위를 그대로 사용하여

? left right를 질문으로 던져 left ~ right 범위의 원소 합을 구하여 사용한다.

하나의 문제에 대한 답을 찾은 후 기존 데이터들을 갱신해 주기 위해 이진 탐색을 같은 방법으로 진행한다.

진행하면서 원소의 값이 1로 바뀐 위치가 포함된 범위의 데이터인 경우에 +1씩 해준다.

이 방식을 이용하면 시간 초과가 나지 않고 문제를 해결할 수 있다.


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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <map>
 
using namespace std;
 
map<pair<int, int>, int> calm;
 
void change(int pos, int s, int e) {
    
    calm[{s, e}]--;
 
    if (s != e) {
        int m = (s + e) / 2;
        if (m < pos) {
            change(pos, m + 1, e);
        }
        else {
            change(pos, s, m);
        }
    }
}
 
int main() {
 
    int n, t;
    cin >> n >> t;
 
    t = min(n, 10000);
 
    while (t--) {
 
        int k;
        cin >> k;
 
        int s = 1, e = n, m;
 
        while (s < e) {
            
            m = (s + e) / 2;
 
            pair<int, int> data = { s, m };
 
            if (calm.count(data) == 0) {
                cout << "? " << s << " " << m << endl;
                cin >> calm[data];
                calm[data] = m - s + 1 - calm[data];
            }
 
            if (calm[data] >= k) {
                e = m;
            }
            else {
                k -= calm[data];
                s = m + 1;
            }
        }
 
        cout << "! " << e << endl;
 
        change(e, 1, n);
    }
 
    return 0;
}
cs

댓글

댓글 쓰기