UCPC 2022 본선 후기

• 팀연습
• 본 대회
  • Phase 1 : WTF?
    • J - 교집합 만들기
    • H - 특별상
    • L - 커넥티드 카 실험
  • Phase 2 : TLE (K - 전대프연 토너먼트)
  • Phase 3 : Segment Tree (D - 전대프연 토너먼트, F - 대충~몬스터~게임)
    • F - 대충 카드로 몬스터 잡는 게임
• Post Mortem

• 본문에서 언급되는 난이도 티어 (브/실/골/플/다/루) 는 Solved.ac 기준입니다.

• 팀에 관해서는 예선후기 에도 적어두었습니다 :)

팀연습

UCPC 본선은 ICPC와 똑같은 5시간 3인 1PC 대회입니다. 고려대 Hongjun7님 등 팀대회를 즐기면서 잘하기 위해서는 이 대회 프레임에 맞는 준비가 필요합니다. 3시간 3PC 대회에 비해, 5시간 1PC 대회는 크게 다음과 같은 눈에 띄는 차이가 있습니다

• 중위권 이상의 팀 대부분은 구현이 bottleneck입니다.
• PC 앞에 항상 1명이 앉아있다는 말은, 반대로 2명이 항상 컴퓨터에서 손을 떼고 있다는 의미가 됩니다. 즉, 푸는 사람은 2명이기 때문에 문제를 동시에 2개 tackle하거나, 둘이 논의를 통해 솔루션을 구상할 수 있습니다
• 가장 위험한 것은 아 맞는줄 알았는데 짜다보니까 아니다 입니다. 3PC 대회에서 30분동안 말리는 것은 팀의 시간을 30분 소모한 것이지만, 1PC 대회는 “PC-시간” 이 3배 귀한 자원이기 때문에 컴퓨터 앞에서 날린 20분은 컴퓨터 밖에서 날린 최소 40분~1시간 가량의 가치가 있습니다.

그래서 대회의 포맷에 맞게 2번의 팀연습을 더 했습니다.

• 2021 서울 리저널 팀연습 : 작년 ICPC의 문제를 아무도 본적이 없다는게 이미 저희가 얼마나 PS를 떠나있었는지 보여주는게 아닐까요? K번을 시간내에 구현해내지 못했다는 점 외에는 결과 자체는 크게 문제는 없었지만, Stet-stet과 제가 한문제씩 잡고 각각 케이스정리와 구현이슈로 필요 이상으로 고통받으며 PC-시간을 소모했습니다.
• 2020 자카르타 리저널 팀연습 : 디닉 코드를 다 짜놓고 어이없는 DFS 구현실수를 해서 (…) 제가 PC-시간을 혼자 1시간 가까이 날린 중죄를 저질렀습니다. 전반적으로 많이 말렸던듯 합니다.

세명 모두 구현이 딱히 강한것은 아니라는 점을 재확인했습니다. 묘하게 컨셉이 겹치는 저희 팀은 아마도 여건이 갖추어지면 다이아 수학/DP 문제를 격추할 수 있는 대신 (특히 세명이 수학을 좀 좋아하는 구성이고, DHDroid와 Stet-stet은 DP/Construction에 굉장히 강합니다. 저는 상대적으로 정수론 류 문제를 좋아하고…) UCPC 2019 택시 같은 문제가 나온다면 그대로 망할수도 있겠다는 생각이 들었습니다.

본 대회

3년만의 오프라인 대회라서 설레는 마음으로(?) 찾아간 대회장은 코엑스 근처라서, 저는 굉장히 가까웠습니다.

2019년 UCPC는 고려대였고 굉장히 환경이 좋았는데, 이번에는 다소 협소한 감이 있었습니다. 학교 대관이 안되면 사실 어쩔수 없었겠지만…

Competitive Programming의 상징같은 문제별 풍선을 보니 묘하게 들떴던 기억이 있습니다. ㅋㅋ

Phase 1 : WTF?

초반전략은 ABCD(Gratus)/EFGH(Stet-stet)/IJKL(DHDroid) 로 나눠 읽고, 쉬운걸 먼저 찾은다음 scoreboard-driven하기로 했습니다. 이 과정에서 중요한건 모든 문제를 읽는 것입니다.

연습했던 대로 문제를 나누어 읽었습니다. 저는 ABCD를 잡았고, 보통 앞에 쉬운게 하나 섞여있고 제가 제일 코딩이 빨라서 이렇게 하는데 사실 UCPC본선같은 플레 이상 문제로 빡빡하게 채워진 대회에서는 큰 의미는 없습니다.

• A : 뭔가 하나씩 채워나가면서 작은 문제가 되는게 DP같은 느낌. DHDroid에게 넘겨야 하나? 를 생각하고 일단 제꼈습니다.
• B : Backus-Naur Form, 컴파일러같은게 나오는걸 보고 즉시 버리기로 했습니다.
• C : 비교적 할만 해 보였습니다. 좀 생각해 보기로 하고…
• D : 전형적인 수열과 쿼리 문제에다가, 뭔가 합의 합의 합의 합을 해야할거같은 느낌에 일단 C보다는 어려워 보였습니다.

저는 여기까지 읽고, C를 생각하면서 쉬운 문제를 뒤에서 identify 해주길 기다렸습니다. 뒤 문제를 읽은 두사람도 고통받고 있는거 같았는데, 여기까진 나름 PS하는 설렘에 기분 좋았던 기억이 있습니다.

뒤에서 J번이 비교적 쉬운 문제임을 파악해왔고, 바로 풀어서 맞았습니다.

J - 교집합 만들기

난이도 : S1             AC Time : 00:20
solve : DHDroid
code : Gratus907

1개 구간으로 가능한 경우, 2개 구간으로 가능한 경우, 불가능한 경우가 있음을 파악하면 됩니다. 1개는 자명하므로 불가능과 2개를 구분하면 됩니다.

만약 3개 이상의 구간의 교집합이 $[l, r]$ 이라면, 이들 중 $l$에서 시작해서 $r$보다 오른쪽까지를 커버하는 구간이 있고, $r$에서 끝나면서 $l$보다 왼쪽에서 출발하는 구간이 있습니다. 이 두개를 택하면 2개로 줄일 수 있습니다. 역으로, 2개의 구간을 이용해서 $[l, r]$을 커버하기 위해서는 $l$에서 출발해서 가장 멀리까지 닿는 구간과, $r$에서 끝나면서 가장 왼쪽에서 출발하는 구간을 이용해서 만들 수 있는지 확인하면 충분합니다.

아마 DHDroid가 문제랑 거의 같이 풀이를 전달했던거 같은데 정확히는 기억이 안나네요.

H - 특별상

난이도 : S1             AC Time : 00:28
solve : Stet-stet
code : Gratus907

마찬가지로 Stet-stet이 문제와 답을 동시에 전달했습니다.

심판의 점수가 높은 $K$명은 어차피 무슨 상이든 받을수밖에 없으므로, 그걸 먼저 그냥 심판상을 줘버리고 남은사람중 주최자 점수가 높은 사람 $M$명한테 주최상을 주면 주최자 입장에서 최선의 결과를 얻을 수 있습니다. 정렬 두번하는 그리디 문제.

L - 커넥티드 카 실험

난이도 : G4             AC Time : 00:48
solve : DHDroid, Gratus907
code : Gratus907

제가 처음에 시작점에서 양쪽으로 끝까지 가보는 간단한 그리디로 된다고 생각하고 Stet-stet과 잠깐 얘기했지만, 둘다 같은 착각을 해서 실수를 찾지 못했습니다. 구현해서 한번 틀리고 DHDroid가 찾아줬습니다 :fan:

매 시점에, “지금 먹은 차보다 하나 왼쪽/오른쪽의 차를 먹을 수 있는지” 를 투포인터처럼 판단합니다. 투포인터 구현은 별로 어렵지 않고, “최대한 많은 연료를 남기면” 최대한 멀리 갈수 있으므로 매 시점에는 그리디하게 선택이 가능합니다.

Phase 2 : TLE (K - 전대프연 토너먼트)

여기까지 대회가 상당히 잘 굴러왔습니다. 결정적으로, 제가 L을 구현하는 동안 K를 DHDroid와 Stet-stet이 거의 다 풀었었고 거의 바로 구현에 들어갈 수 있었습니다.

이 K가 어떤 끔찍한 결과를 가져올지는 생각지 못했습니다.

난이도 : P2             AC Time : 02:15 (+8)
solve : DHDroid, Stet-Stet
code : DHDroid

문제를 요약하자면, 토너먼트에서 1개의 경기 결과가 유실되었을 때 그 유실된 결과를 복원하는 문제입니다.

저는 풀이를 간단히만 들었는데, 일종의 재귀적인 셋업을 통해 매번 깊이를 1씩 줄인 토너먼트를 구축할 수 있으며 구현이 귀찮지만 그렇게까지 어렵지는 않다고 합니다. 공식 풀이에 나온 두번째 방법 (출제자의 풀이) 와 비슷하다고 들었습니다.

L을 풀고 나서, 새로 풀 문제를 찾던 중 DHDroid가 무슨 재귀적으로 풀면... 같은 말을 하길래 바로 넘겼습니다. DHDroid가 평소 constructive한 문제에 비상한 실력을 보여주므로 별 어려움 없이 맞아오겠지 하고 저는 M, F, C, D 등등을 Stet-stet과 잠깐씩 탐방하며 다음 풀 문제를 찾으러 갔습니다.

이후로 WA와 TLE를 합쳐 무려 8번의 페널티를 받았고, 그중에서도 “코드가 틀린거같지는 않은데 왜 TLE인지 모르겠다. 복잡도에는 이상이 없다”는 말을 듣고 상수 최적화 문제인가? 라는 생각을 했습니다. 아래는 TLE의 기록입니다. ㅋㅋ…

• 코드 사방에 std::map<int, int>을 떡칠해서 느린것으로 생각하고, Stet-stet과 제가 정렬성이 필요없다면 std::unordered_map 으로 바꿀것을 제안했습니다.
• 그래도 TLE를 받아서, 도대체 무슨 문제인지 찾기 위해 로컬에서 무려 max test를 만들기로 했습니다. 랜덤 페어링으로 토너먼트를 만들고 하나를 버리는 것은 5분이면 짤 수 있으니…
• 놀랍게도 DHDroid의 코드는 로컬 (제 M1 Pro 맥북) 에서 max case에 대한 답을 1초 이내에 찾고 있었습니다. 제한 시간은 2초였으므로 이는 상당히 수상했습니다.
• M1이 미친 칩이라 그런거 아니냐? 는 얘기를 하고, 일단 시간을 더 줄이기로 했습니다. 이것저것 커팅을 좀 하니 시간이 로컬에서 0.7초대로 줄어들었고, 여전히 TLE를 받았습니다.
• 결국 제가 “이렇게된거 FAST IO를 짜겠다”라고 컴퓨터를 잡았는데, 팀노트에 Fast hash table 이 있음을 떠올리고 그걸 집어넣었습니다.
• 로컬에서는 0.4초대, 서버에서 1.32초로 통과했습니다.

참고 : Fast hash table은 Codeforces Link 에 있는 __gnu__pdbs::gp_hash_table 이며, GCC 컴파일러의 확장 자료구조 중 하나입니다. 일반적으로 unordered_map보다 수 배 가까이 빠르다고 알고 있습니다.

이런 문제를 지양하는 것으로 알려진 UCPC에 왜 우리는 이런 참사가 벌어졌는지는 알 수 없으나, 아마도 정해가 해시테이블을 쓰는게 아니지 않을까 싶습니다. 슬라이드에도 언급되지 않은걸보니 저희가 이상하게 푼것 같긴 한데, 아무튼 이 문제에 무려 1.5시간이 들어갔습니다.

Phase 3 : Segment Tree (D - 전대프연 토너먼트, F - 대충~몬스터~게임)

그동안 저랑 stet-stet은 뒤 몇문제를 고민했습니다. C번은 예제를 보고 너무 어려운거 같다 고 버렸고, D는 stet-stet이, F는 제가 잡고 있었습니다. 저희 둘다 M같은 류의 수학문제를 좋아해서 좀 고민해보았는데 다항식들을 빠르게 관리한다는 점에서 FFT를 잘 쓴다는건 알겠지만 그이상은 얻지 못했습니다.

D는 stet-stet이 Lazy seg로 풀 수 있다 고 했고, 저는 수쿼류 문제를 잘 모르기 때문에 그런가보다 하고 있었습니다. 여기서부터 segment tree 대참사 가 벌어졌습니다

• 때는 두번째 팀연습 (Jakarta 2019) 이후, stet-stet이 현재 있는 세그먼트 트리 구현을¹ 매우 generic한 구현으로 교체할 것 을 제안했습니다
• 이 새로운 구현체는 template 함수를 굉장히 extensive하게 활용해서, 합세그를 xor세그나 곱세그로 교체하는 것이 함수 하나를 갈아끼움으로써 가능하고 전체에 mod P 등을 enforce하는것이 매우 쉽다는 장점이 있었습니다.
• 일부 이 라이브러리에 우리가 상대적으로 익숙하지 못하고, 타이핑량이 좀 늘어난다는 점 등이 조금 걱정스러운 것은 사실이었으나, 신기한 세그 쓰는 문제가 생각보다 잦고 이걸 잘 이용하면 기본문제부터 금광세그까지 잘 커버할수있다는 점이 굉장히 매력적으로 다가와서 이 변경을 approve했습니다.
• 다만 제네릭한 세그먼트 트리 구현체는 몇가지 기본적인 가정에 기반하고 있습니다. 정확한 가정의 집합은 모르겠지만 처음 설명을 듣고 코드를 봤을때는 충분해 보였습니다
• 코드를 숙지해야가야한다는 생각은 했지만, 반대로 템플릿이 엄청 제네릭하니까 진짜 갈아 끼우기만 하면 사실 S.modify 와 S.query만 써서 풀수있지 않을까? 라는 생각이 들어서 그냥 남은 시간동안 접미사 배열 같은 주제들을 공부하는데 투자했습니다

결국, 현장에서는 이런 문제들이 있었습니다.

• Stet-stet은 D에 대한 그럴싸한 풀이에 도달했고, 저는 100%를 이해하지는 못했으나 대충 맞는 방향 이라는 생각은 들었습니다. DHDroid도 비슷하게 판단했습니다.
• D는 상당히 복잡한 형태의 segtree 활용을 요구했고, 솔루션을 떠올린 Stet-stet은 이 문제를 풀 희망이 있는 유일한 팀원이었기에 PC를 넘겼습니다.
• 이 구현은 결국 대회가 끝날때까지 완료되지 못했습니다. 나중에 듣고 보니, 앞서의 제네릭한 세그먼트 트리 가 갖는 기본적 가정 에서 벗어난 구현이 필요했다고 합니다.

F번 (대충~몬스터~게임) 은 저와 DHDroid가 잡았습니다. 대충 얘기했던 것들을 기억을 되짚어 보면…

F - 대충 카드로 몬스터 잡는 게임

난이도 : P1             AC Time : After freeze
solve : DHDroid, Gratus907
code : DHDroid, Gratus907

• 만약, 현재 어떤 몬스터가 있고 내 손에 그 몬스터를 잡을 수 있는 매칭되는 카드가 있다면, 반드시 잡는 것이 자명하게 최적입니다.
• 약간 반대로 생각해서… “리필시점” 을 미리 고정한다고 생각하면
  • 리필시점이 $t_1, t_2$라고 할 때, $t_1$부터 $t_2$ 까지의 몬스터들 중 몇마리나 잡을 수 있을까요?
  • 그 내부에 있는 몬스터의 종류 만큼을 잡을 수 있습니다. 이를 score 라 하겠습니다.
  • 나머지 카드들은 대충 아무렇게나 버리면 됩니다.
  • $t_1$ 부터 $t_2$ 사이에 리필이 가능하려면, 그 사이 간격이 $\ceil{K/2}$ 보다 커야 합니다.

리필 시점을 고정하고 문제를 풀자 (어차피 리필 시점이 고정되어 있다면 전략이 유일) 하다는 얘기를 DHDroid와 나눴습니다. 뭔가 DP식 접근까지는 쉽습니다.

• 즉…다음과 같은 DP를 풀 수 있으면 됩니다. \(D[i] = \max \{ D[j] + \text{score}(j+1, i) \mid 1 \leq j \leq i - \ceil{K / 2}\}\)

이 DP를 꽤 오래 고민하다가, 저는 다른 문제를 잠시 보던 도중 DHDroid가 “$D[j] + \text{score}(j+1, i)$ 를 세그먼트 트리로 관리” 하는 풀이를 제안했고, 거의 페어코딩에 가깝게 구현했습니다. 이 과정에서 D번에서 쓴 레이지세그 구현을 사용했는데, 팀노트를 타이핑하다가 오타가 있었음을 모르고 계속 제출하며 틀리는 등(…) 대참사가 발생했습니다.

이 문제는 난이도가 P1이기는 하지만, 솔직히 그렇게까지 고전했어야 할 문제였다는 생각이 들지는 않습니다. 구현상의 실수가 뼈아픕니다.

F를 맞추고 나서는, Stet-Stet이 D번과 계속 싸우는 동안 I (사건의 지평선), M(x+ +x) 등을 읽었습니다. DHDroid와 제가 (사실 DHDroid가 거의 혼자) I번 풀이도 논의끝에 완성했는데, 세그먼트 트리를 만든다음 그 노드들에서 SCC를 돌리는 문제로 상당히 구현이 빡세지만 시간만 많았다면 (과연…?) 할만해 보였습니다. :(

Post Mortem

UCPC는 항상 PS의 즐거움과 우리 실력의 미진함을 깨우쳐주는 대회입니다. ICPC에 비해 좀더 OI-틱한 문제가 나와서 더 그런것 같기도 합니다.

올해의 새로운 팀원 Stet-Stet은 꽤 높은 확률로 저랑 같이 제 마지막 ICPC를 뛸거 같은데, 이제 딱히 CP 성적에는 미련은 없지만 이번 대회에서 느낀걸 대충 적어보자면….

• 팀노트의 구현체를 Black-box로 활용하는 것은 상당히 위험함을 깨달았습니다. 만약 제네릭한 구현체를 저나 DHDroid가 이해하고 있었으면 훨씬 편했을 것입니다. 이해하기 어렵거나 시간이 많이 드는 구현체라면 차라리 간결한 것을 가져가는 것이 나을 수도 있었겠습니다.
• 반면에, 저희처럼 구현력이 thinking에 비해 많이 딸리는 팀은 팀노트에 최대한 많은 것을 packing해가는 것이 유효합니다. 당장 저희가 못풀기는 했지만 E(LR-Flow), M(FFT) 등 떠올렸더라도 팀노트가 없었더라면 손을 못댔을 문제들이 꽤 있었습니다.

대회가 끝나고는 예전부터 Hashcode 등으로 함께했던 Coffeetea, Dlwocks31이 새로 학과 동기인 Nevivurn을 영입해서 결성한 Industrial Function Agent² 와 고기를 먹으러 갔습니다. :blobaww: 이쪽팀도 상당히 재밌는데, 여기는 F를 풀지 못한 대신 C를 해결했습니다. 저희랑 비교했을 때 엄밀한 논증보다는 직관력이 뛰어난 팀원 구성이 큰 영향이 있지 않은가 싶습니다.

이기회에 내려놨던 algorithmic thinking을 되찾기 위해 Dlwocks31과 (+ 두 팀의 팀원들 함께) weekly rehab 스터디를 결성하기로 얘기했습니다.

오랜만의 오프라인 대회치고는 상당히 frustrating했습니다. Competition을 내려놓아야 더 즐길 수 있을텐데 하는 생각도 들고… 그래도 개인대회였다면 5시간에 저런 구현실수나면 집중하지 못했을텐데, 팀대회라서 좀더 재밌게 치를 수 있지 않았나 싶습니다.

Kudos to my dear teammates - Stet-stet & DHDroid :)