백준16892 레몬 주스 게임

작성일 | In

문제 링크

  • http://icpc.me/16892

사용 알고리즘

  • 세그먼트 트리
  • 게임 이론

시간복잡도

  • $O(N \log N)$
  • $O(N)$

풀이

$K = 0$인 경우만 먼저 생각해봅시다.

$N$이 짝수인 경우, 정답은 가운데 있는 두 원소 중 큰 값 ($\max(A[\frac{N}{2}], A[\frac{N}{2}+1])$)입니다. 만약 구사과가 가운데 있는 레몬이 아닌 다른 레몬을 남기기로 결정한다면, 큐브러버가 그 방향에 있는 레몬을 다 먹어서 저지할 수 있습니다. 그렇기 때문에 가운데 있는 레몬이 정답이 됩니다.

$N$이 홀수인 경우, 정답은 $\max( \min(A[\frac{N+1}{2}-1], A[\frac{N+1}{2}]), \min(A[\frac{N+1}{2}], A[\frac{N+1}{2}+1]) )$입니다. 구사과가 레몬 하나를 먹는 순간, 큐브러버가 선공이고 $N$이 짝수인 게임으로 바뀌기 때문입니다.
$B[i] = \min(A[i], A[i+1])$를 정의해서 $N$이 짝수인 문제를 푸는 것과 똑같습니다.

$K > 0$인 경우에는 양쪽 끝을 적절히 잘라낸 다음 게임을 시작하게 됩니다.

  • 왼쪽에서 $0$개, 오른쪽에서 $K$개
  • 왼쪽에서 $1$개, 오른쪽에서 $K-1$개
  • 왼쪽에서 $i$개, 오른쪽에서 $K-i$개

와 같은 총 $K+1$개의 경우에서 정답이 될 수 있는 레몬들을 합집합해주면 연속한 구간이 나오게 됩니다. 세그먼트 트리를 이용해 연속한 구간의 최댓값을 구하면 $O(N \log N)$에 문제를 풀 수 있습니다.
최댓값을 구해야 하는 구간이 점점 확장된다는 점을 이용해 포인터 2개를 관리하는 방식으로 $O(N)$에 문제를 풀 수도 있습니다.
두 가지 코드 모두 올립니다.

전체 코드

O(N log N)

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

const int sz = 1 << 19;
struct Seg{
    int tree[1 << 20];
    void update(int x, int v){
        x |= sz; tree[x] = v;
        while(x >>= 1) tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
    }
    int query(int l, int r){
        l |= sz; r |= sz; int ret = 0;
        while(l <= r){
            if(l & 1) ret = max(ret, tree[l++]);
            if(~r & 1) ret = max(ret, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
} seg_A, seg_B;

int n, a[303030];

int even(int k){
    int range = n-k;
    int l = range/2, r = (n-range+1) + range/2;
    return seg_A.query(l, r);
}

int odd(int k){
    int range = n-k;
    int l = range/2, r = (n-range) + range/2;
    return seg_B.query(l, r);
}

int f(int k){
    int range = n - k;
    if(range == 1) return seg_A.query(1, n);
    if(range & 1) return odd(k+1);
    else return even(k);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) seg_A.update(i, a[i]);
    for(int i=1; i<n; i++) seg_B.update(i, min(a[i], a[i+1]));
    for(int i=0; i<n; i++) cout << f(i) << " ";
}

O(N)

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, a[303030], b[303030];

int even(int k){
    static int a1 = 0, a2 = 0, A = 0;
    int range = n-k;
    int l = range/2, r = (n-range+1) + range/2;
    if(!a1){
        a1 = l; a2 = r;
        for(int i=a1; i<=a2; i++) A = max(A, a[i]);
    }
    while(l < a1) A = max(A, a[--a1]);
    while(a2 < r) A = max(A, a[++a2]);
    return A;
}

int odd(int k){
    static int b1 = 0, b2 = 0, B = 0;
    int range = n-k;
    int l = range/2, r = (n-range) + range/2;
    if(!b1){
        b1 = l; b2 = r;
        for(int i=b1; i<=b2; i++) B = max(B, b[i]);
    }
    while(l < b1) B = max(B, b[--b1]);
    while(b2 < r) B = max(B, b[++b2]);
    return B;
}

inline int f(int k){
    int range = n - k;
    if(range == 1) return *max_element(a+1, a+n+1);
    if(range & 1) return odd(k+1);
    else return even(k);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i], b[i-1] = min(a[i-1], a[i]);
    for(int i=0; i<n; i++) cout << f(i) << " ";
}