2020 ICPC Seoul Regional 후기

우리나라에서 가장 큰 팀 프로그래밍 경진 대회라고 할 수 있는 ICPC regional이 끝났습니다. 이로써 제가 대학생활 4년동안 준비했고, 수상하기를 원했던 모든 대회가 끝났네요. 모두 좋은 결과를 얻게 되서 너무 행복합니다 ㅎㅎ…

스코어보드

저는 오존이라는 팀으로 참가했고, 7 solve, 14등을 하면서 수상 막차를 탑승했습니다 :)

문제 풀이

간단하게 대회에서 풀었던 문제 또는 풀이를 아는 문제를 정리해보겠습니다. 문제지는 http://static.icpckorea.net/2020/problemset.pdf 에서 확인할 수 있습니다.

A. Autonomous Vehicle

정말 힘든 구현문제입니다. 문제에서 시키는대로 구현하면 되지만 시키는대로 구현하는게 쉽지 않습니다. 대회에서 한번만 틀리고 바로 맞아버린 갓 McDic…

B. Commemorative Dice

리저널에 참가한 모든 팀이 해결한 문제입니다. 설명은 하지 않겠습니다 :)

C. Desert Cafe

많은 팀이 풀었고 저희 팀도 풀었지만, 문제를 잘못 이해해서 꽤 고생했던 문제입니다.

트리 모양의 지도에 있고 몇개의 노드는 아파트 단지입니다. 여기서 좋은 노드 의 개수를 구하는 문제인데, 좋은 노드 란 자신($x$)을 제외한 다른 모든 노드($y \in Tree $)와 비교하였을때 $d(x,z) < d(y,z)$ 인 $ z \in Aparts $가 존재하는 노드입니다.

$x$와 연결되어 있는 모든 간선에 대해서, 간선을 타고 여행하다가 아파트를 만날 수 있는 간선을 세어 그 수가 2 이상이라면 좋은 노드입니다. 그림을 그려보면 쉽게 증명이 가능합니다.

D. Electric Vehicle

못 풀었습니다…ㅜㅜ 추후에 풀이를 알게 되면 업데이트 하겠습니다.

E. Imprecise Computer

문제 이해가 어렵지만 이해만 한다면 쉬운 문제입니다. 다른 팀원 _Rebellion이 빠르게 잘 풀었기에 대회가 끝나고 나서야 읽어봤습니다. :)

difference가 1인 경우만 고려하면 되기 때문에, 입력으로 주어진 배열에서 이전 값만 고려하여 true false를 결정하면 됩니다.

F. Ink Mix

SCC+DAG 문제인줄 알고 제가 받았지만, 호스 추가 조건 때문에 풀지 못했습니다. 찾아보니 Dominator Tree를 사용해서 풀었다는 글을 봤는데, 처음 들어보는 자료구조입니다. ㄷㄷ

G. Mobile Robot

이분탐색 문제입니다. SCPC에서도 비슷한 문제가 있었던걸로 기억합니다. 뒤에 소수를 출력할때 .5 / .0 밖에 나오지 않으므로 소수 변환하여 실수 오차 유발 하는것 보다는 string으로 출력하는게 좋습니다. (대회에서 WA를 받았다가 string으로 고쳐서 맞았습니다.)

H. Needle

FFT 문제입니다. $ a_i+c_k=2 \times b_j $ 를 만족하는 $(i,j,k)$ 쌍을 찾는 문제였습니다.

$a_i, b_j, c_k$의 범위가 60,000으로 작기 때문에 $a_i, c_k$ 값의 개수를 배열에 저장하여 합성곱으로 생각할 수 있습니다.

대회에서는 _Rebllion이 이거 FFT인데요? 하고 FFT 전문가인 McDic에게 넘겨서 잘 풀었습니다 :)

I. Stock Analysis

-INF로 초기화된 2차원 좌표 공간에서 오프라인 쿼리로 u보다 작은 값을 추가하면서 최대값을 찾는 방식으로 시도했습니다.

2차원 세그트리를 구현해서 $(n^2+m)log(n)$ 으로 짜고(복잡도에 곱해지는 상수항이 8쯤), 예상대로 TLE를 받았습니다. 그런데 이게 정해…인 듯 합니다.(시간제한이 2초인데??)

$n^2log^2(n)$에서 펜윅으로 짜고 맞았다고 하니(펜윅은 상수항이 1/8이라고 하는데 이유는 모르겠어요 ㅋㅋ) 최적화 시도해볼 걸 그랬나 아쉽습니다.ㅜㅜ

J. Switches

행렬 DP 문제입니다. Gaussian Elimination을 사용하면 된다는데 행렬 DP는 든든한 두 팀원이 알아서 처리했었고 제가 선형대수학은 잘 기억이 나지 않아 설명은 생략합니다. :)

K. Tiling Polinomio

못 풀었습니다…ㅜㅜ 추후에 풀이를 알게 되면 업데이트 하겠습니다.

L. Two Buildings

World Final 2017 Money for Nothing 이라는 문제의 아이디어와 일치한다고 합니다. 팀원들이 two pointer로 푸는 방법을 고민하다가 대회 시간이 종료되었던 문제입니다.

Special Thanks to

너무나 좋은 퍼포먼스를 보여준 팀원 Mcdic, _Rebellion 고마워! 덕분에 졸업 전에 ICPC 수상하고 싶다는 소원을 이뤘네

3년동안 공부만 하는데도 ‘내 실력이 늘고 있는게 맞나?’ 라는 회의감이 정말 많이 들었었는데, 공부 방향을 잡아주고 모르는거는 가르쳐주신 2019 World Final 팀 Powered by Zigui 팀!! 항상 감사하고 있습니다. 일정이 많이 연기됐지만 월파에서 좋은 성적 받아 오시길 기원합니다!

BOB 때문에 바쁜 BeefCharisma 항상 멘탈 흔들릴때 얘기 들어주고 응원해줘서 고마워!!