제4회 청소년 IT 경시대회 참가 후기

 

 

 

3월 16일 14시 30분부터 17시 30분까지 알고리즘부 대회가 열렸고, 나는 중등부로 참가했다. 작년에 참가한 적이 있었지만 알고리즘 공부를 하지 않았던 탓에 장려상에 그쳤고, 이번에는 근 몇달간 열심히 해왔기에 괜찮은 결과를 기대하고 대회에 임했다. 중등부의 문제는 3문제가 출제되었다.

 

(3/21 추가) 대상을 받았습니댜!!! 

근데 왜 0%임

 

0:00 ~ 0:06 : #A 격자 막기 - WA 0점

3회때는 A번 조차도 G4 난이도로 나온 걸로 아는데, 이번 대회는 난이도 커브가 상당히 쉽게 조절된 듯 하다. A번은 각각 길이 $N$의 이진 배열 두 개가 주어지고, 이 때 1인 칸에선 다른 1인 인접한 칸으로 이동할 수 있을 때 $(1, 1)$에서 $(N, 2)$까지 이동을 하지 못하게 만들려면 1을 0으로 최소 몇 개 만들어야 하는지 구하는 문제이다. 문제를 읽자마자 구현을 시작했다. (1, 0 / 0, 1), (0, 1 / 1, 0), (0 / 0)이 나온다면 애초에 이동이 불가능하므로 0, 모두 1이라면 2, 두 케이스 모두 아니라면 1을 출력하면 되는 간단한 문제이다. 실버 하위정도를 예상한다. 근데 다만 멍청하게도

for(int i=0;i<n;i++) {
        for(int j=0;j<2;j++) {
            int k; cin >> k;
            arr[i][j] = k;
            sum += k;
        }
    }

입력을 이따구로 받아버리는 바람에(...) 한번 틀렸다.

 

0:06 ~ 0:09 : #A 격자 막기 - AC 100점 (+100)

멍청한 실수를 찾아내고 AC를 받아냈다. 이상한 실수를 한 이슈로 말린 느낌이였다.

 

0:09 ~ 0:24 : #B 물류 작업 최적화 - WA 111점 (+11)

$1\le i\le N$인 모든 $i$에 대해, $i$를 포함하면서 연속된 구간합의 최대를 구해야 하는 문제이다. 약간의 생각을 해보면 누적합을 통해 가능하다는 걸 알 수 있다. 근데 정확한 식은 구간 $[l, i-1]$의 최대 합+$a[i]$+$\max(\max_{i+1\le j\le N} sum[j]-sum[i], 0)$라는 걸 알 수 있는데, 앞의 최대 합은 적당한 그리디로 처리한다고 해도 뒷부분이 약간 문제가 될 수 있다. 세그를 통해선 당연히 가능하지만, 오버킬이라는 느낌이 드므로 누적 max 배열을 만들어서 배열의 역으로 값을 정해가면서 $O(N)$에 전처리할 수 있다. 이게 가능한 이유는 max를 할 구간의 끝부분이 항상 정해져 있기 때문이다. 나는 이 풀이를 내고도 WA를 받았는데, mn배열의 값을 0으로 해뒀기 때문이다. 또 멍청한 실수로 WA를 받았다. 골드 하위정도를 예상한다.

 

0:24 ~ 0:29 : #B 물류 작업 최적화 - AC 200점 (+89)

저 문제를 수정하고 AC를 받아냈다. 또 멍청 이슈였다. 그 사이에 WA 하나도 있었다.

 

0:29 ~ 2:27 : #C 계단 보행 / WA 200점

정점 $N$개, 가중치가 있는 간선 $M$개의 그래프가 주어진다. $1$번 정점에서 $i=1, 2, \cdots, N$번 정점까지 가는 최단 거리를 구하여라. 단, 이 최단 거리를 지나는 간선들의 가중치를 순서대로 나열했을 때 계단 수열이여야 한다. 계단 수열이란 인접한 요소의 차가 1인 수열을 말한다. 최단 거리는 지나는 간선의 개수로 세며, 지난 간선이나 정점을 두 번 이상 방문해도 된다. 상당히 어려웠던 문제였다. 그래프를 평소에 즐겨 풀지도 않고 테크닉도 잘 몰라서 할 수 있을 것 같은걸 다 해봤다. dfs tree도 만들고, 다익스트라도 써볼려 하고, dp(?)도 해볼려 하고, 별 난리부르스를 쳐봤다. 그러다가 정점을 분할해보자는 생각이 들었고, (N, i)->N번 정점의 가중치가 i인 정점을 만들자는 아이디어를 냈다. 여기서 자연스럽게 필요한 가중치 부분만 가져다 쓰다 보면 4M 수준에 bound가 된다는 걸 눈치챘다. 대회 후에 딴 사람들과 대화하며 알았는데, 딱 저 아이디어 까지가 11점 서브태스크고 내가 생각한 부분까지가 풀테스크라고 한다. bfs할 때 모든 (1, i) 정점에서 동시에 시작하게 구현한 후 bfs를 통해 최단거리를 구하였다. 그 중 (k, i)에서 모든 가능한 i에 대해 최단거리가 최소인 것을 k의 최단거리로 정하면 되었다. 이를 구현했으나, 맞왜틀을 당했다. 분명 맞는 것 같았는데, 1번 서브태스크도 돌지 않았다.

 

2:27 ~ 2:42 : #C 계단 보행 / WA 200점

무수히 많은 맞왜틀을 당했다. 틀릴 것 같은 배열 range나 뭔가 잘못된 것 같은걸 다 뜯어고쳤는데 자꾸 틀렸습니다만 받았다. 왜 11점도 나에게 주지 않는가.. 시간이 18분 남은 터라 무척 쫄렸다.

 

2:48 : #C 계단 보행 / AC 300점 (+100) / ALL SOLVE!

절규하던 중, 반포기 상태로 그냥 방문 체크를 한 번 더 하는 코드를 넣어보았고 돌렸다. 

     ///외안ㄷㅎ도림ㅇㄴ룀ㅇㄴ란ㅇㄹㅇㅁㄹ아니왜안ㄷ홰어이가없네이게왜않됨하아ㅓ어람닝럼ㅇㄹㅇㄻㅇㄹ
    //분명맞게햇는데시복도되는데왜서브태스크1도안되는거야하아아아
    //매핑함수도잘짠거같은데대체어디가문제인거지맞왜?틀 반례일만한것도다찾아봣는데하아아아아아어이가없네ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
    //무슨일이생겻나요무슨걱정잇나요마음대로안되는일오늘잇엇나요

AC코드에 있던 주석이다. 사실 저걸 제출한 이유는 이 주석 내용을 내 코드를 보고 있을지도 모를 출제진 분께 전달하고 싶었다. 근데 그렇게 우연히 낸게 AC를 받았다. 난 아직도 아까건 WA인데 저게 왜 AC를 내는 코드인지 알지 못한다. 12분을 남기고 올솔을 했고, 정말 행복했다. 프리즈 전까지 211점이 최대였어서, 300점이 많지 않을거라고 생각했다. 실제로 중등부 300점은 아직 듣지 못했는데, 왜인지 있을 것 같다. 물론 없으면 대상이라 좋지만,,. 프리즈 전 1등이였던 사람이 AB 퍼솔인 터라 아직 장담하긴 힘들 것 같다. 그래도 대상 받길 기대하고 있다(...) 

 

나름 최선을 다해서 풀었고, 그에 대응하는 좋은 결과를 받은 것 같다. 그 다음이 대회 썰은 바로 다음날에 있을 피갤컵 얘기로 이어질 것 같다. 노력한 만큼 실력이 는 것 같아서 만족한다. 마지막으로 나의 채점 현황 이미지로 이 글을 마친다.