2026 05.10 정보올림피아드 1차 후기

종료 후 3시간 뒤에 남기는 따끈따끈한 후기이다.
결론부터 말하자면 2교시는 어느정도 만족하지만 1교시 이산수학이 많이 아쉬웠던 시험이었다.
 
 
일단 2교시 문제부터 알아보자.

 
 
00:00 ~ 00:12
학생들의 집이 수직선 상의 좌표로 주어졌을 때, 왼쪽 오른쪽으로 k1/ k2 만큼 떨어져 있는 사람들의 수를 구하는 문제였다.
문제를 처음 읽고는 pq인가?, n제한이 50만이라서 뭔가 정렬을 해야 할 것 같긴 한데...와 같은 여러가지 생각을 했다.
예제를 직접 종이에 그려보고 각 학생별로 집의 좌표 x 주변의 범위 내에 있는 학생들의 수를 빠르게 구하는 방법은 뭘까? 라는 생각을 하며 풀이의 단서를 찾아나갔다.
 
00:12 ~ 00:16
학생의 학교를 인덱스로 하여 같은 학교의 학생끼리만 정보를 저장해놓은 이차원 벡터와 전체 학생들을 모두 담아놓은 배열 하나를
각각 정렬해준 후, upper_bound를 사용하여 O(logN) 만에 k만큼 떨어져있는 학생들을 같은 학교 학생, 모든 학생 대상으로 각각 구해준 후, 더해주면 된다는 생각이 떠올랐다.
 
00:16 ~ 00:42          1번 AC
구현했다. 이탐 함수를 두개를 각각 짜느라 조금 오래 걸렸다. 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> pos(505050);
vector<pair<int, int>> v, input;
int pbs(int x, int idx) {
    int s, e, mid;
    s = 0;
    e = pos[idx].size();
    while(s < e) {
        mid = (s+e)/2;
        if(pos[idx][mid] <= x) {
            s = mid+1;
        }
        else {
            e = mid;
        }
    }
    return s;
}
int vbs(int x) {
    int s, e, mid;
    s = 0;
    e = v.size();
    while(s < e) {
        mid = (s+e)/2;
        if(v[mid].first <= x) {
            s = mid+1;
        }
        else {
            e = mid;
        }
    }
    return s;
}
int main() {
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    for(int i = 0; i < n; i++) {
        int x, s;
        cin >> x >> s; 
        input.push_back({x, s});
        pos[s].push_back(x);
        v.push_back({x, s});
    }
    for(int i = 0; i <= n; i++) {
        sort(pos[i].begin(), pos[i].end());
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++) {
        int x, s;
        x = input[i].first;
        s = input[i].second;
        int a, b;
        a = pbs(x+k1, s) - pbs(x-k1-1, s);
        b = (vbs(x+k2) - vbs(x-k2-1)) - (pbs(x+k2, s) - pbs(x-k2-1, s));
        cout << a+b-1 << " ";
    }
}

 
00:42 ~ 00:50 
2번 문제를 관찰했다. n개의 노드의 가중치와 n-1개의 간선의 길이가 주어진 트리가 주어졌을 때, 두 정점 사이의 거리를 S, 정점 사이의 경로에 있었던 모든 노드의 값 중 최댓값을 M이라고 했을 때 S - M의 값을 최대화하는 문제였다. n제한은 마찬가지로 
대충 보니 만점 풀이는 도저히 생각나지 않아 n이 7500일 때를 노려서 풀이를 생각해봤다. 모든 노드에서 dfs를 돌려주고,
S -  M의 최댓값 만을 구해주면 O(n^2)으로 풀 수 있기에 구현을 시작했다. 
 
00:50 ~ 01:10
구현했다.
중간중간에 구현에서 말리는 느낌이 들었다. 역시 나의 약점은 구현력이다...
 
01:10 ~ 01:20         2번 1, 2번 테케 20점
구현 실수를 고치고 부분점수를 긁었다.
 

#include <bits/stdc++.h>
#define int long long
#define Min LLONG_MIN
using namespace std;
int a, b, k;
int val[7550];
int input[15500];
vector<vector<pair<int, int>>> connected(7550);
void dfs(int p, int cur, int dist, int max_node, int s) {
    if(p != -1) {
        if(dist - max_node > k) {
            a = s;
            b = cur;
            k = dist - max_node;
        }
    }
    for(auto x : connected[cur]) {
        int c, d;
        c = x.first;
        d = x.second;
        if(c == p)continue;
        dfs(cur, c, dist+d, max(max_node, val[c]), s);
    }
}
int32_t main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    for(int i = 1; i <= 2*n-2; i++) {
        cin >> input[i];
    }
    for(int i = 1; i <= n-1; i++) {
        int u, d;
        u = input[i];
        d = input[i+n-1];
        connected[u].push_back({i, d});
        connected[i].push_back({u, d});
    }
    k = Min;
    for(int i = 1; i <= n; i++) {
        dfs(-1, i, 0, val[i], i);
    }
    cout << a << " " << b;
}

 
01:20 ~ 01:40
3번 테케를 긁다가 시간이 끝났다.
1, 2번은 긁을 수 있었던 것 같은데... 아쉽다.


2교시 총점은 120점으로 1번을 AC를 받았다는 것에 의의를 둔다.

근데 이번에는 1교시 전략을 정말 잘못 짠 것 같다.
이산수학 초반 문제와 인터랙티브 1문제에서 말려서 시간을 너무 날려보낸 것 같다..

우선 다른 사람들과 맞춰본 결과 1교시 점수는 53점이 나왔다.

1+2교시 173점이면 장려컷에 걸릴 것 같은데...

이번 정올 목표가 수상권이었으니 가채점표가 나올 때까지 기도해야겠다.

ps 공부를 계속해야겠다.
공부하자 공부!

 

 

+

가채점

 

야호~~

내가 동상이라니..

2차 때까지 열심히 공부해서 수상권 안에 들자!