UCPC 2023 예선 후기

오늘 7/2에 UCPC 2023 예선이 열렸다.
 

결론부터 말하면 5솔하고 본선엔 못 간다ㅠㅠ 내년엔 진짜 간다.
 
ICPC 팀원 분이 이미 팀이 있으셔서 학회 내에서 급하게 한 분을 섭외해서 maker29, tkfkddl59323님과 팀을 꾸렸다.
maker29님은 수학 고수시고 개잘하셔서 언젠가 같이 해보고 싶었는데 마침 잘됬다고 생각했다 ㅎㅎ
 

 
멀 안 먹어야 집중이 잘된다는 걸 최근에 어디서 봐서, 아침 먹고 아무것도 안 먹었었는데 컨디션이 진짜 좋았다. 다음에도 이 방법을 써야겠다.

---

문제 링크

 

타임 라인

 
[0:00] 
maker29님이 ABCD, tkfkddl59323님이 EFGH, 내가 IJK를 맡기로 하고 시작했다.
 
[0:02] A '체육은 코딩과목 입니다' AC - maker29
간단한 구현 문제라고 한다.
 
[0:24] D '더 흔한 타일 색칠 문제' AC - maker29
무슨 문제인지는 모르겠지만 잘 풀어주신 듯하다.
 
[0:28] I '자석' AC - yunny_world
a_i + a_j - k|i- j|의 최댓값을 구하는 문제이다.
바로 방향을 잡은 건 아니고, O(N^2)에서 끙끙대다가 i끼리, j끼리 식정리하니까 풀 만해졌다.
그 뒤에 누적최댓값, 최솟값 쓰는 건 당연한 거 같다. 첨에 세그 쓰려고 했는데, 너무 오버킬 같아서 옆에 호영님한테 잠깐 여쭤보고 누적어쩌고를 쓰기로 했다. 물어보기 잘한 듯..
 
[1:55] C '차량 모듈 제작' 1WA, AC
문제는 maker29님이 읽어주셨고, 풀이는 tkfkddl59323님이 문제 듣자마자 내셨고, 나는 식정리랑 구현만 했다.
N제한이 1000이어서 N^2인거랑 MST 쓰는 게 쉽게 보여서 풀이 방향 자체는 필연적이다. 처음에 구현했는데 -(nan)ind 이 나와서 너무 당황했다. 알고 보니 분모랑 분자를 계속 바꿔 쓰고 있었다... 이거 찾는 데 20분 정도 쓴 듯... 너무 아쉽다.
분모 분자 위치 때문인지 모르고 분모 0일 때 처리하려고 입실론 더하고 있던 내가 바보다 ㅋㅋ
이거 고치고 냈는데 틀려서 봤더니 오차가 너무 컸다. 예제도 틀렸던데 너무 성급하게 냈다. 그냥 위에 써놨던 입실론 지우니까 맞더라.
 
[2:37] F '응원단' AC - tkfkddl59323
처음부터 이거 잡고 계시면서 옆에서 계속 이건 너무 풀고 싶다고 하셨는데, 결국 푸셨다 ㅎㅎ 너무 좋다. 나는 그냥 옆에서 혼자 도출하신 풀이 듣고 있었는데, 갑자기 풀이 나왔다고 하셔서 구현하러 가셨었다. tkfkddl59323님의 구현과의 싸움 끝에 AC를 받으셨다. 
 
[~3:00]
F 풀고 난 이후에 스코어보드 보니까 B, K를 다들 많이 풀었어서 나랑 tkfkddl59323님은 B를 풀러 갔고, maker29님은 K를 풀러 가셨다. 
 
B에 대해 말하자면, 내가 Maximal Spanning Tree 만드는 거까지 하고 그 이후에 DP 어떻게 잘할 수 없나 생각하고 있다가, F가 풀린 이후에 tkfkddl59323님한테 여기까지 생각했다고 말했는데, 그냥 이거 합칠 때 답에 계속 더해주면 되지 않냐라고 말해주셔서 이거 듣고 한 단계 나아갔다. 근데 조금 생각해 보니까 이렇게 하면 O(KM)인 거임.. 그래서 좀 더 생각한다가 Small to Large까지 생각만 하고 확신은 없는 채 계속 고민하다가 끝났다.. Small to Large를 떠올린 게 대회 종료 3분 전인데 너무 아쉬웠다.
 
K는 대회 중간에도 다 같이 봤었는데, 이분탐색 → 그리디로 풀이 방향을 잡으면서 AC와 점점 멀어져 갔다..
 
대회 중에도 B, K만 풀면 본선이라 생각했는데, 먼가먼가 아쉽다. 저번 겨울에 있던 SUAPC처럼 망하진 않아서 괜찮긴 한데, 아쉽다 ㅋㅋ 내년엔 진짜 간다.
근데 Small to Large 문제인데 이렇게 많은 사람들이 빠르게 푼다는 게 믿기지가 않는다. 사람들 왤케 잘함! 
 
그나저나 tkfkddl59323님한테 풀이 중간까지만 만들고 의논하는 게 호흡이 잘 맞는다고 느꼈다. 팀대회가 이런 묘미가 있는 거 같다. 앞으로도 잘 부탁드립니다.
 
대회 열어주신 관계자분들, 참여한 모든 팀들, 그리고 우리 팀원 모두 고생하셨습니다!!