제6회 청소년 IT 경시대회 후기(고등부)

한국정보진흥기술원에서 주관하는 제6회 청소년 IT 경시대회에 참가했습니다. 4문제를 3시간 30분 동안 푸는 대회였고, 결과적으로 400점 만점에 220점을 받았습니다. 아무래도 A,B,C를 풀고 300점 이상인 사람은 꽤 있을 거 같아 동상이나 장려상 정도라도 받으면 좋겠다고 생각하고 있습니다.

A. 체스판 다시 칠하기 — 100/100#

이미 색칠된 검은색 칸들의 좌표 $(x, y)$에 대해, $x + y$의 parity가 모두 같으면 YES, 아니면 NO입니다.

B. 감시자 — 20/100#

섭테 1은 모든 노드에 대해 $A_{i} = 1, B_{i} = 0$이기 때문에, 단순히 1번 노드에서 가는 최단시간을 출력하면 됩니다. 빠르게 20점을 긁었습니다.

이후에 더 고민을 해봤는데, 섭테 2를 긁기 위해 주기성을 이용해서 bfs로 각 노드마다 가능한 시간을 갱신해주는 풀이가 떠올랐습니다. 하지만 최솟값만 갱신하면 된다는 걸 간과하고 모든 $t$에 대해 가능/불가능 여부를 관리하려고 삽질하다 결국 던졌습니다.

만점을 받으려면 $t \bmod 2520 = i$인 최솟값을 정점에서 관리하면서 다익을 돌리면 된다고 합니다. $2520 = \operatorname{lcm}(2, \cdots, 10)$입니다.

C. 로봇 청소기 — 100/100#

왼쪽 끝까지 간 뒤 오른쪽으로 쭉 먼지를 없애는 방법과, 오른쪽으로 끝까지 간 뒤 왼쪽으로 쭉 먼지를 없애는 방법 중 더 최소인 걸 고르면 됩니다. 먼지를 없앨 때는, 현재 $i$번째 칸에 위치해 있을 때 $i$번째 칸과 $i + 1$번째 칸(오→왼인 경우 $i - 1$번째 칸)을 왔다갔다 하며 $a[i] = 0$이 될 때까지 반복하면 항상 최적입니다. 엄밀하게 증명해보진 않았고, 몇몇 개의 테케를 직접 손브포해서 관찰할 수 있었습니다.

$s < l$인 케이스는 오→왼으로 가는 방법에서 자연스럽게 커버할 거라고 생각해 배제했는데, 이거 때문에 50점에서 계속 맞왜틀 당해서 40분은 넘게 잡아먹었습니다.

D. 구간과 쿼리 — 0/100#

섭테 1을 긁어보려고 스위핑 비슷한 풀이를 냈습니다. 구간을 항상 시작점 기준 오름차순 정렬된 상태로 유지하면, 3번 쿼리마다 $[p, q]$에서 $p \le l; \, r \le q$를 만족하는 구간들에서 최대한 많은 구간을 안 겹치게 선택하는 걸 $O(N)$에 할 수 있습니다. 사실 원래는 끝점 기준으로 정렬하는 게 정석이지만, 시작점 기준으로 해도 지금 보고 있는 구간이 이전 구간의 끝점보다 일찍 끝나면 갱신해주는 방식으로 같은 효과를 낼 수 있습니다. 문제는 이렇게 낸 $O(NQ)$ 풀이가 섭테 1부터 WA를 받았다는 것입니다. 구현 실수가 있던 것 같은데 예제는 또 잘 돌아서.. 디버깅하다가 대회가 끝났습니다. 개인적으로 굉장히 아쉽습니다.

친구한테 들은 정해는 세그 2개로 구간 개수하고 실제 겹치지 않는 최대 구간 개수를 각각 관리를 하는 거라고 하는데, 이걸 대회 중에 어떻게 생각해요..

개학하고 할 일이 산더미라 PS를 마냥 재밌게 계속할 수만은 없던 상황이었는데, 대회 준비라는 명목으로라도 열심히 한 것에 만족합니다. 기출을 풀다 보니 세그가 너무 많이 나와서 lazy seg 템플릿까지 외우고 갔는데, 문제로 나왔음에도 써먹지를 못해서 아쉽네요.