2022 ICPC Seoul 후기

올해 처음 알고리즘 공부를 시작했지만 매우 노력하는 모습을 보여준 같은 동아리 팀원 a, b와 ICPC 예선부터 치르게 되었다. 작년에 같이 나간 팀원들은 졸업반이었기 때문에 이번에 새로운 팀원들과 함께 하게 되었다. 예선 전에는 같이 동아리방에 모여서 전년도 기출문제들을 시간 재서 풀어보거나 공부는 각자 알아서 진행하게 되었다.

 

우리학교에서는 총 두 팀이 예선을 치르게 되었는데 처음 목표를 본선만 가자 라는 마인드로 준비하였다.

문제들을 펼쳐서 읽어봤을 때 가장 먼저 E번을 보고 풀이를 떠올려낸 a가 코드를 짜기 시작했다.

A번은 읽어봤을때 쉬운 dp일 수 있다는 생각이 들어서 우선 두고

b와 같이 C번에 대한 아이디어를 내고 풀이를 적었다.

 

E (00:15)

그리디형 구현으로 가장 싼 물건들을 가장 비싼물건들을 할인하면서 사는 문제였다.

자체 테스트케이스도 만들고 통과하자 제출하여 정답이 되었다.

 

C (00:21)

이것도 그리디한 방식으로 전체합 을 구하면 특정 높이의 컨테이너가 몇개 있는지를 알 수 있어서

정렬 한 후에 특정 높이에 대해서 높은 컨테이너와 낮은 컨테이너 개수를 절대값으로 빼주면서 진행하면된다.

 

A (00:29)

많은팀이 첫문제로 A를 풀었고 읽어봤을때 그리디, 구현으로 풀린다고 생각되어

문제에서 요구하는대로 코드를 짜서 제출 해서 정답을 받았다.

 

K(01:46) [+2]

이 시점에서 다른 한팀보다 문제푸는 속도 차이가 났어서 1,2 문제 더 풀면 본선 진출이라 생각 되었다.

그리고 G번 K번 을 동시에 보게 되었는데, K번이 이해가 안가서 해석하는데 오래걸렸고 적당한 풀이를 논의하다. 다익스트라나 dp bfs얘기가 나왔고 dp에 자신있던 a가 dp로 K번을 해결하게 되었다.

 

마지막까지 G번을 해결하고자 봤는데, 게임이론 dp 인것 까지는 인지했지만 점화식을 못세워서 시간 안에 해결 하지 못하였다. 4solve로 학교 1위로 본선에 진출하게 됐다.

 

 

본선은 아쉽게도 3솔로 마무리를 하게 되었다.

문제를 처음 펼치고 각자 읽어보고 있을 때 몇개의 팀이 J번을 해결하는것을 보고 바로 J번을 시작하기로 했다.

J (00:19)

스택을 이용한 비슷한 KOI 문제를 풀어봤던 기억이 있어 빠르게 구현하여 제출하여 정답이 되었다.

그리고 다음으로 많이 푼 문제가 I 였는데 읽어봐도 해답이 생각나지 않았고 F번이 풀만하다고 판단되어 각자 아이디어를 내서 F번을 코드 짜는 사이에 I번을 고민하고 있었다.

 

I (02:06)

F번 풀다가 내 풀이를 듣더니 a가 뚝딱 코드를 짜서 제출하여 정답을 받았다. 양 끝에서 시작하는 투포인터인데 팰린드롬인지를 확인하면서 다른 단어면 dfs 느낌으로 들어가는 재귀 코드를 짰다.

 

F (02:15) [+2]

같은 영역에 있는 부분을 union-find로 합치고 좌표압축과 prefix sum으로 최적화해서 코드를 짜서 제출했는데 예제 테케는 통과했지만 WA를 받아서 디버깅을하였다. 디버깅 하는 동안 I번 해답을 생각해냈지만 F번 완성하는게 먼저라고 생각되어 틀린부분을 찾으면서 점심 샌드위치를 먹었다. 

 

K, E

K번은 DP문제라 자신있던 a가 잡았지만 결국 해결하지 못했고 e번은 다익스트라라는걸 알았는데 at most 10이라는 내용을 못보고 구현하다 시간이 부족해서 해결하지 못했다.

 

후기)

시험장 처음들어왔을때 앞에 있는 풍선들을 보고 각자 풍선들 하나씩은 가져가자는 마인드로 시작했지만 풀수 있었을 것 같았던 문제들을 못풀었던 것은 조금 아쉬웠던 것같다. 그리고, 나포함 팀원들 모두 더 높은 목표를 가지고 공부하는 계기가 될 수 있었 던 것 같다. 내년에는 더 열심히해서 더 많은 같은학교 학생들을 데려오고 싶다. 다른 학교들 중 같은 학교 나온 학생들이랑 서로 이야기하는게 조금 부러웠던 것 같을지도