240226 팀 연습 (Jakarta 2022) + 잡설

챔피언십 전 마지막 팀연습이다. 대면 1컴으로 진행하였다.

 

셋 : https://qoj.ac/contest/1109

 

 

petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:33

가운데를 잡은게 나이긴 하지만 F 제목을 보고 꽂힌 petamingks에게 F를 넘겨주었다. 쉬운 문제였는지 풀이가 빠르게 나왔다고 해 컴퓨터를 넘겼지만, 아쉽게도 틀렸다. 그러던 중 kwoncycle이 M 풀이를 냈고 다행히 1번에 맞았다.

 

~1:04

가운데 문제를 모두 본 나는 바로 풀 수 있는 문제가 없다는 사실을 깨달았다. 그러던 중 스코어보드에서 C가 풀려 보았고, 다행히 C는 쉬운 문제였다. 중간에 petamingks에게 컴퓨터를 넘겨주거나 지문을 잘못 해석해 시간이 좀 걸렸지만 틀리지 않고 맞았다.

 

~2:56

이후에는 L을 봤다. 문제 자체는 쉬운 MST 응용이라서 빠르게 짰는데 WA를 받았다. 이 쯤 petamingks와 kwoncycle이 각각 A와 K 풀이를 냈다. A가 더 빠를 것 같아서 A를 일단 짜기 시작했는데, 짜면서 생각해보니 시간 복잡도가 잘 bound되지 않는 것 같아 일단 kwoncycle의 K에 컴퓨터를 넘겨주었다. 나오니까 우선 A 풀이는 어느정도 정리되었고, L을 어떻게 짜면 될까 고민하다가 PBS를 쓰면 잘 처리될 것 같다는 생각이 들었다. 마침 kwoncycle의 K 코딩이 거의 끝나 잠깐 치운 후 PBS를 빠르게 짜 맞았다.

 

~3:31

kwoncycle은 K에서 몇 번의 WA를 받으며 긴 디버깅에 들어갔고, 나는 다익스트라 응용 문제로 보이는 D를 잡았다. 식 정리를 좀 하니 옆에서 petamingks가 아이디어 하나를 던져 주었고, 이를 토대로 다시 식을 정리해보니 놀랍게도 CHT 꼴이 나왔다. 그 쯤 kwoncycle의 K 디버깅이 끝나갔고, 다행히 AC를 받았다. 나는 (다차원의 복잡한 DP지만 식이 대충 정리된 A)와 (다익스트라와 CHT를 짜야 하지만 그 외에는 뭐가 없는 D) 중 하나를 짜야 했고, 두 알고리즘을 모두 빨리 짤 자신이 있었기에 D를 짜기 시작했다.

 

~4:27

4시간쯤 D 코딩을 마치고 예제가 나와서 냈지만 틀렸다. 이때 kwoncycle이 I 풀이를 가져왔고, A를 깔끔하게 짤 자신이 없었기에 그냥 트리에서 익숙한 코딩을 하면 되는 I를 짜기로 했다. 이 동안 petamingks는 D 예제를 만들었다. 하지만 I 케이스 분류가 제대로 되지 않았고, 이를 틈타 D에서 놓친 부분을 발견해 고쳐서 맞았다.

 

~5:00

남은 시간 동안 I 풀이를 열심히 다듬었으나, 결국 완성시키지 못했다. 이 30분 동안은 정말 옆에서 시키는 대로 코딩을 했는데, soulless coding machine도 보통 일이 아니라는 것을 깨달았다.

 

문제별 요약

 

A (D5, Not solved) : petamingks가 풀이를 냈지만 짜지 못하고 끝났다. 거리 함수의 성질을 이용한 bit DP인데 복잡도를 줄이는 것이 조금 복잡하다.

B (?, Not solved) : 기하 문제이지만 대회 중에는 감을 잡지 못했다. segment가 ray의 교집합이라는 점을 이용해 잘 카운팅하는 것 같다.

C (G4, solved by leo020630) : 지문 이해만 잘 하면 쉽게 해결할 수 있다.

D (D4, solved by leo020630, petamingks) : 연산을 시작점이나 도착점에서 쓰는 경우는 쉽게 처리해줄 수 있다. 그 외가 문제인데, 우선 a-b-c 경로에서 b에 연산을 사용할 때 \(H_a,H_c\)의 평균으로 맞춰야 한다는 점은 자명하다. 이러면 cost를 \(H_a, H_c\)에 대한 식으로만 나타낼 수 있다. 이제 b를 기준으로 해 시작점-b, b-도착점과 같이 경로를 분할한 후 비용을 계산하려 하면 CHT 꼴의 식이 나온다. 따라서 각 정점마다 CHT를 돌려주면 된다.

E (?, Not solved) : 뭔가 적절한 문자열 알고리즘을 찾지 못해서 대회 중에는 미뤄두었는데, 버킷으로 해결할 수 있다고 한다.

F (G?, solved by petamingks) : 코포식 문제라고 한다.

G (?,  Not solved) : 대회 중에는 3차원 세그같은 것이 필요해 보여서 잡지 않았다. 이외에도 여러 풀이가 있는 것으로 보인다.

H (?, Not solved) : 어려운 게임 이론 문제이다.

I (P1, Not solved) : 케이스 분류가 귀찮은 트리 constructive 문제이다. kwoncycle이 풀이를 거의 냈으나 구체화가 모자라 대회 시간 중에는 풀지 못했다.

J (?, Not solved) : 관찰이 엄청나게 어려운 조합론 문제라고 한다.

K (D?, solved by kwoncycle) : kwoncycle이 CTF에서 하는 것과 비슷한 정수론 문제라고 하며 잘 풀어주었다.

L (P2, solved by leo020630) : MST를 구한 후, MST의 간선들이 절대 쓰이지 않도록 cost를 증가시키는 문제이다. 즉 MST에 포함되지 않은 간선들로 MST를 만들 때 기존 MST 간선들에 해당하는 정점이 언제 이어지는지 찾아야 하는데, PBS로 처리할 수 있는 전형적인 상황이다. 끝나고 보니 PBS는 오버킬이고 새로 만든 MST에서 LCA로 RMQ를 날려도 되는 것 같다.

M (G?, solved by kwoncycle) : 쉬운 문제인 것 같다. 문제를 읽지 않았다.

 

느낀 점 + 피드백

풀이를 못 짜고 나오는 경우가 없도록 컴퓨터 관리를 확실하게 하자.

 

코딩을 한 사람이 너무 몰아서 하면 과부하가 오기 쉬운 것 같다.

셋이 도와주지 않으면 어쩔수 없지만 가능하면 적당히 나눠서 짜자.

 

보지 못한 문제들이 엄청나게 어렵지는 않았다. 서울 리저널 때에도 그랬지만, 스코어보드를 너무 믿지는 말자.

 

초반 문제에서는 페널티를 쌓지 말자.

 

WA 디버깅은 프린트로 하자.

 

마치며..

 

이제 정말 단 한 번의 진검승부만이 남았다.

 

솔직히 작년까지는 이런 좋은 기회를 얻게 될 줄도 몰랐고, PS판에서 얻을 수 있는 것은 22 리저널 성적이랑 SCPC 정도로 끝냈다고 생각해서 ICPC를 준비할 때에도 상 타면 좋고 아니면 말고 정도의 자세였다. 실제로 이 팀으로 한 서울 리저널 전 팀 연습은 2~3번에 그쳤던 것 같다.

 

허나 리저널에서 잘 풀린 상황은 아님에도 생각보다 좋은 성적이 나와버리고, 플레이오프에 대한 정보가 점차 구체화되면서 월드 파이널 진출이 불가능한 자리만은 아니라는 생각이 점점 선명하게 다가왔다.

 

그래서 지난 방학은 정말 여기에만 몰두했던 것 같다. 뭐 학창시절 대부분을 PS와 함께 하긴 했지만, 살면서 이렇게 PS에 집중한 적이 얼마나 있었나 싶다. 특히 많은 양의 어렵고 새로운 내용들을 단기간에 흡수하는 것은 정말 힘들었다. 마치 지금까지 PS를 대충한 벌을 받는 것만 같았다. 새삼 지금까지는 마냥 동경의 대상이었던 WF 진출팀, 또는 IOI 국대, 다른 여러 고수분들에 대해 이런 과정을 미리, 그리고 더 많이 거쳤다는 점에서 진심으로 대단하다는 생각이 들었다.

 

내가 열심히 했다고는 하지만 결국 ICPC는 팀 대회이다. 우리 팀이 다른 WF 진출 경쟁 팀들에 비해 여러모로 부족한 부분이 있는 것은 모두가 느끼고 있었고, 이 간극을 메우기 위해 팀 연습을 정말 열심히 했던 것 같다. 다들 힘들었을 텐데도 열심히 달려준 점에 대해 감사하다는 말을 전하고 싶다.

 

거창하진 않지만 이런 글을 왜 출국도 전인 지금 쓰냐 하면, 만약 WF 진출에 실패하면 정신이 어떨지 가늠조차 되지 않기 때문이다. 이제 PS에만 빠져있을 수 있는 기간이 얼마 남지 않기도 했고 이번 기회를 놓치면 다음이 있을지, 과연 지금처럼 전력을 다할 수 있을지 확신이 들지 않는다. 그래서 그냥 하고 싶었던 말을 차분한 상태에서 하는 나름의 유언장 또는 출사표였다고 하겠다. 뭐 실패하면 유언장, 성공하면 출사표 아니겠는가?

 

지금까지 팀 연습을 도와주신 연대 SCC, Cookie 팀, 전북대 2 3 5 8 14 팀,

바쁘신데도 팀 연습과 더불어 여러 도움 주신 Hyperbolic, menborong, slah007 선배, 그리고 다른 POSCAT 구성원 여러분,

아직은 별로 한 건 없지만 베트남에 Co-Coach 자격으로 동행하는 qjatn0120 선배,

그리고 금전적으로 지원해주신 포스텍 컴퓨터공학과에 감사의 말씀을 드린다.

 

팀원 두 명은 아직은 잘 모르겠고 대회 끝나면 고마워해야 할지 결정하도록 하겠다.

 

베트남에서 뵙겠다.