본문 바로가기
PS/KOI

2024 정보올림피아드 고등부 2차 후기

by woohyunjng 2024. 8. 1.

2024년 7월 14일에 온라인으로 진행한 KOI 고등부 2차 후기입니다.

 

1. 가로등

0:00 ~ 0:22 : 0 → 10

1번 가로등 문제를 잡았습니다.

먼저, 두 연속한 가로등 사이의 구간을 밝기가 연속적으로 증가하는 두 부분으로 나눴고 이것의 크기를 배열에 넣은 뒤 정렬했습니다. 그리고 이분탐색을 돌리면서 1이 나오는 횟수, 2가 나오는 횟수 등을 K가 될 때까지 구하고 출력해 바로 전체 문제를 노렸습니다. 그러나 1번 섭테에서 10점밖에 받지 못했습니다.

0:22 ~ 0:27 : 10 → 100

다행히도 반례를 빠르게 찾고 만점을 얻었습니다.

코드

더보기 
from sys import stdin
from bisect import bisect_left

input = stdin.readline

L, N, K = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

B = [A[0], L - A[-1]]
for i in range(N - 1):
    M = A[i + 1] - A[i] - 1
    B.append(M // 2)
    B.append(M - M // 2)
B = list(sorted(B))

arr = []
if K >= N:
    K -= N
    for i in range(N):
        arr.append(0)
else:
    for i in range(K):
        arr.append(0)
    K = 0
cur, num = len(B) - bisect_left(B, 1), 1

while K > 0:
    if K >= cur:
        K -= cur
        for i in range(cur):
            arr.append(num)
        num += 1
        M = bisect_left(B, num)
        cur = len(B) - M
    else:
        for i in range(K):
            arr.append(num)
        K = 0

print(*arr, sep="\n")

 

꽤 어렵게 풀어서 솔브닥 기준으로 골드 상위가 나올 거라 예상했고 그렇게까지 많은 사람이 풀 줄은 몰랐으나 시복에 로그도 붙지 않는 더 쉬운 풀이가 존재했었습니다….

 

 

 

2. XOR 최대

0:27 ~ 0:55  : 100 → 200

N의 범위를 고려했을 때, O(N) 풀이만 가능하다고 판단했습니다. 약간의 아이디어가 떠올라 바로 만점 풀이에 도전해 보았습니다.

조금만 생각해 보니, 1의 최대 자릿수가 높을수록 유리하므로 s1은 S와 동일하게 설정하는 것이 최적의 경우라는 사실을 알아내었습니다.

비슷한 논리로, 두 수의 XOR 결과에서 앞에서 1이 많이 연속될수록 좋다는 점을 이용해, S에서 처음 등장한 1의 위치에서 계속 평행이동을 해주면서 s2를 구할 수 있다는 아이디어를 생각해 냈습니다.

그러다가 예제가 나오지 않아 두 가지 예외 케이스가 존재하는 것을 깨닫고 이를 처리함으로써 만점을 받을 수 있었습니다.

코드

더보기 
from sys import stdin

input = stdin.readline

T = int(input())

for t in range(T):
    N = int(input())
    S = input().rstrip()

    S = S.lstrip("0")
    cut = N - len(S)
    N = len(S)

    if not N:
        print("0")
        continue

    if S.count("1") == N:
        if cut > 0:
            print(S)
        else:
            print("1" * (N - 1) + "0")
        continue

    K = 0
    for i in range(N):
        if S[i] == "0":
            break
        K += 1

    A = K
    j = K
    while j < N and K > 0:
        if S[j] == "0":
            K -= 1
        else:
            break
        j += 1

    A = S[K : K + N - A]
    print(bin(int(f"0b{A}", 2) ^ int(f"0b{S}", 2))[2:])

이 문제는 XOR와 애드혹 문제로, 코드포스에서 자주 접할 것 같은 유형이었습니다. 난이도를 고려했을 때 플래티넘 하위 수준일 것으로 예상했고, 2차 대회의 2번 문제 치고는 비교적 쉽게 느껴졌습니다.

어디선가 지금까지의 은 컷은 2문제에서 만점을 받고 섭테를 많이 긁으면 된다는 말을 들었습니다. 이른 시간 안에 200점을 얻어 은상을 받을 수 있겠다는 생각에 기분이 좋았습니다. 실제로도 2번 문제에서 100점을 받아 12등으로 이른 시간에 높은 점수를 얻은 편이었습니다.

 

 

3. 트리 뽑아내기

0:55 ~ 1:18 : 200 → 206

고등부 3번이니깐 최소 플상위겠거니 하는 생각에 천천히 섭테부터 노렸고 나이브로 구현했을 때 가능한 섭테 1을 C++로 구현했고 6점을 받았습니다.

1:18 ~ 1:21 : 206 ~ 216

그 이후에 바로 섭테 2를 잡았는데 섭테 1과 전혀 관련 없이 그냥 정렬만 해서 출력하면 된다는 것을 깨닫고 바로 Python으로 구현해 10점을 받았습니다.

1:21 ~ 1:28 : 216 ~ 227

그리고 섭테 3을 잡았는데 이 친구도 이전 부분 문제와 전혀 관계없이 DFS order을 구해서 출력해 주면 되는 문제라서 바로 구현하고 11점을 받았습니다.

1:28 ~ 2:03 : 227 ~ 227

섭테 4에서 차수가 3 이상인 정점의 수가 20개 이하라는 점을 이용해 차수가 같은 점들을 세그먼트 트리로 관리해 줄 수 있겠다고 생각해서 30분 넘게 구현했습니다. 예제까지 나왔지만 TLE로 터졌습니다. 살짝 보완해 보면 점수를 받을 수 있을 것 같았으나 4번에서 점수를 얻는 게 더 효율적일 것 같아서 4번으로 넘어갔습니다.

 

3:19 ~ 3:43 : 239 ~ 312

4번에서 더 이상 서브테스크를 긁을 수 없게 되자 3번 만점 풀이라도 노려보려고 돌아왔습니다. ETT와 레이지 세그먼트 트리를 잘 결합해서 만점을 얻을 수 있을 거로 생각하고 자세하게 구상하려고 했습니다. 그러다가 비슷한 논리로 우선순위 큐를 이용해 줄 수 있다는 생각이 들었고 실제로 시뮬레이션해 봤을 때 예제가 나와서 바로 구현해 주고 만점을 받았습니다.

코드

더보기 
#include <bits/stdc++.h>
#define int long long
#define MAX 300100

using namespace std;
typedef pair<int, int> pr;

int P[MAX], A[MAX], res[MAX];
vector<int> child[MAX];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, X, cur = 1;
    pr K;
    cin >> N;

    for (int i = 2; i <= N; i++) {
        cin >> P[i];
        child[P[i]].push_back(i);
    }

    for (int i = 1; i <= N; i++)
        cin >> A[i];

    priority_queue<pr, vector<pr>, greater<pr>> pq;
    pq.push({A[1], 1});

    while (!pq.empty()) {
        K = pq.top(), pq.pop();
        cout << K.first << '\n';

        for (int i : child[K.second])
            pq.push({A[i], i});
    }

    return 0;
}

만점 풀이를 증명하고 짜진 않았지만, 구현이 고3치고는 굉장히 쉬웠고 심지어 고2보다 쉽게 느껴졌었습니다. 여기서 뭔가 이상함을 느꼈고 은 컷이 200 후반이 아니겠다고 생각하게 됐습니다.

 

 

4. 점수 경주

2:03 ~ 2:12 : 227 → 229

고등부 4번을 읽고 깊이 생각하지 않고 문제 본문대로 그저 구현만 했더니 섭테 1의 2점을 받았습니다. 상당히 구현량은 많았는데 2점밖에 얻지 못해서 서운했습니다.

 

2:12 ~ 2:43 : 229 → 233

그리고 긁을만한 섭테를 보다가 섭테 4가 할만해 보였고 모든 지점이 시작 지점일 때 S와 C값을 이분 탐색을 이용해 log⁡N의 시간복잡도로 구할 수 있어서 이를 구현했고 몇 번의 WA와 재도전 끝에 4점을 긁었습니다.

 

2:43 ~ 3:19 : 233 → 239

섭테 2를 봤을 때 모든 도로의 점수가 양수라면 그냥 트리 DP라서 이를 생각하다가 구현해 줬습니다. 꽤 쉽지 않았으나 6점밖에 주지 않아 한 번 더 서운했습니다. 알고 보니깐 백준에 이미 존재하는 문제였습니다.

 

섭테 3은 Wi가 음수일 때 -300,000 * 5 이하였다면 만날 때마다 0으로 초기화를 해주면서 이제 트리 DP로 잘 풀 수 있었을 거로 생각했으나 -200,000 * 5 이하여서 전체 문제와 그렇게 다른 것 같지 않아 풀지 않았습니다. 나중에 솔브닥 디코를 보니깐 N 범위를 늘리면서 섭테의 Wi 범위도 늘렸어야 했는데 늘리지 못했다네요…. ㅠㅠㅠ 이걸 긁었으면 금상…. 도 가능했을 수 있으나 그렇더라도 다른 여러 변수에 의해서 가능하진 않았겠죠…!

남은 섭테와 부분 문제는 모두 트리 DP로는 가능해 보이지 않으니 결국 센트로이드 풀이일 것으로 생각했고 당시에는 센트로이드 구현과 활용 방법을 몰랐으므로 4번 긁기를 멈췄습니다.

 

 

대회 끝나고 후기

  • 3번 만점을 받고 더 이상 점수를 올릴 수가 없을 것 같고 생전 처음 받아보는 점수에 너무나도 기뻐서 문제가 풀리지 않아 그만두려고 조기 퇴실 가능 시간 10초 남았을 때 급하게 조기 퇴실했습니다. 이때 조기 퇴실하지 않고 4번의 섭테 3의 조건을 의심하고 구현했었으면 어땠을까라는 생각도 들긴 하는데 제가 30분 안에 풀었을 리가 없기 때문에 후회되진 않습니다~
  • 3번이 상당히 쉬웠고 4번이 어려웠어 은 컷은 300점대 초반일 것으로 생각했고 마침 그 점수라 은상을 기대했었습니다. 그러나 솔브닥 디코에서 만점도 몇몇 보이고 제 위의 점수가 꽤 돼 살짝 불안해서 대회 끝과 가채점 결과 사이 2일 동안 굉장히 떨렸었습니다.
  • 그래도 풀 수 있는 문제는 모두 풀었었어서 상당히 뿌듯했고 센트로이드가 근 3년간 2번이나 출제되었기 때문에 배워야 할 필요성을 느끼게 됐습니다.

 

 

결과

전체 12등을 하고 은상을 받았습니다. 중등부 때는 최대 등수가 2023 KOI 1차 18등 금상, 2차 최대 등수는 2022 KOI 2차 20등 은상이었는데 첫 고등부 시험에서 역대급 등수와 은상이 나와 너무나도 기뻤습니다. 그래도 이 성적이 고점이 되지 않게 앞으로 더욱 PS를 열심히 해야겠죠?

티스토리툴바