JusticeHui가 PS하는 블로그

서론
오랜만에 작성하는 KOI 1차 풀이 글입니다. 2026 한국정보올림피아드 1차 대회 2교시에 출제된 6문제의 풀이를 다룹니다.
과거 대회 풀이는 아래 링크에서 확인할 수 있습니다.
2020 KOI 1차대회 고등부 문제 풀이
2021 KOI 1차대회 고등부 문제 풀이
2022 KOI 1차대회 고등부 문제 풀이
초등부 1번. 이웃
단순 구현 문제입니다. $1 \le i,j \le N$ 이고 $i \ne j$ 인 모든 정수 순서쌍 $(i, j)$를 순회하면서, $i$와 $j$가 이웃 조건을 만족한다면 $i$번째 학생의 이웃 수를 1 증가시키도록 구현하면 됩니다.
#include <iostream>
#include <iterator>
#include <cmath>
#include <vector>
using namespace std;
int main(){
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vector<int> s(n), res(n);
    for(auto &i : s) cin >> i;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j) continue;
            if(s[i] == s[j] && abs(i - j) <= k1) res[i]++;
            if(s[i] != s[j] && abs(i - j) <= k2) res[i]++;
        }
    }
    copy(res.begin(), res.end(), ostream_iterator<int>(cout, " "));
}
중등부 1번/고등부 1번. 친구
초등부 1번 문제를 여러 방향에서 확장시킨 문제입니다.
$j$번 학생이 $i$번 학생과 이웃이기 위해서는 아래 조건 중 하나를 만족해야 합니다.
$S_i = S_j$ and $X_i - K_1 \le X_j \le X_i + K_1$
$S_i \ne S_j$ and $X_i - K_2 \le X_j \le X_i + K_2$
첫 번째 조건은 학교가 같은 학생의 위치를 하나의 배열에 모은 다음 이분 탐색을 사용하면, 조건을 만족하는 $j$의 개수를 $O(\log N)$ 시간에 구할 수 있습니다. 같은 방식으로 두 번째 조건까지 처리하기 위해서는 $i$번 학생이 다니지 않는 모든 학교를 순회하면서 이분 탐색을 수행해야 하는데, 학교가 최대 $N$가지 있기 때문에 너무 오래 걸립니다.
2번 조건을 만족하는 $j$의 수는 아래의 첫 번째 조건을 만족하는 학생의 수에서 두 번째 조건을 만족하는 학생의 수를 뺀 것과 같습니다.
학교 무관 $X_i - K_2 \le X_j \le X_i + K_2$
$S_i = S_j$ and $X_i - K_2 \le X_j \le X_i + K_2$
따라서 $S_i \ne S_j$ 인 친구의 수도 이분 탐색을 이용하면 $O(\log N)$ 시간에 구할 수 있습니다.
각 학생에 대해 $O(\log N)$ 시간에 답을 구할 수 있으므로 전체 시간 복잡도는 $O(N \log N)$입니다. Radix sort 와 투 포인터 기법을 이용하면 $O(N)$ 시간에 해결할 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int N, K1, K2, R[505050];
vector<pair<int,int>> G[505050];
vector<pair<int,int>> A;
int Get(const vector<pair<int,int>> &v, int le, int ri){
    auto lo = lower_bound(v.begin(), v.end(), make_pair(le, -1));
    auto hi = upper_bound(v.begin(), v.end(), make_pair(ri, N+1));
    return distance(lo, hi);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K1 >> K2;
    for(int i=1; i<=N; i++){
        int x, s; cin >> x >> s;
        G[s].emplace_back(x, i);
        A.emplace_back(x, i);
    }
    for(int i=1; i<=N; i++) sort(G[i].begin(), G[i].end());
    sort(A.begin(), A.end());
    for(int v=1; v<=N; v++){
        for(auto [x,i] : G[v]){
            int local = Get(G[v], x-K1, x+K1);
            int global = Get(A, x-K2, x+K2) - Get(G[v], x-K2, x+K2);
            R[i] = local + global - 1;
        }
    }
    for(int i=1; i<=N; i++) cout << R[i] << " ";
}
초등부 2번. 가위바위보
$i$보다 왼쪽에 있는 사람과 오른쪽에 있는 사람이 대결할 수는 없으므로, $A[1\cdots i]$와 $A[i\cdots N]$을 독립적으로 판정해도 됩니다. 바위(R)을 낸 $i$번 사람이 $A[1\cdots i]$를 모두 이길 수 있는지 판정하는 상황을 생각합시다.
만약 $A[1\cdots i-1]$에 바위(R)를 이기는 보(P) 로만 구성되어 있다면 $i$는 절대 우승할 수 없습니다. 반대로, 보(P)가 하나도 없다면 $i$번 사람이 모든 사람을 상대로 승자가 될 수 있으므로 우승할 수 있습니다.
$A[1\cdots i-1]$에 보(P)와 나머지(R, S)가 둘 다 나오는 경우에는, 보(P)를 모두 없앨 수 있다면 $i$가 우승할 수 있을 것입니다. 이때는 보(P)가 인접한 위치에 있는 모든 바위(R)를 없앤 다음 가위(S)가 보(P)를 잡는 식으로 매치를 구성하면 됩니다. 따라서 둘 모두 나오는 경우 가위(S)가 하나라도 있으면 $i$번 사람이 우승할 수 있습니다.
정리하면, 구간에 $i$번 사람을 이길 수 있는 사람이 한 명도 없거나, $i$번 사람에게 지는 사람이 한 명이라도 있는 경우 $i$번 학생이 우승할 수 있습니다.
누적 합 배열을 이용하면 구간에 특정 카드가 존재하는지를 $O(1)$ 시간에 판별할 수 있습니다. 따라서 $O(N)$ 시간에 전처리하면 각 사람마다 $O(1)$ 시간에 답을 구할 수 있고, 전체 시간 복잡도는 $O(N)$이 됩니다.
#include <bits/stdc++.h>
using namespace std;
string X = "RSP";
int N, A[202020], B[202020][3];
string S;
bool f(int l, int r, int v){
    if(l > r) return true;
    int win = (v + 1) % 3, lose = (v + 2) % 3;
    if(B[r][win] - B[l-1][win] > 0) return true;
    if(B[r][lose] - B[l-1][lose] == 0) return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> S;
    for(int i=1; i<=N; i++) A[i] = X.find(S[i-1]);
    for(int i=1; i<=N; i++) memcpy(B[i], B[i-1], sizeof B[i]), B[i][A[i]] += 1;
    for(int i=1; i<=N; i++) cout << (f(1, i-1, A[i]) && f(i+1, N, A[i]));
}
초등부 3번/중등부 2번. 수열 정렬하기
편의상 좌표 압축을 해서, 수열 $A$에 $1, 2, \cdots, M$이 모두 각각 한 번 이상 등장하는 상황만 생각합시다.
어떤 정수 $v$가 처음으로 등장하는 위치를 $L(v)$, 마지막으로 등장하는 위치를 $R(v)$라고 합시다. 모든 $a < b$에 대해 $R(a) < L(b)$가 되도록 만드는 것이 목표입니다. 만약 $a < b$ 이고 $R(a) > L(b)$ 라면 $[a, b)$ 범위의 정수 중 하나를 $x$로 정해서 연산을 수행해야 $R(a) < L(b)$로 만들 수 있습니다.
잘 생각해 보면 $a = i, b = i + 1$인 $(a, b)$ 쌍만 고려해도 된다는 사실을 알 수 있습니다. 즉, $R(i) > L(i+1)$ 인 모든 $i$를 찾은 뒤 $x = A_i$로 연산을 수행하면 수열을 정렬할 수 있고, 이보다 더 적은 횟수로 정렬할 수 없음을 증명할 수 있습니다.
구현 방식에 따라 $O(N)$ 또는 $O(N \log N)$ 시간에 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int N, A[303030], B[303030], R;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    fill(A+1, A+N+1, N+1);
    for(int i=1; i<=N; i++){
        int t; cin >> t;
        A[t] = min(A[t], i);
        B[t] = max(B[t], i);
    }
    int lst = 0;
    for(int i=1; i<=N; i++){
        if(A[i] > N) continue;
        if(lst > A[i]) R++;
        lst = B[i];
    }
    cout << R;
}
중등부 3번/고등부 2번. 산책로
정점에 가중치($A_i$)가 없다면 트리의 지름을 찾는 문제입니다. 정점의 가중치는 가장 큰 값만 $-\max A_i$ 형태로 반영되므로, $A_i \le x$ 인 정점으로만 구성된 포레스트에서 $(\text{지름} - x)$ 를 구하는 것을 모든 $x$에 대해 반복하면 답을 구할 수 있습니다.
이를 위해 $A_i$ 오름차순으로 정점을 추가하면서, union find를 이용해 두 컴포넌트를 합칠 때 지름을 효율적으로 계산하는 방법을 알아봅시다. 가중치가 0 이상인 트리는 아래 성질이 있다는 것이 잘 알려져 있습니다.
지름의 양 끝점이 $u, v$ 일 때, 임의의 정점 $x$와 가장 멀리 떨어져 있는 정점은 $u$ 또는 $v$ 이다.
따라서 합치고자 하는 두 컴포넌트 $T_a$와 $T_b$의 지름이 각각 $(a_1, a_2)$, $(b_1, b_2)$ 일 때, 합쳐진 컴포넌트의 지름은 아래 6가지 중 하나입니다.
기존 컴포넌트의 지름을 그대로 사용: $(a_1, a_2)$, $(b_1, b_2)$
두 컴포넌트에서 각각 하나씩 선택: $(a_1, b_1)$, $(a_1, b_2)$, $(a_2, b_1)$, $(a_2, b_2)$
경로의 길이는 LCA를 이용하면 $O(N \log N)$ 시간 전처리 후에 매번 $O(\log N)$ 시간에 구할 수 있으므로 두 컴포넌트를 $O(\log N)$ 시간에 합칠 수 있습니다. 이러한 연산을 총 $N$번 수행하므로 전체 시간 복잡도는 $O(N \log N)$입니다. Radix sort를 이용해 정점을 정렬하고, $O(N)$ 전처리와 $O(1)$ 쿼리를 지원하는 LCA를 구현한다면 $O(N)$ 시간에도 문제를 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, A[303030], C[303030], D[303030], P[22][303030];
vector<tuple<ll,ll,ll>> E;
vector<tuple<ll,ll,int>> G[303030];
int Active[303030];
void DFS(int v, int b=-1){
    for(auto [i,w,e] : G[v]) if(i != b) P[0][i] = v, C[i] = C[v] + w, D[i] = D[v] + 1, DFS(i, v);
}
int LCA(int u, int v){
    if(D[u] < D[v]) swap(u, v);
    for(int i=0, k=D[u]-D[v]; k; i++, k>>=1) if(k & 1) u = P[i][u];
    if(u == v) return u;
    for(int i=21; i>=0; i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}
ll Dist(int u, int v){
    return C[u] + C[v] - 2 * C[LCA(u, v)];
}
int UF[303030], U[303030], V[303030];
ll M[303030], Diameter[303030], R=LLONG_MIN, ru, rv;
void Init(){
    iota(UF+1, UF+N+1, 1);
    iota(U+1, U+N+1, 1);
    iota(V+1, V+N+1, 1);
    copy(A+1, A+N+1, M+1);
    memset(Diameter, 0xc0, sizeof Diameter);
}
int Find(int v){ return v == UF[v] ? v : UF[v] = Find(UF[v]); }
void Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return;
    UF[u] = v; M[v] = max(M[v], M[u]);
    vector<int> can = {U[u], U[v], V[u], V[v]};
    for(int i=0; i<4; i++){
        for(int j=i+1; j<4; j++){
            int x = can[i], y =can[j];
            ll dist = Dist(x, y);
            if(dist > Diameter[v]) Diameter[v] = dist, U[v] = x, V[v] = y;
        }
    }
    if(Diameter[v] - M[v] > R){
        R = Diameter[v] - M[v];
        ru = U[v]; rv = V[v];
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; E.resize(N-1);
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<N; i++) get<0>(E[i-1]) = i;
    for(auto &[u,v,w] : E) cin >> v;
    for(auto &[u,v,w] : E) cin >> w;
    for(int i=0; i+1<N; i++){
        auto [u,v,w] = E[i];
        G[u].emplace_back(v, w, i);
        G[v].emplace_back(u, w, i);
    }
    DFS(1);
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
    vector<int> O(N);
    iota(O.begin(), O.end(), 1);
    sort(O.begin(), O.end(), [](int x, int y){ return A[x] < A[y]; });
    Init();
    for(auto v : O) for(auto [i,w,e] : G[v]) if(Active[e]++) Merge(v, i);
    cout << ru << " " << rv;
}
고등부 3번. 점프
러프하게 요약하면, DAG 가 주어졌을 때 각 정점에서 도달할 수 있는 정점의 수를 세는 문제입니다. 그래프를 naive하게 만들면 간선이 $O(N^2)$개라는 것, 그리고 일반적인 그래프에서 이런 문제는 $O(N^2)$보다 빠르게 풀 수 없다는 문제점이 있습니다. 문제의 성질을 이용해서 이 두 가지 요소를 풀어나가는 것이 핵심입니다.
아래 두 가지 성질을 관찰합시다.
만약 $X_i < X_j$ 이고 $(X_i, i)$ 에서 $(X_j, j)$ 로 가는 경로가 있다면, $X_i \le X_k$ 인 $(X_k, k)$ 들만 사용해서 가는 경로가 존재한다.
$X_i < X_k \le X_i + D$ 인 가장 작은 $k$를 $p_{i,R}$ 라고 하자. $X_i < X_j$ 이고 $(X_i, i)$ 에서 $(X_j, j)$ 로 가는 경로가 존재한다면, $(X_{p_{i,R}}, p_{i,R})$ 에서 $(X_j, j)$ 로 가는 경로가 존재한다.
여기에서 $p_{i,R}$은 $(X_i, i)$ 보다 오른쪽에 있으면서 한 번에 갈 수 있는 가장 낮은 발판이라고 생각할 수 있습니다.
(1)은 어렵지 않게 증명할 수 있고, (2) 또한 (1) 을 관찰했다면 어렵지 않게 증명할 수 있습니다. 따라서 $i$의 왼쪽과 오른쪽에서 각각 갈 수 있는 가장 낮은 발판으로 가는 간선, 그리고 자신의 바로 위로 갈 수 있는 가장 낮은 발판으로 가는 간선만 추가해도 그래프의 정보를 온전히 나타낼 수 있습니다. 세그먼트 트리 등을 사용하면 $O(N \log N)$ 시간에 모든 간선을 구할 수 있고, 이를 통해 간선을 $O(N^2)$개에서 $O(N)$개로 줄일 수 있습니다. 구체적인 방법은 아래 코드를 참고하시면 됩니다.
이제 도달 가능한 정점의 수를 빠르게 세야 합니다. DP를 다음과 같이 정의합시다.
$D_L(i) :=$ $X_j < X_i$ 이면서 $(X_i, i)$ 에서 도달 가능한 $(X_j, j)$ 의 개수
$D_R(i) :=$ $X_i < X_j$ 이면서 $(X_i, i)$ 에서 도달 가능한 $(X_j, j)$ 의 개수
$D_U(i) :=$ $X_i = X_j$ 이면서 $(X_i, i)$ 에서 도달 가능한 $(X_j, j)$ 의 개수
$D_U(i)$ 는 단순히 $i < j$ 이고 $X_i = X_j$ 인 $j$의 개수를 세면 됩니다. 모든 $i$에 대해 $D_U(i)$를 $O(N \log N)$에 구하는 다양한 방법이 있습니다.
$D_R(i)$ 는 우선 $D_R(p_{i,R})$의 값을 가져오면 $X_{p_{i,R}} < X_j$ 인 $(X_j, j)$는 모두 커버할 수 있습니다. $X_i < X_j \le X_{p_{i,R}}$ 인 발판을 추가로 세어야 하는데, 정의의 따르면 $X_{p_{i,R}} \le X_i + D$ 이므로 $X_i < X_j \le X_{p_{i,R}}$ 인 $(X_j, j)$ 는 모두 $(X_i, i)$ 에서 도달할 수 있습니다. 따라서 $i = N, N-1, \cdots, 1$ 순으로 처리하면서 세그먼트 트리 등을 이용해 $i < j$ 이고 $X_i < X_j \le X_{p_{i,R}}$ 인 $j$의 수를 매번 $O(\log N)$ 시간에 구할 수 있습니다.
$D_L(i)$는 $D_R(i)$와 같은 방식으로 구하면 됩니다.
$p_{i,L}$과 $p_{i,R}$을 구하는 것, 그리고 $D_L$, $D_R$, $D_U$ 를 계산하는 것 모두 $O(N \log N)$ 시간에 수행할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 19;
constexpr int INF = 0x3f3f3f3f;
namespace min_segment_tree{
    int T[SZ<<1];
    void init(){ memset(T, 0x3f, sizeof T); }
    void update(int x, int v){
        for(x|=SZ; x; x>>=1) T[x] = min(T[x], v);
    }
    int query(int l, int r){
        int res = INF;
        for(l|=SZ, r|=SZ; l<=r; l>>=1, r>>=1){
            if(l & 1) res = min(res, T[l++]);
            if(~r & 1) res = min(res, T[r--]);
        }
        return res;
    }
}
namespace fenwick_tree{
    int T[SZ];
    void add(int x, int v){ for(x+=3; x<SZ; x+=x&-x) T[x] += v; }
    int get(int x){ int r = 0; for(x+=3; x; x-=x&-x) r += T[x]; return r; }
    int get(int l, int r){ return l <= r ? get(r) - get(l-1) : 0; }
}
int N, D, X[303030], L[303030], R[303030];
int LD[303030], RD[303030], UP[303030];
vector<int> C;
vector<int> PrvL[303030], PrvR[303030];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> D;
    for(int i=1; i<=N; i++) cin >> X[i];
    C = vector<int>(X+1, X+N+1);
    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    for(int i=1; i<=N; i++) X[i] = lower_bound(C.begin(), C.end(), X[i]) - C.begin();
    min_segment_tree::init();
    for(int i=N; i>=1; i--){
        int lo = lower_bound(C.begin(), C.end(), C[X[i]] - D) - C.begin();
        int hi = upper_bound(C.begin(), C.end(), C[X[i]] + D) - C.begin() - 1;
        L[i] = min_segment_tree::query(lo, X[i]-1);
        R[i] = min_segment_tree::query(X[i]+1, hi);
        if(L[i] < INF) PrvL[L[i]].push_back(i);
        if(R[i] < INF) PrvR[R[i]].push_back(i);
        min_segment_tree::update(X[i], i);
    }
    for(int i=N; i>=1; i--){
        fenwick_tree::add(X[i], 1);
        UP[i] = fenwick_tree::get(X[i], X[i]);
        for(auto j : PrvL[i]) LD[j] = LD[i] + fenwick_tree::get(X[i], X[j]-1);
        for(auto j : PrvR[i]) RD[j] = RD[i] + fenwick_tree::get(X[j]+1, X[i]);
    }
    for(int i=1; i<=N; i++) cout << LD[i] + RD[i] + UP[i] << " ";
}

2026 KOI 1차대회 실기 문제 풀이

댓글