JusticeHui가 PS하는 블로그

총평
문제를 푸는 데 필요한 사전지식이 모두 있다는 가정하에 체감 난이도는 1 < 2 < 5 < 4 < 3 이었습니다. solvedac 기준으로는 1번 브론즈, 2번 골드 하위권, 3번 P5, 4번 P2~P3, 5번 P1 정도라고 생각합니다.
5문제 다 푸는 것보다 문제 요약이랑 풀이 작성하는 게 더 오래 걸리네요…
증강현실 배달 안경
사과 $A$개를 담을 수 있는 박스와 $B$개를 담을 수 있는 박스가 있다. 두 가지 종류의 박스를 적절히 이용해서 모든 박스가 가득차도록 $N$개의 사과를 담을 때, 사용할 수 있는 박스 개수의 최댓값을 구하는 문제.
$T\leq50;$ $N \leq 10^6;$ $1\leq A,B \leq N;$ $\sum N \leq 6.7\times 10^6;$ $N$개의 사과를 모두 박스에 담을 수 있는 경우만 입력으로 주어진다.
$N$이 많이 크지 않기 때문에 단순히 $A$개를 담을 수 있는 박스를 $0, 1, 2, \cdots, \lfloor N/A \rfloor$개 사용하는 경우를 모두 확인하는 것으로 문제를 해결할 수 있습니다.
void Solve(){
    int N, A, B, R=0;
    cin >> N >> A >> B;
    for(int i=0; i<=N/A; i++) if((N - A * i) % B == 0) R = max(R, i + (N - A * i) / B);
    cout << R << "\n";
}
딸기 수확 로봇
수직선 위에 $N$개의 딸기가 있다. 로봇은 원점에서 출발해 최대 $D$만큼 움직이면서 만나게 되는 딸기를 모두 수확할 수 있다. 로봇이 수확할 수 있는 딸기의 최대 개수를 구하는 문제.
$T \leq 50;$ $N\leq 10^6;$ $D \leq 10^9;$ $\vert X_i\vert \leq 10^9;$ $\sum N \leq 1.1\times 10^6$
로봇이 이동 방향을 2번 이상 전환하면 이동 거리에서 손해를 보기 때문에 방향은 최대 1번만 전환하는 경로만 고려해도 괜찮습니다. 일반성을 잃지 않고, 음의 방향으로 먼저 이동한 다음에 양의 방향으로 이동하는 경로만 생각합시다.
좌표가 음수인 딸기들의 위치를 $0 > A_1 \geq A_2 \geq \cdots\geq A_l$이라고 합시다. 이때, 음의 방향으로 $\vert A_i\vert$ 만큼 이동한 다음 양의 방향으로 $D-\vert A_i\vert$ 만큼 이동하는 경로만 고려해도 충분하다는 것은 쉽게 알 수 있습니다. 따라서 음의 방향으로 $\vert A_i\vert$ 이동하는 경로에서 수확하게 되는 딸기의 개수를 구하는 것은 위치가 $1 \leq X_j \leq D-\vert A_i\vert$를 만족하는 딸기의 개수, 위치가 $X_j = 0$을 만족하는 딸기의 개수, 그리고 $i$를 모두 더한 값과 같습니다.
$1 \leq X_j \leq D-\vert A_i\vert$를 만족하는 딸기의 개수는 이분 탐색을 이용해 $O(\log N)$ 시간에 구할 수 있으므로 전체 문제를 $O(N \log N)$ 시간에 해결할 수 있습니다.
int N, K, R;
vector<int> V[3];
int Sign(int v){ return (v > 0) - (v < 0); }
void Solve(){
    cin >> N >> K;
    for(int i=1,t; i<=N; i++) cin >> t, V[Sign(t)+1].push_back(abs(t));
    V[0].push_back(0); V[2].push_back(0);
    for(int i=0; i<3; i++) sort(V[i].begin(), V[i].end());
    for(int iter=0; iter<2; iter++, swap(V[0], V[2])){
        for(int i=0; i<V[0].size(); i++){
            if(V[0][i] > K) continue;
            int now = i + V[1].size();
            if(K - 2 * V[0][i] >= 0) now += upper_bound(V[2].begin(), V[2].end(), K - 2 * V[0][i]) - V[2].begin() - 1;
            R = max(R, now);
        }
    }
    cout << R << "\n";
    R = 0; for(int i=0; i<3; i++) V[i].clear();
}
장난감
$N$개의 칸으로 구성된 원형 배열이 있고, 초기에 $i$번째 칸에 $A_i$개의 구슬이 있다. 매초 $i$번째 칸에 쇠구슬이 1개 이상 있으면 그중 1개를 $i+1$번째 칸($i=N$이면 1번 칸)으로 보낸다. 장난감의 상태는 $N-$tuple $(A_1, A_2,\cdots, A_N)$으로 정의될 때, 무한히 많이 등장하는 튜플의 개수를 구하는 문제.
$T\leq 509;$ $N \leq 5\times 10^5;$ $0\leq A_i \leq 10^9;$ $\sum N \leq 3.5\times 10^6$
무한이 많이 등장하는 튜플의 개수를 구하는 것은 결국 충분히 많은 시간이 흐른 뒤 등장하는 사이클의 크기를 구하는 것과 같습니다. 문제 풀이의 과정은 사이클에 포함되는 튜플의 조건(이하 종료 상태)을 찾는 것과 입력으로 주어진 튜플이 어떤 종료 상태로 바뀌는지 구하는 것, 종료 상태의 사이클 주기를 구하는 것까지 총 세 개의 단계로 나눠서 생각하는 것이 편합니다.
종료 상태의 조건을 바로 찾는 것은 어렵기 때문에 자명한 경우부터 하나씩 생각해 봅시다. 먼저, 모든 칸에 구슬이 1개 이상 있다면 더 이상 상태가 변하지 않는다는 것은 쉽게 알 수 있습니다. 또한, 구슬이 1개 초과로 들어있는 칸이 있으면서 빈칸이 있는 경우에는 언젠가는 그 빈칸이 메꿔지게 되므로 1 초과인 칸과 0인 칸이 동시에 있을 때는 종료 상태가 될 수 없습니다. 빈칸이 있지만 구슬이 있는 칸에는 모두 1개의 구슬이 있다면 $N$초마다 같은 상태가 되므로 이때는 종료 상태가 맞습니다. 즉, 종료 상태의 조건은 다음과 같습니다:
빈칸이 없는 경우
각 칸에 있는 구슬의 개수가 1개 이하인 경우
빈칸이 없는 경우에는 1초가 지나도 상태가 바뀌지 않기 때문에 사이클의 크기는 1이고, 빈칸이 있는 경우에는 사이클의 크기가 1보다 클 수 있습니다. 즉, 구슬의 전체 개수가 $N$ 이상일 때는 항상 정답이 1이므로 구슬이 $N$개 미만으로 주어질 때만 신경 써도 충분합니다. 구슬이 $N$개 미만일 때 어떤 종료 상태로 바뀌는지 구하는 방법을 생각해 봅시다.
$A_1 > 1$이고 다른 모든 칸이 비어있는 상황을 생각해 봅시다. 1번 칸이 $A_1$초 동안 구슬을 하나씩 뱉어내서 $1, 2, \cdots, A_1$칸에 구슬을 깔아놓은 다음, 그 이후로는 매초 한 칸씩 그 덩어리가 앞으로 이동하게 됩니다. $\sum A_i < N$인 상황만 다룰 것이기 때문에 $N-1$초가 지나면 구슬을 뱉어내는 작업은 모두 끝나게 됩니다. $A_i > 1$인 칸들끼리 서로 간섭을 일으킬 수도 있지만, 그런 칸이 2~3개 있는 상황을 직접 손으로 그려서 시뮬레이션해 보면 문제가 되지 않는다는 것을 알 수 있습니다.
$N+1$초가 지난 상황을 생각해 봅시다. $A_i > 0$이었던 칸은 $A_i$초 동안 $[i,i+A_i-1]$ 구간에 구슬을 깔아놓은 뒤, 이 구간을 $N-A_i+1 \equiv 1-A_i \pmod N$번 전진시킵니다. 즉, $N+1$초가 지나면 $A_i > 0$이었던 칸은 $[i-A_i+1, i]$ 구간에 구슬을 깔아놓게 됩니다. 따라서 해당하는 구간에 1씩 더한 다음, 1 초과인 칸이 있으면 적당히 풀어주는 것으로 종료 상태를 구할 수 있습니다.
0과 1로만 구성된 종료 상태의 주기는 KMP 알고리즘을 이용해 계산할 수 있습니다. 이건 BOJ에도 있고 SWEA에도 있는 유명한 문제이므로 설명을 생략하겠습니다. $O(N)$ 시간에 문제를 해결할 수 있습니다.
int N, A[505050], B[505050], F[505050];
void Solve(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> A[i];
    if(accumulate(A, A+N, 0LL) >= N){ cout << "1\n"; return; }
    memset(B, 0, sizeof(int) * N);
    memset(F, 0, sizeof(int) * N);
    for(int i=0; i<N; i++){
        for(int j=0, p=i; j<A[i]; j++){
            B[p] += 1;
            if(!p--) p = N - 1;
        }
    }
    for(int i=N+N; i; i--) if(B[i%N] > 1) B[(i-1)%N] += B[i%N] - 1, B[i%N] = 1;
    for(int i=1, j=0; i<N; i++){
        while(j > 0 && B[i] != B[j]) j = F[j-1];
        if(B[i] == B[j]) F[i] = ++j;
        else F[i] = 0;
    }
    if(N % (N - F[N-1]) == 0) cout << N - F[N-1] << "\n";
    else cout << N << "\n";
}
최적의 프로세스 수행 순서
알파벳 소문자로 구성된 두 문자열 $S, P$가 주어진다. $S$을 적당히 분할할 건데, 분할된 모든 부분 문자열은 $P$의 접두사 형태(즉, $P[0:i]$ 형태)여야 한다. 이 조건을 지키는 최소 분할 횟수를 구하는 문제.
$T\leq 55;$ $\vert S\vert, \vert P\vert \leq 2.5\times 10^5;$ $\sum \vert S\vert, \sum \vert P\vert \leq 3\times 10^6$
$S$의 각 지점에서 시작하는 부분 문자열이 $P$의 접두사와 얼마나 매칭되는지 구하면, 그 이후는 간단한 동적 계획법으로 정답을 구할 수 있습니다. 즉, 모든 $0\leq i < \vert S\vert$에 대해, $S[i:i+x]=P[0:x]$를 만족하는 $x = X[i]$를 모두 구한 다음, $D[i+j] \leq D[i] + 1 (1 \leq j \leq X[i])$ 를 이용해 정답을 계산할 수 있습니다.
이제 주어진 문제를 $X[i]$를 효율적으로 계산하는 것과 점화식을 $O(N^2)$보다 빠르게 계산하는 두 개의 부분 문제로 나눠서 생각할 수 있습니다.
먼저, $X[i]$는 Z 알고리즘을 이용하면 $O(N+M)$ 시간에 계산할 수 있습니다. Z 알고리즘은 문자열 $S$가 주어지면 $S$의 모든 접미사 $S[i:]$에 대해, $S$와 $S[i:]$의 최장 공통 부분 문자열의 길이를 선형 시간에 구하는 알고리즘입니다. 즉, $S[0\cdots]$와 $S[i\cdots]$가 일치하는 최대 길이를 구합니다. 이를 이용하면 $B+A$의 $Z$ 배열을 구하는 것으로 모든 $X[i]$를 $O(N+M)$ 시간에 구할 수 있습니다.
이제 점화식을 빠르게 계산할 차례입니다. 점화식을 계산할 때 $D[i+1], D[i+2], \cdots, D[i+X[i]]$를 현재의 값과 $D[i]+1$ 중 더 작은 것으로 갱신하는 연산이 필요한데, 이는 연속된 구간에 최솟값 갱신을 수행하는 연산이므로 세그먼트 트리를 이용해 수행할 수 있습니다. 구간 최솟값 갱신 쿼리와 특정 지점의 값을 알아내는 쿼리는 레이지 프로퍼게이션 없이 반복문만을 이용해 구현할 수 있습니다. 점화식을 계산하는 시간 복잡도는 $O(N \log N)$입니다.
따라서 전체 문제를 $O(M + N \log N)$ 시간에 해결할 수 있습니다.
struct segment_tree_range{
    int sz; vector<int> tree;
    constexpr static int INF = 0x3f3f3f3f;
    segment_tree_range() = default;
    segment_tree_range(int n){
        sz = 16; while(sz < n + 10) sz <<= 1;
        tree = vector<int>(sz * 2, INF);
    }
    void update(int l, int r, int v){
        for(l|=sz, r|=sz; l<=r; l/=2, r/=2){
            if(l & 1) tree[l] = min(tree[l], v), l++;
            if(~r & 1) tree[r] = min(tree[r], v), r--;
        }
    }
    int query(int x) const {
        int res = INF;
        for(x|=sz; x; x/=2) res = min(res, tree[x]);
        return res;
    }
};
vector<int> Z(const string &s){
    vector<int> z(s.size()); z[0] = s.size();
    for(int i=1, l=0, r=0; i<s.size(); i++){
        if(i < r) z[i] = min(r-i-1, z[i-l]);
        while(i+z[i] < s.size() && s[i+z[i]] == s[z[i]]) z[i]++;
        if(i+z[i] > r) r = i+z[i], l = i;
    }
    return z;
}
int N, M, X[252525], D[252525];
string A, B, S;
segment_tree_range T;
void Solve(){
    cin >> A >> B; S = B + "#" + A;
    N = A.size(); M = B.size();
    vector<int> V = Z(S);
    for(int i=0; i<N; i++) X[i] = min({M, N-i, V[M+i+1]});
    T = segment_tree_range(N);
    T.update(0, 0, 0);
    for(int i=0; i<=N; i++){
        D[i] = T.query(i);
        if(X[i] == 0) continue;
        int le = i + 1, ri = min(N, i + X[i]);
        T.update(le, ri, D[i] + 1);
    }
    cout << (D[N] < 1e9 ? D[N] : -1) << "\n";
}
타이젠
총 $M$개의 내부 상태를 갖는 시스템에서 $N$개의 작업을 수행해야 한다. $i$번째 작업은 $[L_i,R_i]$ 시간 구간 동안 수행되어야 하고, $0=L_1<R_1<L_2<R_2<\cdots<L_N < R_N$이 성립하므로 모든 작업의 수행 시간은 겹치지 않는다.
시스템은 $i$번째 상태에 있을 때 시간당 $P_i$ 만큼의 전력을 소모하고, $P_1>P_2>\cdots>P_M$이 성립한다.
작업이 수행되는 동안에는 반드시 1번 상태에 있어야 하며, 수행하지 않는 동안에는 다른 상태로 자유롭게 바꿀 수 있다. $i$번째 상태에서 $j(>i)$번째 상태로 바꾸는데 $W_j - W_i$ 만큼의 전력을 소모하고, $j(>i)$번째 상태에서 $i$번째 상태로 바꿀 때는 전력을 소모하지 않는다. 이때 $0=W_1\leq W_2\leq \cdots \leq W_M$이 성립한다.
시스템이 $N$개의 작업을 모두 수행하는 데 필요한 전력 소모량의 최솟값을 구하는 문제
$T\leq 45;$ $N,M \leq 10^5;$ $0=L_1<R_1<L_2<R_2\cdots<L_N<R_N \leq 10^{11};$ $10^7\geq P_1> P_2> \cdots > P_M\geq 0;$ $0=W_1\leq W_2\leq \cdots \leq W_M\leq 10^{11}$
작업 구간일 때는 1번 상태에 있어야 하므로 이때 소모하는 전력량은 상수 취급해도 됩니다. 따라서 수면 구간에서의 비용만 최소화하면 되고, 각각의 수면 구간에서 상태를 여러 번 바꿔서 이득을 보는 일은 없기 때문에 한 번의 수면 구간에서는 한 개의 상태만 선택하는 경우만 고려해도 됩니다.
길이가 $x$인 수면 구간을 $i$번째 상태에서 보낼 때 소모하는 전력의 양은 $P_ix+W_i$입니다. 비용이 일차 함수 꼴이기 때문에 Convex Hull Trick을 사용할 수 있고, 심지어 $P_i$가 순감소하므로 수면 구간을 길이 오름차순으로 정렬하면 CHT를 선형 시간에 할 수 있습니다. 수면 구간을 정렬해야 하므로 전체 시간 복잡도는 $O(N \log N)$입니다.
$P_i$에 순감소 조건이 붙어있어서 비교적 복잡한 자료구조(li-chao tree, line container, …)가 필요하지 않고, $P_i\leq 10^7;L_i,R_i,W_i\leq 10^{11}$ 제한 덕분에 long long만 써서 교점을 비교할 수 있다는 점에서 출제자의 너그러운 마음을 확인할 수 있었습니다.
struct line{
    ll a, b; line(ll a, ll b) : a(a), b(b) {}
    ll f(ll x) const { return a * x + b; }
};
ll N, M, L[101010], R[101010], P[101010], W[101010], X;
vector<line> H;
bool Check(line a, line b, line c){
    return (a.b - b.b) * (b.a - c.a) <= (c.b - b.b) * (b.a - a.a);
}
void Insert(line l){
    while(H.size() >= 2 && Check(H[H.size()-2], H.back(), l)) H.pop_back();
    H.push_back(l);
}
ll Query(ll x){
    while(X + 1 < H.size() && H[X].f(x) >= H[X+1].f(x)) X++;
    return H[X].f(x);
}
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> L[i] >> R[i];
    cin >> M;
    for(int i=1; i<=M; i++) cin >> P[i];
    for(int i=1; i<=M; i++) cin >> W[i];
    ll res = 0; vector<ll> len;
    for(int i=1; i<=N; i++) res += (R[i] - L[i]) * P[1];
    for(int i=2; i<=N; i++) len.push_back(L[i] - R[i-1]);
    sort(len.begin(), len.end());
    H.clear(); X = 0;
    for(int i=1; i<=M; i++) Insert({P[i], W[i]});
    for(auto i : len) res += Query(i);
    cout << res << "\n";
}

2023 SCPC 1차예선 풀이

댓글