백준21100 Game

작성일 | In

문제 링크

  • http://icpc.me/21100

사용 알고리즘

  • 볼록 껍질

풀이

에서 시작했을 때 얻을 수 있는 값을 $f(x)$라고 하면, $f(x) = \max\lbrace f(x), (f(x-1)+f(x+1))/2\rbrace$를 무한히 반복한다고 생각할 수 있고, $f(x)$는 $(i, A_i)$들의 Convex Hull 형태가 됩니다.

만약 $(i, A_i)$가 Convex Hull 위의 점이라면 정답에 $A_i\cdot N^{-1}$을 더하면 되고, 그렇지 않다면 $i$와 왼쪽/오른쪽에서 가장 가까운 Convex Hull 위의 점을 찾아서 확률을 계산해서 더하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 998244353;

ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD) if(b & 1) res = res * a % MOD;
    return res;
}
inline ll Inv(ll a){ return Pow(a, MOD-2); }

ll N, A[505050], C[505050], L[505050], R[505050];
ll CCW(int p1, int p2, int p3){
    return (p2 - p1) * (A[p3] - A[p1]) - (p3 - p1) * (A[p2] - A[p1]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    vector<int> U;
    for(int i=1; i<=N; i++){
        while(U.size() >= 2 && CCW(U[U.size()-2], U.back(), i) > 0) U.pop_back();
        U.push_back(i);
    }
    for(auto i : U) C[i] = 1, L[i] = R[i] = i;
    for(int i=1; i<=N; i++) if(!C[i]) L[i] = L[i-1];
    for(int i=N; i>=1; i--) if(!C[i]) R[i] = R[i+1];
    for(int i=1; i<=N; i++) A[i] %= MOD;

    ll res = 0;
    for(int i=1; i<=N; i++){
        if(C[i]){ res = (res + A[i]) % MOD; continue; }
        int dst = R[i] - L[i], le = i - L[i], ri = R[i] - i;
        res = (res + le * Inv(dst) % MOD * A[L[i]]) % MOD;
        res = (res + ri * Inv(dst) % MOD * A[R[i]]) % MOD;
    }
    cout << res * Inv(N) % MOD;
}