2024 한국정보올림피아드 고등부 1차 대회

2024년 5월 12일에 한국정보올림피아드를 응시했습니다. 리뷰입니다.

1교시

• 1교시는 80분 동안 20개의 비버챌린지형 문제를 푸는 시험입니다.
• 문제를 하나하나 돌아볼 필요는 없는 것 같고, 여러 개 묶어서 보겠습니다.
• 1~4번: 그냥 슥슥 풀면 풀렸습니다. 3번은 제꼈다가 나중에 다시 돌아와 풀었습니다. 와중에 1번은 틀렸습니다.
• 5번: 제꼈고 다시 풀지 않았습니다. 논리 문제는 푸는 요령이 없어서 그런지 점수 대비 시간이 너무 오래 걸리는 것 같습니다.
• 6~7번: 슥슥 풀면 얘네도 풀렸습니다. 시간이 좀 더 오래 걸리기는 했습니다.
• 8~10번: 시간이 좀 걸리는 것들이었습니다. 맞았는지는 모르겠습니다.
• 11번: 제꼈고 다시 풀지 않았습니다.
• 12번: 시간 안에 완전히 풀지 못했고, 찍었으나 틀렸습니다. 7까지는 제대로 셌는데 (여기까지만 15분은 쓴 것 같습니다) 8에서 아무리 세도 안 세지더라고요.
• 13번: 자명했습니다.
• 14번: 머리를 조금 굴리긴 했습니다. 근데 몇 번 해보면 2진법적인 무언가가 보여서 풀릴 수밖에 없습니다.
• 15번: 솔직히 이게 최소일 거라고 확신하지 못했습니다만, 어쨌든 맞았으니 된 것이 아닐까요?
• 16번: 코드포스 잘 하면 쉽게 풀립니다.
• 17번: 패리티 비트를 사용하니까 맞았습니다.
• 18번: 그래프를 그리려고 했지만 너무 귀찮아서 뇌리스틱을 썼고(반쯤 찍었다는 뜻입니다) 맞았습니다.
• 19번: 좀 어려웠습니다만, 전략을 세우는 것이 그리 어렵지는 않았습니다.
• 20번: 재밌었습니다. BOJ 25434에서 비슷한 것을 해보기도 했고, 루트질이 그래도 웰논이라서 빠르게 맞을 수 있었던 것 같습니다.
• 총평을 내리고 가면, 시간이 널널하지는 않았습니다. 그러나 작년보다는 쉬웠던 것 같습니다.

2교시

• 2교시는 100분 동안 3개의 문제를 푸는 시험입니다.
• 아래 시간은 정확하지 않습니다.

0:00~0:05 - 0~100

• 1번을 잡았습니다.
• 발상: 그냥 갔다가 오면 됩니다. 그중에 최대 찾으면 됩니다.
• 발상: 그걸 구현하기 위해 max(a[n-1]\*2, a[i]+b[i])를 하면 됩니다.
• 맞았습니다. 100/300

0:05~0:40 - 100~200

• 2번을 잡았습니다.
• 발상: 약간 금광 세그에서 구조체 merge를 구현하는 것과 비슷한 느낌의 merge를 dp식으로 짜면 선형 시간에 문제를 해결할 수 있습니다.
• 배열은 리프 노드, 왼쪽 정렬 금광, 오른쪽 정렬 금광, 답 4가지를 추가로 관리해야 합니다.
• 짜고 돌리면서 구현을 구체화해나갔습니다.
• 맞았습니다. 200/300

0:40~0:48 - 200~200

• 3번을 잡았습니다.
• 누적 합의 누적 합을 구하되 음수는 0으로 바꾸어줘야 해서 단순 누적 합은 안 됩니다.
• 풀테는 적절한 금광 세그 비슷한 것으로 될 것 같다고 느꼈습니다.
• 그 이상의 구체화가 되지 않았습니다.

0:48~0:55 - 200~212

• 3번의 서브태스크 2를 잡았습니다.
• N제곱이 돌아가므로, N^2개를 모두 전처리하면 됩니다.
• 섭테 1, 2를 맞았습니다. 212/300

0:55~1:10 - 212~222

• 3번의 서브태스크 4를 잡았습니다.
• 누적 합의 누적 합에 음수가 나오지 않아 그냥 N에 대해 선형으로 구해도 됩니다.
• 섭테 4를 맞았습니다. 222/300

1:10~1:20 - 222~227

• 3번의 서브태스크 5를 잡았습니다.
• 모든 원소가 1 아니면 2이므로 일정 포인트 뒤의 원소를 모두 2로 만들면 됩니다.
• 다음 2의 위치와 구간 내 2의 개수를 관리하면 됩니다.
• 섭테 5를 맞았습니다. 227/300

1:20~1:30 - 227~227

• 3번의 서브태스크 6을 잡았습니다.
• 섭테 5에 로그를 붙이면 섭테 6을 같은 방법으로 짤 수 있습니다.
• 그러나 시간이 부족해 짜다 말았습니다.

1:30~1:40 - 227~227

• 놀았습니다. 227/300

후기

1교시는 129점으로, 총점 356점 (20등 / 상위 2.8%)이 나왔습니다. 생각보다 1교시 중반부 문제를 많이 틀려서 아쉽습니다만, 그래도 시험을 보면서 생각했던 기대치보다는 적당히 괜찮게 나온 것 같아서 만족합니다. 마지막 정올을 이렇게 끝낸다고 생각하면 조금 슬프네요. 2차를 노려봐야겠습니다.(그렇다고 2차 금을 노리는 건 말이 안 되는게?)

올해 학교 내 응시자는 131명이라고 합니다. 131명 중 동상 이상이 몇 명이나 나올지는 모르겠습니다. 졸업하기 전에 시트의 50%를 가져오는 모습을 한 번쯤 보고 싶은데, 가능할지 모르겠네요…