2019 ICPC 인터넷 예선 후기

나름 열심히 준비한다고 했던 ICPC 인터넷 예선이 기대 이하의 성적으로 끝났다. 

 

일단 시작하기 전에 인쇄본 문제지가 10분여 정도 늦게 도착할 예정이라는 공지가 있었고, 뭐 그동안은 등록 내고 한문제 모니터로 보면서 잡고 있으면 되겠지 라고 생각해서 그러려니 했다. 그런데 시작과 동시에 터진 서버는 25분 정도 복구가 안 되었고, 당연히 문제지가 안 보이는 상황에서 인쇄본 문제지가 인쇄될 방법이 없으므로 실제로는 서버가 완전히 복구된 시점쯤에 인쇄본이 도착했다.

그동안 일부 팀들 (사실 대부분의 팀들) 은 몇몇 문제를 볼 수 있었고, 어떤 팀은 전체 pdf 파일 다운로드가 가능했던 팀도 있다. ICPC 대회가 PS에서 갖는 권위를 생각했을 때 이미 역대급으로 망한 상태였다고 생각한다. 

아무튼, 그후에도 문제가 끊이지 않았는데(...) 채점 서버가 오락가락하면서 나중에 낸 제출을 먼저 채점하는 등의 일들이 벌어졌고 (처음에는 각 문제별로 큐를 따로 관리하나 싶었는데, 아무래도 채점 서버가 큐가 아닌 것 같다. 같은 문제에 낸 복수의 제출에 대해 나중에 제출한 코드가 먼저 채점된 팀이 있었다) 90분 시점쯤에 아예 채점이 뻗어버려서, 대회 주최측에서 "대회를 30분 연장하며, 대회 시간 중 제출한 코드는 대회가 끝나고라도 채점하겠다" 라는 공지가 이루어졌다. 즉 내 코드가 맞았는지 틀렸는지를 확인해볼 방법이 없으며, WA를 받은 후 디버깅한다는것 자체가 불가능한 상황이었다. 

오늘 슬랙에서 얘기를 들어보니 형평성을 위해 채점 서버 다수가 뻗은 시점에서 모든 서버를 껐다는 얘기가 있던데, 사실 여부는 잘 모르겠다. 일부 팀이 채점을 받고 일부 팀이 받지 못하는 것보다는 나은...가?

 

우리는 5솔브 (등록 제외 4문제) 를 했고, 5솔브 팀 중에는 페널티가 낮은 편인데 어차피 서울대 컷은 6문제이거나 (희망사항) 7문제일 가능성이 있다는(...) 얘기가 돌고 있으므로 ICPC 대전 본선 진출에는 실패했다. 

 

그 외에도 대회에 대해 이런저런 하고싶은 말들이 많지만, 이건 누구의 문제라기보다는 우리 공부의 문제라고 생각하는 것도 많이 있으니...

---

B. Balanced String

Solve : Gratus907

Code : Gratus907

25분 시점쯤 문제가 열리자마자 스코어보드를 보고 다른 팀들이 서버와 싸우며 B와 H를 제출했음을 알고 B를 먼저 잡았다.

단순히 $2^{n/2 + n \%2}$ 에 주어진 모듈러를 하면 답인데, 어차피 가능한 경우가 10과 01을 아무렇게나 늘어놓고 마지막에 홀수개면 아무거나 하나 더 놓으면 된다는 사실을 관찰하면 된다.

---

H. Four Squares

Solve : Gratus907

Code : Gratus907

우리 모두 서버와 싸우며 제출한 문제 2.

2007년에 출제되었던 https://www.acmicpc.net/problem/1699 문제가 $n$ 제한만 바뀌어서 다시 출제되었다. 제한을 늘린게 아니라 제한을 반으로 줄여버렸기 때문에 (...) $O(n \sqrt{n})으로 dp 테이블을 채우면 된다.

---

C. Bytecoin

Solve : Coffeetea, Diordhd

Code : Gratus907

Coffeetea가 문제를 보며 가끔 사용하는 '빙의' 가 활용되었다.

어떤 코인의 가격 등락 그래프가 주어질 때 최대한 많은 돈을 버는 방법을 찾는 문제인데, 누구나 극소에서 사서 극대에서 팔면 된다는 생각을 할 수 있다. (그리디) 

극대 / 극소를 마킹하면서 지나가면 되니까 $O(n)$ 으로 돌려야지 라고 생각하고 있었는데, 사실 저걸 생각하기에 앞서 Coffeetea가 

"너가 코인을 들고 있는데 내일 떨어질걸 알아. 그러면 다 손절하는거 아니냐? 글고 내일 오를거면 전재산을 부어서 사고 내일 다시 팔더라도 내일 생각하면 되잖아" 라는 말을 해서 그냥 그렇게 하루하루 보면서 구현했다. 저 방법이 극대 / 극소 마킹하는거랑 동치인데 (이틀 연속 가격이 오르더라도, 처음 오르기 전날 이미 전재산을 털어 코인을 샀으므로 두번째 날에는 코인을 살 수가 없다. 현금을 가진 날은 극소점에서만 가지고 있게 된다) 구현이 훨씬 짧고 간결하다.

여담으로, 알고리즘이 $O(n)$ 이고 생각하기도 어렵지 않은 문제인데 $n = 15$ 라 몇몇 팀들이 약간의 혼란에 빠져서 (그리디가 안 되는 이유가 있나?) $3^{n}$ 완전탐색을 돌렸다. $n = 1,000,000$ 으로 주지 않은 이유를 사실 잘 모르겠다. 최소한 10만이라도..?

---

L. Two Machines

Solve : Diordhd, Coffeetea, Gratus907

Code : Gratus907

4솔에 막힌 팀 대부분 이 문제가 DP임을 알았던 것 같고, 실제로 상당수의 팀이 낼 때까지 맞는줄 알았는데 채점이 안 되어 디버깅을 못한 것으로 보인다. 놀랍게도 https://www.acmicpc.net/problem/10982 와 $n, a, b$ 제한 외에는 똑같은데, ICPC 문제는 $n$이 작고, 대신에 $a, b$ 가 크다. 

Diordhd가 낸 핵심 아이디어는 다음과 같은 dp테이블을 관리하는 것이다.

$dp[i][j][k]$ 는 

- $i$ 번째 일까지 고려했을 때

- 많이 일하는 기계 $k$ 가 $j$만큼 더 많이 일했을 때의 최적값 (즉 $j$는 두 기계가 일한 시간의 차, $k$는 0 또는 1이다)

이렇게 하면 다음 $i$가 들어올 때 이전 $i$들의 $j, k$ 값을 모두 보면서 관리해도 한 층 ($i$ 하나) 업데이트에 걸리는 시간이 대략 $nm$ 만큼이고 ($m$은 한 일에 걸리는 최대시간) $n = m = 250$이므로 이 $O(n^2m)$ dp는 시간 안에 잘 돌아간다.

 

삐끗하면 음수 인덱스 접근 등 오만 이상한 버그가 날거 같았지만 의외로 내가 뇌절 안하고 한번에 짜서 맞았다.

이때까지만해도 우리가 진출할줄 알았지....

---

D. Canal (WA)

Solve : Diordhd, Coffeetea, Gratus907

Code : Gratus907

문제의 어려운 해석을 모두 지우고, 수학적인 요소로만 문제를 다시 표현하면 다음과 같다.

$\mathbb{Z}^2$ 공간 상에 점들이 $n$개 주어진다. 좌표의 절댓값이 10억 이하.

가로 길이가 $L$ 이고, 세로 길이가 무한대인 판자가 있다. 이걸 세로모양 판자라고 하자.

세로 길이가 $L$ 이고, 가로 길이가 무한대인 판자가 있다. 이걸 가로모양 판자라고 하자.

이때 이 두 판자로 $n$개의 점들을 모두 다 덮기 위해, $L$이 최소 얼마 이상이어야 하는지 찾는 문제.

 

답에 대한 이분 탐색을 해야겠다는 생각은 꽤 일찍 했고, 그다음을 어떻게 할지는 이런저런 생각을 하다가 (사실 나는 $F$가 해볼만하다는 잘못된 생각을 했기 때문에 혼자 $F$를 좀 잡고 있었다. 그런데 사실 내가 여기 있었어도 도움은 전혀 안 되었을 것 같다) 한 번 판정이 $n \log n$ 에 가능하다는 것을 알아냈다.

 

먼저 주어진 점들을 $y$좌표의 순서로 정렬해서 번호를 매기자. 즉, $(x_0, y_0), (x_1, y_1) ...$ 인데 $y_0 \leq y_1 \leq ...y_{n-1}$ 이 되게 한다는 뜻이다. 이때, 이 점들의 배열을 돌면서 다음과 같은 값들을 미리 구한다.

- front_min[i] : 0번부터 i번째까지 봤을 때, $x$좌표의 최솟값

- front_max[i] : 0번부터 i번째까지 봤을 때, $x$좌표의 최댓값

- back_min[i] : $n-1$번부터 $i$번까지 봤을 때 $x$좌표의 최솟값

- back_max[i] : $n-1$번부터 $i$번까지 봤을 때 $x$좌표의 최댓값

 

그런 다음, 정해진 어떤 $L$에 대해 가로판자를 밑에서부터 밀자. $y_0$에 가로판자의 밑변이 오게 놓은 경우, 가로판자들이 밑에서부터 $L$거리 이내에 있는 점들 몇 개를 커버해 준다. 이외의 점들에 대해서, front_max와 back_max를 이용하면 가로 판자가 커버해주지 않는 점들만 볼 때 x좌표의 최댓값과 최솟값이 어떠한지를 알 수 있다. 이 최대와 최소가 다시 $L$ 이내에 들어오면 세로판자를 그 사이에 놓아서 커버할 수 있다.

 

이게 가능한 이유는 가로판자가 커버해주는 점들이 y좌표를 기준으로 볼 때 연속적인 subsegment를 커버해 주기 때문이다.

 

이 처리를 lower_bound 를 이용하면 $n \log n$ 시간이 걸리는데, 답의 최댓값이 20억 ($T$라 하자) 이므로 $n \log n \log T$ 알고리즘이다. (30만 * 로그 30만 * 로그 20억) 은 대략 1.x억 정도로, 시간내에 돌거라는 확신은 없지만 이걸 내면 맞았다고 한다.

 

우리는 이 확신이 없어서 투포인터를 이용해서 $\log n$을 떼야 한다는 생각을 했고, WA를 받은걸 보니 내가 투포인터 구현을 잘못 한것 같다. 투포인터 관련된 코드에 익숙하지 않아서 그런것 같기도...

내가 A번 풀이에 대해서 개소리를 하는 동안 Diordhd가 이것저것 넣어보다가 Segmentation Fault가 나는 걸 확인해서 로컬 오류일 거라는 믿음을 가지고 코드를 조금 읽었더니 이상한게 있길래, 당연히 로컬 오류가 아님을 깨닫고 조금 고쳐서 냈다. 총 5번을 제출했으나 뒤 3번은 사실 같은 코드고, 당연히 그중 어떤것도 채점이 되지 않았기때문에 아무것도 할 수 있는게 없었다.

 

이제와서 생각해보니 내가 잡지 말고 Diordhd한테 넘길걸 그랬다. 

---

그 외 문제들

A : 디닉으로 어떻게 어떻게 되지 않을까 싶었지만 어림도 없지  ㅋㅋㅋ L-R Flow라는걸 알아야 한다고 한다. 지식부족.

J : Convex Hull Trick인걸 식정리를 통해 알았고, (아마도) multiset 같은걸 이용해서 기울기가 단조성 없이 주어질 때 CHT를 적용하는 방법에 대한 문제였다. 끝나고 저녁 먹으면서 들었더니 Li-Chao Tree 라는걸 알면 쉽게 할 수 있다고 한다. 지식부족 2.

---

이래저래 여러 생각을 하게 만드는 대회였던것 같다. 작년에 비해서 팀원 3명 모두 엄청 많이 나아진 실력인 것도 분명히 맞고 (작년에는 트리를 아예 구현할 줄 모르는 팀이었으니...) 나름 팀연습도 열번 이상 하면서 호흡도 잘 맞췄다고 생각했기도 했고. 

ICPC가 서울대에 매우 불리한 규정 (1/2룰, $x$문제 이상 진출 이후 $y$문제 $z$등 방식) 을 적용하는 것도 알고 있었지만, 그래도 지금 폼이면 어떻게어떻게 비벼질 거라는 생각도 좀 했었다. UCPC에서도 기대 이상의 결과를 얻기도 했고...

ICPC가 다른 대회에 비해 다른 점은, 한 대회에 한두문제씩은 고인물 알고리즘을 알아야 풀수있는 문제들이 꼭 나온다. CF Div1도 물론 그렇지만, CF Div1이나 다른 어려운 대회는 주로 그 알고리즘 하나 안다고 해서 풀 수 있는 문제가 나오는건 아닌데 비해 ICPC 인예는 그 알고리즘에 대한 기본 연습 문제 수준의 문제가 나오는 경우가 꽤 있다. 이런 부분들에 대한 공부가 부족했던건 아직 PS를 시작한지 이제 1년 정도 된 우리의 경험 부족 문제이기도 하고. 차라리 이 문제는 훨씬 간단한다. 공부하면 되니까...

그와 별개로 진출 규정에 의해 우리보다 위 실력의 (만약 정말 7솔로 잘린다면) 팀들이 탈락하는 것은 보는 입장에서... 내년엔 나갈수 있을까 싶은 생각이 들어서 좀 묘하다. 만약 컷이 6솔에서 잘리면 우리가 탈락팀중 위에서 1~5등 사이일 거라는 점도 좀 그렇고...

 

그리고 팀원 두명이 소개원실이라는 과목 때문에 자바스크립트에 뇌가 절여져서 (...) 2학기 들어서 PS 코딩을 거의 못 해봤고, 그것 때문에 내가 3시간 내내 컴퓨터를 혼자 잡고 혼자 구현하다시피 했다. 이게 앞 5문제는 괜찮았는데 D번에서 이거때문에 박살난거같아서 좀 아쉽다. 나도 구현력이 좋은 편은 아니라서... 무엇보다 내가 문제지를 거의 안 보고 있었던지라 이번 대회는 나는 굉장히 재미가 없었다. ㅠㅠ

 

(내년엔 내가 소개원실에 절여질 예정이라 Coffeetea나 Diordhd가 코딩해야 한다. ㅅㄱ)

 

내년에도 대회는 많이 있고, 내년부터는 좀 높은 목표를 갖고 개인이든 팀대회든 참가해볼 생각이라서 PS 자체는 계속 나름 열심히 할 것 같다. 지금은 뭔가 많이 바빠진것 같지만...