ICPC Seoul Regional 온라인 예선 후기

최종 456팀 중 43위 했다.

 

1. 팀 결성

사실 여기부터 이야기를 시작해야 할 것 같다. 나는 ICPC 신청 마감 약 2주 전까지 팀원을 구하지 못했고, 친구들에게 '교내대회 상금 30만원씩 떼 줄 테니 같이 나가지 않을래?'라고 부탁해야 하는 상황이었다. (우리 학교는 ICPC 온라인 예선을 '가을 프로그래밍 대회'라는 이름으로 총 500만 원에 달하는 상금을 장학금 형식으로 주었다.)

 

그런데 마침 최근에 들어간 jwpassion1님의 카카오톡 오픈채팅방 '경희대학교 PS 모임'에서, ICPC 팀원 구하는 채팅을 허용한다고 하셨다.

 

그래서 바로 카톡을 올려봤지만 그 누구도 봐주지 않았다...

무시당했다

 

그 이후 약 3일 뒤에, 갑자기 5분만에 팀이 결성됐다.

?

 

진짜다. 생각보다 너무 빠르게 팀이 결성돼서 놀랐다.

 

이 이후 처음으로 만났을 때, 팀연습 이전에 먼저 팀 등록부터 하기로 했다. 팀명은 아무도 의견을 내지 않아서 그냥 내가 '뉴비같은 거 어때요?' 했고, 그게 그냥 팀명이 됐다...?

 

이렇게 오합지졸 nEwBiE팀이 완성됐다.

 

뉴비팀 완성!

나는 당시 Diamond V였고, train0113님이 Diamond IV, gdw1301님이 Platinum IV였다. 갑작스럽게 구성된 팀 치고는 생각보다 티어가 높아서, 해볼 만 하겠다는 생각이 들었다.

 

이미 우리는 경희대학교에 3오렌지 (당시 1루비 2다이아, 현재 3루비) 팀이 결성되었다는 소식을 들었기에, 목표는 교내 2등이었다.

사실 교내 2등도 성공했다. 야호 :blobcheer:

이때부터 팀 합 맞추려고 팀연습을 빡세게 했던 것 같다.

 

2. 팀 연습

우리 팀은 팀연습을 좀 많이 빡세게 했다. 일주일에 4번 정도 만났고, 다음과 같은 셋들로 팀연습을 했다.

물론 시험기간에는 못 만났다... 왜 시험기간과 ICPC가 겹치는 걸까?

 

• 실버~플래티넘 랜덤 10문제
• 저저번 ICPC 예선 셋
• 백준 유저 대회들 (추후 후기글 따로 작성할 예정)
• 코드포스 Div.3 버추얼

 

팀 연습을 하다 보니, 우리 팀의 기복이 좀 심하다는 생각이 들었다. 어떤 셋에서는 플레급 문제도 풀면서, 어떤 셋에서는 실버급 문제도 놓치고... 이걸 어떻게든 극복하는 걸 핵심으로 잡았다.

 

이중 KAIST Mock Open Contest가 나는 제일 아쉬웠다. 내가 풀 수 있을 만한 문제 냅두고 기하 많은조건분기를 세시간동안 구현하느라 팀원들 구현시간도 날리고 결국 만이천바이트 구현해놓고 맞지도 못했다. 내 팀연습 통틀어서 가장 큰 실수였다고 할 수 있겠다. 하지만 이건 ICPC에서도 되풀이됐다...

 

사실 팀연습은 길게 적으려면 많이 길게 적을 수 있는데, 결국 본대회 이야기가 제일 중요할 것 같아 본대회로 넘어가겠다.

 

3. 본대회

1. 예비소집

대회 전날 예비소집이 있었다. 스코어보드 사진은 유실된 것 같다. 찾을 수가 없다.

 

A가 채점환경 연습하라고 준 DOMJudge 테스트사이트에서 본 문제와 유사해보이는 인터랙티브 문제길래 잡았는데, 실수로 인해서 3번이나 틀리고 겨우 맞았고, 이때가 8분이었는데 이미 6분에 퍼스트 솔브가 나와 있었다. 처음에 제출한 게 맞았으면 5분에 맞고 퍼스트 솔브 가져가는 것이었다는 사실에 아쉬웠다.

 

BCD는 작년 예선에 출제된 문제들을 그대로 줬다. 문제는 B는 브론즈 C는 골드 D는 다이아였다는 것이다. (확실하진 않지만 아마도 그랬던 것 같다.) 그래서 BC만 풀고 D는 건드리지도 않았다. 근데 스코어보드 나중에 보니 풀려있더라. 알고 봤더니 푼 팀이 ohwphil님 팀 등이 있었는데, 이미 푼 문제라 BOJ에서 코드를 복붙했다고 한다. 본대회도 아니고 예비소집이니 아무래도 상관없을 것 같다는게 이유였다고 한다. 사실 내가 생각해도 상관없을 것 같긴 하다.

 

예비소집은 그렇게 길지 않았기에 그렇게 끝났다.

 

2. 본대회 준비

나는 대회 시작 30분쯤 전에 대회실에 입실했다. 우리 팀뿐만 아니라 그 어떤 팀도 대회실에 없었다. 심지어 감독관도 없어서 내가 너무 일찍 왔나 싶었는데 30분 전이면 또 그렇게 일찍은 아니었고... 아무튼 그랬다.

 

대회 시작 15분쯤 전에 train0113님이 왔고, 10분쯤 전에 gdw1301님이 왔다. 근데 train0113님이 말하시기를 내가 팀노트를 잘못 출력해왔다고 하셔서 (단면으로 출력해야 하는데 양면으로 출력했다고) 그때 바로 gdw1301님이 학생회실에 출력하러 가셨다. 결국 팀노트 일부는 다시 출력하지 못하고 돌아오셨고, 결국 우리는 팀노트 일부가 없는 상태로 대회를 치렀다...

 

이후 대회가 시작됐다.

 

3. 본대회

문제셋

 

train0113님이 알려주신 팁 중에, 한국어 설명이 포함된 문제들이 그렇지 않은 문제들에 비해 난이도가 상대적으로 낮다는 팁이 있었다. 그래서 바로 11문제를 다 열고 아래로 스크롤해서 한국어 설명이 있는 문제들을 판별했다.

 

한국어 설명이 있는 문제들은 E, F, H였고, K는 한국어도 없는데 스크롤이 끝없이 내려가는 거 보고 바로 걸렀다. 내가 F를 읽었고, 그동안 gdw님이 E, train님이 H를 읽었다. (E F H 순서대로 삼분할 해 열어 놓았었고, 내가 가운데, gdw님이 왼쪽, train님이 오른쪽에 앉아있었기에 자연스럽게 그렇게 됐다.) F가 좀 토나오게 생긴 기하여서 gdw님이랑 문제 교환하고 내가 E를 봤다.

 

E (8')

E를 풀었다. 그냥 2차원에서 a_ij, b_ij 차의 절댓값에 대해서 각 행 중 최댓값 구해놓고 쿼리에 따라 최댓값 취하면 되는 문제였다. 설명이 복잡해보이는데 그냥 하면 된다.

 

노솔브 방지문제가 얘 같았는데 난이도가 생각보다 높아서 당황했다. 그래도 실버 중위는 될 것 같은 느낌.

 

H (-1)

내가 E 구현하는 동안 F, H 풀이가 안 나왔다. 여기에서부터 이미 대회 망했다고 생각했다. 보통 ICPC 예선은 '5솔플마단'이라는 말이 있을 정도로 한국어 문제는 빠르게 풀고 이후 2-3문제가 본선 진출을 가르는데, 한국어 문제가 쉬운 게 E 말고 없었다는 말이었기 때문이었다.

 

일단 F는 읽기 싫어서 H를 읽었고, train님이 값들을 적절히 정해주면 8중포문으로 될 것 같다는 의견을 내셨다. 이후 같이 토의한 결과 더 적절히 정해주면 6중포문으로 충분하다는 결론이 나왔다.

 

제한시간이 0.1초인데 돔저지 파이썬 기본이 파이파이고 파이파이는 기본시간이 0.1초 정도 된다는 심각한 문제가 있었기에, 파이썬을 사용하는 나나 gdw님은 구현하지 못했고 (물론 둘다 C++을 아주 모르는 것은 아니라 시간만 충분히 주면 구현할 수 있었겠지만 train님이 C++ 메인이시기에) train님께 맡겼다.

 

이후 train님이 구현 끝났다면서 제출하셨는데, 틀렸다.

 

H (47', +1)

train님이 H 디버깅을 시작하셨고, 나는 그 동안 F 풀이와 D 풀이를 낸 뒤 A를 읽다가 문제 이해도 잘 안 돼서 그냥 H 디버깅을 도왔고, 조건을 하나 검사하지 않았음을 발견했다. 내가 고쳤고, 바로 맞았다.

 

F (64')

생각해 둔 풀이대로 F를 구현했다.

풀이는 다음과 같다: 원을 두 반평면으로 분할했을 때, 두 자원의 위치가 분할된 횟수의 홀짝성에 따라 수락할지 여부가 결정된다. 이 반평면 분할은 CCW로 충분하다.

 

마침 '팀노트의 잘리지 않은 부분'에 CCW가 있었기에 그걸 그대로 작성하고 예제를 돌려보려 하는데... 문제가 생겼다. 바로 문제에서의 모든 좌표가 극좌표계로 주어지는데 내 CCW 코드는 xy좌표계에서만 동작한다는 사실이었다. 그래서 극좌표계 -> xy좌표계로 변화시키는 코드를 작성할 수 있냐고 두 분에게 여쭤보았는데 (나도 못 하는 건 아니지만, 실수가 생기면 디버깅하는 데 한참 오래 걸릴 것 같았다. 기하 싫어) gdw님이 가능하다고 하셔서 gdw님한테 잠시 컴퓨터를 드리고 C를 읽었다.

 

다행히 구현 금방 끝나서 돌려 봤는데 예제가 맞았고, 제출했더니 AC를 받았다.

 

D (131', +2)

이때쯤 스코어보드에 많이 풀린 문제는 (E, F, H를 제외하면) C, G였다. 나는 내 풀이에 확신이 있었기에 D를 잡았다.

 

먼저 격자를 홀수 격자와 짝수 격자로 분할한다. (홀수 격자와 짝수 격자라고 말은 했지만, 다음과 같이 분할한다는 말이다.)

 

1끼리/2끼리로 2-SAT 분할한다.

이렇게 분할된 격자를 45도 돌리면 놀랍게도 그리디로 쉽게 풀림이 잘 알려져 있는 불 끄기 문제를 두 번 한 뒤 그 최소값을 더하는 문제로 환원된다.

 

문제는 풀이에 비해 구현이 굉장히 더러웠다는 것이다. 한 시간 동안 키보드 타자만 쳤을 정도로. 다행히도 이번에는 Mock 때와 다르게 구현이 빠르게 끝났고, 내 보았는데...

 

틀렸다.

 

틀린 이유는 단순히 오타 때문이었다. 문제는 오타 때문에 틀린 게 두 번이었다는 것이다. 정말 정말 다행히도 그 이후에는 TLE나 RE가 나지 않고 맞았다.

 

G ()

내가 한 시간 동안 잡고 있던 D를 겨우 맞은 뒤로, 두 분이 같이 잡고 있던 G를 구현하시기 시작했다. 나는 읽어봐도 모르겠어서 C를 잡았다. 문제는 내가 알고 있는 문자열 알고리즘은 KMP밖에 없는데, KMP를 쓰면 abc abcabcabcd 와 같은 입력에서 반례가 생긴다는 점이었다.

 

이때쯤에 많이 풀린 문제는 CDEFGH였는데, DEFH는 이미 맞았으니 남은 문제는 CG밖에 없었다. C는 내가 못 풀 것 같아서 팀원들과 같이 G를 잡았다.

 

근데 구현의 핵심적인 아이디어가 부족한 상태로 구현하다 보니 결국 어떤 한 지점에서 막혔고, 대회 끝까지 이 지점에서 벗어나지 못했다. 결국 4솔 36등, 교내 2등으로 마무리되었다.

4. 대회 이후

WayInWilderness팀(교내 1위 팀)의 jwpassion1님께 G 풀이를 여쭤 봤더니 SCC/BCC가 튀어나왔다. 문제는 내가 둘 다 몰랐다는 것이고, '아, 그래서 내가 못 풀었구나' 싶었다. 딱히 아쉽지는 않았다.

 

이후 WayInWilderness 팀과 segCanDoAnythin팀과 함께 같이 밥을 먹으러 갔다. 대회 뒤풀이 느낌으로 먹으러 갔기에 몇 가지 대회 관련 얘기가 나왔다.

 

그보다도 한참 이후, C번 정해에 오류가 있었다는 발표가 나왔고, 잘못된 데이터를 삭제한 후 재채점을 한 결과 우리 팀은 43등으로 밀려났다. (WayInWilderness 팀은 C를 오히려 맞아서 12등으로 올라갔다.) 또한 이때 본선 진출팀 발표가 났는데, 우리 팀이 포함되어 있었다.

 

아무튼 본선에는 진출했고, 본선을 준비해야 하는 상황이 되었다. 제발 본선에서도 딱 이만큼만 성과를 거뒀으면 좋겠다는 마음이 있다.