UCPC 2018 후기

imeimi, Diuven과 함께 unofficial contestant로 참가했다. 팀명은 InDexedTree로 정했었는데 강제로 Challenge-SSHS로 변경당했다. 

결과는 9solve + 52팀 중 7등. (스코어보드엔 반영되지 않았다)

페널티를 신경썼으면 바로 앞의 TCG를 잡을 수도 있었을 것 같고, 또 반대로 바로 뒤의 DeltaMAX 팀이 무리하게 기만만 안했어도 우리가 질 수 있었다는 생각이 든다.

온사이트 대회는 정말 꿀잼이었고 팀 조합도 괜찮아서 대학 가서도 계속 시도해보고픈 팀이었다. 민폐가 되지 않을 수 있다는 전제 하에 말이지 ㅁㄴㅇㄹ

전략도 괜찮았고, 팀 전체적으로 봤을 때는 성공한 운영이었지만 개인 Contestant로는 조금 아쉬운 마음이 남아서 후기를 작성하기로 했다. 의식이 흐르는 대로 적되 중요포인트는 나중에 알아볼 수 있도록.

[Solved]

TAMREF : H, K

Diuven : A, J, L

imeimi : C, E, G, I

전략, 팀노트

대회용 컴으로는 그램(imeimi)과 서피스(TAMREF)를 거르고 남은 Diuven의 컴퓨터를 선택했다.

또 3명이서 컴퓨터 1대를 쓰는 게 익숙하지 않을 것 같아서 2.5 Solver + 1 Coder (Diuven) 전략을 쓰기로 했다. 결국에는 설명하기 어려워서 자기 문제를 다 자기가 코딩했지만...

IDE는 VSCode로 했고, Diuven이 세팅도 깔끔하게 하고 조작법도 명료하게 전달해줘서 코딩에 큰 어려움은 없었다.

팀노트를 인쇄물로 만들 필요가 없었던 대회 규정 덕에 대부분의 구현 template을 cpp 파일로 만들어갔다. 

더불어민규당과 MolaMola팀의 팀노트를 참고해서 NTT / Polynomial Dividing을 만들어갔고,

imeimi가 구현한 다음의 알고리즘들을 넣어갔다.

- Manacher's algorithm, Aho-Corasick, Suffix Array

- Splay tree, Link - Cut Tree

- FFT (complex)

물론 본선 문제를 보면 알겠지만, 이 알고리즘들을 쓰는 일은 없었다. ㅂㄷㅂㄷ

구현이 까다로운 자료구조나 알고리즘이 대부분 imeimi에게 편중되는 문제가 있었다. 그렇다고 내가 당장 저것들을 익혀서 실전에서 써먹을 실력은 안되니 어쩔 수 없지... 모르면 이멘에게 패스

연습

전날밤에 Tsukuba Regional 2017을 돌려고 했는데 팀원 둘의 스케줄 문제 때문에 잘 되지 않았다. imeimi는 지쳐서 자러 갔고, Diuven과 둘이서 문제를 풀다가 나도 컨디션이 급격히 떨어져서 구현 2개 + 탐레프 맞왜틀 1개 (낙인) 로 끝나버렸다.

연습을 돌 때 노트도 제대로 쓰지 않았던 게 문제라고 생각하고 있다.

초반

빠른 두뇌 회전을 위해 세븐일레븐에서 병 데자와 2개를 사서 들어갔다. (도합 카페인 230mg)

대회가 40분이나 늦어져서 기다리기 되게 지루했다... imeimi가 엎어져 자려고 하길래 컨디션이 좋지 않은가 걱정했지만, 뭐 기우였다.

단순히 자리 배치대로 태스크를 나눴다. 내가 ABCD, 듀벤이 EFGH, 이멘이 IJKL.

문제 별로 첫인상을 적어보자면

A : 

변명하자면 진짜 T가 10^9로 보였다. 그래서 ??????하면서 바로 넘겼다.

B :

????????????????????

이게 뭐지 싶었다. yclock은 풀겠지 싶은 그런 기하 문제... 셋 중에 기하 전문가가 없고 나도 기하 문제를 풀어본 기억이 가물가물해서 또 넘겼다.

C : 

??????????????

이때부터 숨쉬기가 힘들어지기 시작했다. ABC를 봤는데 하나도 쉬운 문제가 없다고? 심지어 디스크립션도 길어서 읽을 용기가 없었던 것 같다.

D : 

빅데이터 로봇 짤 때문에 생각이 잠시 멈췄다.

이 중에 가장 만만해 보인 A로 돌아가기로 결정하고, "BCD 개어렵다"라고 팀원에게 이야기했다.

다시 A로 돌아왔는데도 정풀이 보이지 않았다. 아마 겁을 먹어버린 것 같았다.

관련된 백트래킹 문제만 생각나고 적당한 동적계획법도 잡힐 생각이 없었다. 소위 말하는 '말리는' 현상이 대회 극초반부터 찾아온 것이다.

ABCD를 통째로 imeimi에게 넘겼다. 아마 이때쯤 imeimi가 J를 Diuven에게 넘겨서 코딩을 시작했던 것 같다.

Diuven은 J를 순조롭게 맞았고 imeimi가 A 풀이를 쉽게 찾아내서 Diuven과 내게 전달했다. 나머지 생각과 구현은 Diuven이 성공적으로 해줬다. 혼자 잡았다면 더 말렸을 것 같아서 다행이라는 생각이 들었지만... 개인적으로는 못내 아쉽다.

imeimi가 K번이 이상하다는 이야기를 했었나? K번 종이를 내가 봤었나? 기억나지 않지만 K번의 수식이 well-known 수올문제 꼴과 같았다. 안타깝게도 그 문제가 2년 전에 봤던 거여서 그렇지. 그래도 일단은 가능성이 있어 보이는 K번을 잡았다.

기억을 더듬어서 풀이를 생각해내려 했지만 비슷한 기억조차도 나지 않았다. 떠오른 건 '귀납법'이라는 막연한 힌트. 그래서 "이거 놓으면 0솔브다"라는 심정으로 어떻게든 m을 줄이려고 수식을 이리저리 가지고 놀았고, 아이디어님이 결국 강림하셔서 Diuven이 A를 맞을 때쯤 풀이를 정리할 수 있었다.

그런데 설명을 하자니 디테일 전달이 잘 안 될 것 같아서 바로 코딩을 잡았다. 다행히 예제 출력과 내 코드 답이 정확히(!) 같아서 확신을 가지고 제출했고 원큐에 AC가 나왔다. 대회 끝나고 나서 예전에 블로그에 정리한 풀이랑 비교해 보니까 발상이 약간은 다르더라. 잘 생각해냈다 싶었다.

노트북이 Diuven과 나를 거쳐가는 사이에 imeimi가 E 풀이를 떠올려서 무난하게 AC를 냈다. 여기까지가 4솔브 1시간. 2등 그룹에 속해있을 정도로 빠른 속도였다.

중반

FGH를 봤는데, 어째서인지 G는 못 풀 것 같아서 (G나 A나 보자마자 떠오른 게 Manhattan MST였다) 건성으로 읽고, 하필이면 F랑 H 중에 F를 잡았다.................. 이것도 H 문제를 잘못 읽다보니 H가 개어려운 문제가 된 탓.

F 동적계획법 식을 떠올려보다가 안된다는 걸 깨닫고 다시 D를 읽었다. 이 사이에는 머신이 놀면 안된다는 생각에 Diuven이 구현 문제 L을 맡고 있었고, imeimi가 본 적이 있다는 문제인 C를 잡고 있었다.

D와 H의 디스크립션을 모두 잘못 읽었다는 사실을 깨닫고 큰 충격에 빠졌다.

D에서는 인접한을 빼먹었고, H에서는 인접한을 넣어서 읽었다. 이미 이 시점에서 영영 D를 풀 수 없게 되어버렸다. 정풀이 매칭이라서 풀 수 있었을 것 같지도 않지만, 발상 자체가 이 시점에서 비뚤어진 것이다.

마음을 다잡고 다시 H를 읽었는데 증명이 잘 되지 않았고 짐작가는 값조차 모호했다. 그 와중에 Diuven이 L을 2번 틀렸고, 코드를 프린트해서 버그를 하나 잡았다. 그 사이에 노트북은 C의 imeimi에게.

2시간째는 노솔브로 지나갔다. 그 사이에 다른 팀의(특히 더민규;;) 풍선 개수가 착실히 쌓여갔다.

imeimi의 코드가 로컬에서 세그폴트가 떴고, 프린트할까 고민하는 imeimi에게 그냥 VS 디버깅을 하자고 했다. 이 판단은 개인적으로 좋았다고 생각한다.

L의 버그를 (대충이나마) 잡은 Diuven과 H를 논의했다. 이 시점에서 처음으로 '논의'를 했다!

'최솟값'을 주장하던 Diuven과 'gcd'를 주장하던 나 사이의 의견이 좁혀지지 않았다. (사실 둘 다 풀이에 쓰더라;;)

Diuven이 역시 아이디어맨 답게 유의미한 관찰을 해줬지만, 이 시점까지 더 이상의 관찰이 나오지는 않았다. 다만 케이스를 조금 체계적으론 나눴다면 나눈 것이 수확.

그 사이에 imeimi의 C 코드가 30%에서 돌연사했고 노트북을 Diuven에게 넘겼다. 버그를 찾는 사이에 imeimi와 B를 논의하고, H의 나머지 케이스를 처리하려고 전전긍긍해봤지만 잘 되지 않았다.

Diuven이 L 출력 초과를 내고, 버그를 잡은 imeimi가 C를 맞고, 다시 Diuven이 L을 맞았다. 디버깅이 어떻게 저렇게 안정적으로 되는지 모르겠다...

후반

보통 초반이 기억이 잘 안 나는게 정상 아닌가? 오히려 후반의 내용이 잘 기억나지 않는다.

G를 imeimi와 논의했지만 내 발상이 좋지 않았다. imeimi가 결국 O(NMD)짜리 위험한 솔루션을 제시했고, 내가 약간의 디테일을 추가한 시점에서 시간 제한을 봤다. 2초! 바로 코딩에 들어갔다.

G에서 imeimi가 고전하는 사이 Diuven과 다시 H를 논의했다. 둘 다 discussion 내용을 기억하고 있어서 진행이 빨랐고, 유클리드 호제법을 떠올린 Diuven의 아이디어를 내가 받아서 "양수와 음수가 동시에 있는 케이스에 답은 0이다!" 라는 결론을 엄밀한 증명 없이 내리는 데 성공했다.

2번의 WA를 거쳐 imeimi가 G를 풀었다. God coder imeimi... 7솔브로 3시간이 지났다.

이 때부터는 대부분의 문제들이 생각을 요하는 것이어서 머신이 쉬었다.

imeimi와 H를 논의해봤지만 모든 수가 양수일 때의 케이스를 도저히 증명할 수 없었다. 하지만 이 때 정답에 대한 강한 추측이 이미 완성되어 있었고, 안 되면 죽자 하는 식으로 짜서 냈는데 맞았고 그게 정해였다. 8솔브 개꿀ㅋㅋㅋㅋ 후반의 승부수였다고 생각한다.

H를 푼 뒤에는 I가 가장 만만하다고 생각했고, 모두가 flow라고 직감한 D와 F를 합의 하에 과감히 버렸다.

I를 차근차근 해부하고 Diuven과 imeimi의 관찰을 조금씩 더해 dynamic connectivity라는 결론이 나왔고, 우리 중에 유일하게 이를 구현할 수 있는 imeimi에게 노트북이 넘어갔다. 이걸 또 원큐에 맞추는 imeimi... 9솔브.

imeimi가 코딩하는 사이에 Diuven과 B를 논의했다. 문제 없이 풀린다고 생각했는데 복잡도가 QNlogN이 나왔다. 아무리 시간 제한이 5초라지만 20000 * 5000 * log (???) 는 불가능했다. 더구나 기하인데.

열심히 pivot을 돌리면 QN이 나오겠구나! 하는 직감만 했을 뿐, 실제로 그런 문제를 풀어본 지가 너무 오래되어 생각을 더 발전시키지 못했다. 내가 B코딩을 잡았지만 QNlogN 구현이 한 번 터진 뒤 solving을 그대로 종료. 4시간보다 시간이 조금 더 지났을 때였다. 그 뒤로는 서로 C, K, G 풀이를 교환하고 자리를 정리했다.

총평 - 팀

나는 작성한 코드 길이가 1500B가 안되니까 논외로 하고, 나머지 둘은 페널티를 신경쓰지 않고 과감히 코딩했다. 오히려 이게 성공적이었는데, 기본적으로 코딩 실수를 거의 하지 않는 둘이다 보니 컴퓨터 회전이 빨라지고 낭비하는 시간이 적었던 것 같다.

순간 순간에 태스크의 우선 순위를 정하는 방식도 합리적이었고, 의견 교환도 원활하게 이루어졌다고 생각한다. 애초에 명료하게 말을 잘 하는 팀원들이니까.

다만 기하 전문가가 없었던 점, H 증명에 너무 시간을 오래 쏟은 점은 옵저버 고삐리팀이라면 몰라도 정식 팀이라면 보완이 필요한 부분일 것이다. 또 빡센 문제가 있다 하면 imeimi에게 넘어간 점, Diuven을 구현 문제 이외에 크게 활용하지 못한 점도 아쉽고 아마 Diuven 본인이 가장 안타까울 것이다.

총평 - 개인

잘한 점이 없는 건 아니다.

K 캐치부터 관찰, 코딩까지 큰 실수 없이 해낸 점은 좋았고, H에서 몇 가지 유의미한 관찰을 해낸 것과 깔끔한 코딩, 과감한 찍기는 분명 좋은 선택이었다. E, G에서도 imeimi가 관찰해낸 사실을 나름대로 잘 검토했다.

근데 문제점이 더 많아서 문제지.

1) 난독

A를 초견에 못 푼 건 실력도 있지만 난독의 몫이 더 컸다고 생각한다.

D, H를 잘못 읽은 건 치명적이다. 이 때문에 중반부에서 사실상 1시간 가까운 시간 동안 내 역할은 없었다.

2) 아무 아이디어 대잔치

G에서 상상의 나래를 너무 넓게 펼쳐서 PST까지 다녀와버렸다.(...) imeimi의 관찰에 방해가 될 수도 있었던 부분.

항상 "뭘로 풀지"보다 "어떻게 풀지"를 생각하도록 하자.

H에서도 관찰을 너무 마구잡이식으로 해서 푸는 데 시간이 걸렸다. Diuven의 관찰 전까지 풀이는 0이었다고 봐도 될 정도.

I에서도 마찬가지. 엥 이거 다이나믹 2sat 아니냐~~~ 이러고 있었는데 진짜 그 아이디어에 obsessed되어버렸다. 하위호환격 문제를 1년 전쯤 풀어본 적이 있는데도 떠올리지 못한 걸 보면 감을 잃긴 한 모양이다.

230mg 카페인을 먹어도 졸린 건 처음이다.

기하 열심히 해야지.

재밌었다. 자야지.