2019 UCPC 인터넷 예선 후기 (스포 O)

UCPC 2019 인터넷 예선에 Little Piplup 팀으로 참가했다. 작년이야 코딩 자체를 시작한 지 4달? 만에 나간 대회니까, 조금 제대로 뭔가 '아 대회 나가야지' 라고 생각하고 나간건 처음인 것 같다.

나름 UCPC를 위해 레이팅에 비해 팀으로 연습 하면서 열심히 했다고 생각했는데, 결과는 솔직히 좀 아쉬운 것 같다. 대략 45~50등 사이에 들거 같은데, 백준 서버가 터지고 종료 8시간 후에도 최종 스코어보드가 공개되지 않고 있으므로 (...) 조금 더 생각나는 것들을 내일(내일은 서버가 복구된다는 가정 하에) 써보려고 한다.

 

평소 코포 라운드 / 팀연습과는 달리, 문제 풀이 자체보다는 대회 중 내가 생각했던 것들? 을 whining 할 생각이기 때문에, 풀이가 궁금하다면 이 글보다는

 

문제 : https://drive.google.com/file/d/1WAci8u_VY8FKeiwbsKN4CVOVg1W4fQxH/view

풀이 : https://drive.google.com/file/d/1lEkJ4sW5s2bD8SXHh2nYVp8MgXf2nkNg/view

 

공식 문제 / 풀이 링크가 있다.

---

시작 전

일단 기본 전략은 내가 A D G (있다면 J) 를 읽고, Coffeetea가 B E H (있다면 K) 를, DHdroid가 C F I (있다면 L) 을 읽으면서 쉬운 문제를 먼저 체크하고, 바로 코딩할 수 있는 문제는 그자리에서 잡고 넘어간다는 생각으로 했다. 

---

A. 수학은 체육과목입니다 2

Solve : Gratus907

Code : Gratus907

1부터 시작해서 다시 9로 돌아온다는 것을 잘 관찰하고, 그냥 %8 값에 따라 출력해주면 된다.

내가 먼저 보고 먼저 잡고 넘어갔다. 

---

B. 우유가 넘어지면?

Solve : Coffeetea

Code : Coffeetea

시키는 대로 문자 하나씩 바꿔서 잘 출력하면 된다. 사실 문제도 안 읽어봤는데, 아마 뭐 배열 두개로 적당히 잘 짰겠지.

---

이 시점에서 C는 상당히 어려운 것 같다는 생각이 들었고, 나는 D가 문자열이고 뭔가 부분 문자열 관련 문제인걸 보고 빠르게 '이거 버리자' 라고 말하고 G로 넘어갔다. 그리고 G는 끝없이 케이스를 나누는 + 수능 수학 실력을 요구하는 문제였기 때문에, 일단 J도 읽어보기로 했다.

Coffeetea는 E랑 H가 매우 어려운 것 같다 라고 평가했고, DHDroid는 우리가 A랑 B를 미는걸 보고 나서 "어 C는 왤케 어렵냐" 라고 말하며 F I 로 넘어갔는데 이것도 바로 코딩할 문제는 아니라고 생각했다.

 

사실 이때 했어야 할 올바른 전략은 뭘 풀지를 빠르게 정하고, 집중을 조금 했었어야 하는데, 이때 상위권 스코어보드가 실시간으로 제출-AC-제출-AC하며 6문제 정도를 한 20분에 순식간에 밀어버리는걸 봐버렸고, 굉장히 멘탈이 안좋아지기 시작했었다. 처음 진지하게 (어떤 목표를 가지고) 뛰어보는 CP 대회여서인지, 그냥 원래 내가 유리멘탈인건지 아무튼 상위권 솔브를 보고 D, F, I, J 가 비슷한 난이도이며 뭘 먼저 잡을 지 몰라서 일단 다 읽어본다는 이상한 생각을 했고, 3명이 다같이 뇌절을 시작했다.

 

그래도 일단 J가 뭔가 Reasonable 하다는 생각이 들었고, 나는 J를 풀어보려고 했다. 다행히 한 20분 정도 생각해서 솔루션을 찾고, 바로 (구현이 쉬웠기 때문에) 코딩을 시작해서 금방 AC를 받았다. 이게 한 00:45 정도.

---

J. 이사

Solve : Gratus907

Code : Gratus907

정해에 Voronoi Diagram & Furthest Voronoi Diagram 이라는 이상한게 있던데, 당연히 저런 생각은 못했고 (영역을 $n^2$ 개로 나눌 수 있는건 알았는데, 한 쿼리를 $\log n$ 에 처리할 수 있을 거라는 생각도 못했다.)

기하적으로 잘 생각해 보면 삼각 부등식과 등등을 활용해서, 반드시 답의 후보가 주어진 $n$ 개 점이라는 사실을 알 수 있다. 예제가 그렇지 않아서 약간 당황했지만, 계산해보니 맞는 것 같길래 일단 믿고 내기로 했다. 

라운드 중에는 완전히 증명을 하지는 못했고, 대략적인 감만 가지고 풀었는데 코딩을 하면서 생각해보니 귀류법으로 증명이 되는 것 같았다. (그리고 풀이 슬라이드에 있는 내용도 내가 생각했던 것과 같다) 

아마 빠르게 J를 푼 팀이 많은 것으로 볼 때 대부분이 이렇게 푼 것 아닐까 싶다.

---

이때 팀원들이 F번을 풀고 있었는데, 나도 대략 풀이 구상에 참여를 했지만 팀원들이 $6 \times 6 \times 6 \times n$ dp 테이블에 대해 얘기하고 있는 걸 보고 그냥 팀원들을 믿기로 했다. I번을 고민하러 갔지만 사실 나는 별로 좋은 생각이 나지 않았고, 개인적으로는 이때부터 그냥 끌려다니기 시작했다. 

---

F. 공교육 도박

Solve : Coffeetea, DHdroid

Code : DHdroid

위에서 써 놓은 대로, $6 \times 6 \times 6 \times n$ 테이블을 채우면서 접근하면 된다. 지금 이 순간까지의 주사위들을 버리고 다음 주사위를 던지는게 맞는지 아닌지를 6번의 체크로 확인할 수 있고, 이 행동을 $n$번 (최대 1000) 반복함으로써 기댓값을 다 구할 수 있으므로, 충분히 빠르게 dp로 구할 수 있다. 

 

이때 DHdroid의 머신에서 왜인지 모르겠지만 틀릴 이유가 없는 코드가 안 돌아갔다. 더 이상한건 똑같은 코드를 내 머신으로 옮겨서 돌려 보니 잘 된다는 것인데, 뭔가 windows 환경에서의 MSVC 컴파일러가 이상한 행동을 하나? 전혀 모르겠지만, 아무튼 내 머신에는 GCC 컴파일러가 깔려 있고 나는 나름대로 UB나 등등을 대비해서 대회랑 동일한 옵션을 맞춰놓고 있으므로 맞을거라고 믿고 냈는데 맞았다. 사실 구현 자체는 그렇게 막 어렵진 않았지만.

---

I. 육각형 우리 속의 개미

Solve : Coffeetea, DHdroid, Gratus907 (내가 기여한 바가 사실 거의 없다.)

Code : Coffeetea

6각형에서 사이클을 $n$ 개의 간선을 이용해 만들 수 있는 경우의 수를 세는? 약간 그런 느낌의 문제인데, 나는 계속 어떤 수학적인 formula가 나타날 거라고 믿고 6개, 7개, 8개 경우를 손으로 해보고 있었고 (그러고 나서 무슨 점화식을 세우거나 뭔가 생각을 해볼 수 있을 거라고 믿었다) 거기 빠져서 혼란스러워 하는 동안 Coffeetea가 육각형에서의 방향을 3차원에서의 $x, y, z$ 방향으로 보면 그래프 탐색처럼 풀 수 있고, 경우의 수를 BFS나 DFS로 잘 셀 수 있다고 말했는데 이게 매우 맞는 말인거 같아서 Coffeetea가 코딩하러 갔다.

---

D번은 Trie를 이용해서 풀 수 있는 문제였고, 사실 Trie가 잘 동작하면 그다음 뭘 해야 하는지도 거의 완전히 생각을 해놓고 있었다. Coffeetea랑 DHdroid가 틈틈이 풀어서 대충 다 유사코드화 해 놓기도 했고, 나도 들어보고 풀이가 맞는 것 같다고 납득할 만 했기도 했고, 시간이 약간 걱정이었지만 내생각에는 충분히 잘 돌 거 같아서, 이 시점 (01:30 쯤) DHdroid가 D번을 구현하러 가고 나는 다른 문제로 뭘 봐야 할지 생각하고 있었다. 아마 차라리 C번을 봤으면 나았을 텐데, 일단 스코어보드상 G를 봐야 한다는 생각이 들어서 G를 보기 시작했다.

---

결과적으로, D는 Trie에 개수세는거 구현을 못해서 (포인터 연산 같은거에 익숙하지 않다보니, 그런걸 태생적으로 많이 쓰는 구현에 너무 심각하게 약하다) D는 끝까지 AC를 못 받았고, G는 제출하려고 보니 서버가 터져서 제출을 못하고 끝났다. 이걸 Coffeetea는 진짜 아쉬워하던데, 솔직히 말해서 나는 G를 아무리 많은 시간이 주어져도 절대로 AC를 받을 자신이 없다. 아마 마지막에 제출하려던 코드도 거의 기대하지 않았기 때문에...

 

G는 대충 지수함수, 분수함수, 일차함수를 경우의 수를 나눠서 7가지를 잘 세는 그런 문제로, 사실 꼼꼼하게만 코딩하면 풀 수 있는 문제였다. 그런데 시간이 별로 없으니까 원래 그런거 잘 못하는 성격이 더 심각해져서인지, 계속 이상한 경우를 못 보면서 틀렸고 결국 그렇게 타임아웃.

---

본선 진출 여부

아마 안 될거 같은데(...) 나는 6솔에서 커트가 될거라는 생각이 들었는데, Slack에 보니 몇몇 분들이 5솔 상위권까지 끊길거라고 생각하는 듯 했다. 그런데 아마 기존 5솔 팀들이 대부분 프리즈 이후 6솔로 올라갔을 것 같은 정황을 생각해보면, 5솔에서 페널티가 130분 대 이하인 팀들이 많지는 않을 것도 같..긴 한데... :thinking_face_rotating:

기대는 솔직히 전혀 없고, 솔직히 그냥 1.5시간동안 트라이 구현을 못한게 너무 기분 나빴다. 왜 그런거 구현 해볼 생각을 안했을까...;;

 

대회 끝나고 직후에는 PS를 별로 하고싶지가 않았는데, 그래도 뭐 대회때문에 하는거라기보다는 지금은 재밌어서 공부하는거니까... ㅋㅋㅋㅋ

 

UPD : 43등으로 UCPC 본선 진출했다. :dhk: