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

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

 

upd: 장려상을 받게 되었습니다! B를 풀지 못해서 굉장히 아쉬운 기량이였다고 생각하지만요.. 거의 턱걸이로 상을 받게 되어 감사할 따름입니다.

ㅤ

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$에 대해 가능/불가능 여부를 관리하려고 삽질하다 결국 던졌습니다.

만점을 받으려면 $MOD \, 2520 = i$ 인 최솟값을 정점에서 관리하면서 다익을 돌리면 된다고 합니다. $2520 = 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 \leq l; \, r \leq q$를 만족하는 구간들에서 최대한 많은 구간을 안겹치게 선택하는걸 $O(N)$에 할 수 있습니다. 사실 원래는 끝점 기준으로 정렬하는게 정석이지만, 시작점 기준으로 해도 지금 보고있는 구간이 이전 구간의 끝점보다 일찍 끝나면 갱신해주는 방식으로 같은 효과를 낼 수 있습니다. 문제는 이렇게 낸 $O(NQ)$ 풀이가 섭테 1부터 WA를 받았다는 것 입니다. 구현 실수가 있던 것 같은데 예제는 또 잘 돌아서.. 디버깅하다가 대회가 끝났습니다. 개인적으로 굉장히 아쉽습니다.

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

ㅤ

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