UCPC 2023 예선 후기
올해도 어김없이 돌아온 ucpc 시즌...인데 모종의 억까로 인하여 팀이 삭제되었다. 급하게 팀원을 다시 구한 결과 제작년 같은 팀원이자 구데기컵 전문가(?) @rubix와 무려 2인팀(!)을 결성하게 되었다. 팀이 정확히 3명이 아니면 본선에 아예 참가가 불가능하다고 써 있길래, dummy로 존재해줄 사람을 어찌어찌 구해서 참가신청을 넣었다. 다만 전력이 \(2/3\)이 되어버렸기에... 특별상에 잘하면 얻어걸리지 않을까라는 생각으로 즐겜팟을 꾸렸다. 오프라인으로 만나지도 않았고 디코로 전화연결만 해서 진행했다. 덕분에 집에서 듀얼 모니터로 실시간 슼보를 바로 옆에 띄워둘 수 있었다.
Phase 1
우선 내가 그나마 ps를 최근까지 잡고 있었기 때문에, 문제가 홀수 개면 반올림해서 앞쪽 파트를 읽기로 했다. 제일 쉬운 A번을 먼저 잡았고, 대충 1 2 3이 입력이고 90도 180도 270도 얘기가 있길래 다 더해서 4로 나눈 나머지를 내면 되겠다 싶었다. 라는 생각으로 코드를 짰는데 답이 안 나오길래 결국 문제를 처음부터 다시 읽었으나, 내가 추정한 내용이 맞아서 상당히 당혹스러웠다. 그렇지만 알고 보니 입력을 받지도 않고 있던 게 원인이었다. A AC (2 min, +0)
슼보를 보니 아무 일도 안 일어나있길래 우선 B부터 읽었다. B는 말이 어렵게 써 있어서 이해하는데 시간이 좀 걸렸고, C는 일단 그림을 보자마자 넘겼고, D는 잠깐 생각해보니 모든 \( K \times K\) 보드가 독립인 게 바로 눈에 보여서 코딩을 시작했고, 푸는 도중에 AC가 뜨길래 풀이에 확신을 얻었다. 얼마 안 가서 1트에 성공. D AC (9 min, +0)
Phase 2
이 시점에서 슼보에 B, I, K가 풀려있던 것으로 기억한다. I를 rubix가 잡기 시작하고, 나는 B로 갔다. 대충 봤을 땐 어려워보였는데, 이 시점에서 다시 봐도 어렵다는 문제가 발생했다. \(K=1\)이면 간선 역순 정렬하고 DSU를 끼얹어서 풀린다는 게 보였는데, \(K\)가 클 때는 뭔지 잘 모르겠더라. 연결된 component별로 \(i\) 회사 소속인 창고의 개수를 저장하고 있을 수도 없고, 창고의 리스트를 naive하게 관리하고 있으면 합치는 지점에서 \(O(N^2)\)이 걸리니까 아무 생각이 없어졌다. 생각하는 도중에 rubix가 I AC (19 min, +0) 을 띄웠고, B랑 K를 교체했다.
K는 이분탐색이 가장 먼저 떠올랐고, 어떤 parameter \(k\)에 대해서 \(k\)개 이하의 중첩 상태를 유지하면서 구간을 집어넣을 수 있는지를 greedy + simulation으로 처리할 수 있지 않을까를 고민 중이었다. 그런데 이걸 \(O(Nk)\)보다 빠르게 할 수 있는지에 대한 아이디어로 발전이 안 되길래 다시 막혔다. 이 때부터 머리라는 걸 쓰기 시작했다. 먼저 어떤 두 값 \(a_i < a_j\)에 대해서 각각을 포함하는 세미나 \([a, a+T-1]\), \([b, b+T-1]\)가 \(b \le a \le a_i < a_j \le b+T-1 \le a+T-1\) 순서로 열린다면, 외부 강사의 세미나 일정 순서대로 전체 세미나가 끝나도록 두 세미나 일정을 바꿔줘도 무관하다는 관찰을 할 수 있다. 그러면 모든 최적해가 이러한 성질을 만족한다고 가정할 수 있다. 그리고 증명은 못 하겠지만 강력하게 맞다는 직감이 든 최종 풀이는, \(a_i\)들을 정렬한 후에 index를 \(k\)로 나눈 나머지가 같은 \(a_i\)들끼리만 묶어서 \(k=1\)인 새로운 instance \(k\)개를 만든 것과 전체 instance가 같다는 것이다. \(k=1\)인 instance는 \(O(N)\)에 검증이 가능하므로 ok. K AC (27 min, +0)
bool possible(int t, const vector<int>& arr) {
int n = arr.size();
int right_end = 0;
for (int i=0; i<n; ++i) {
if (right_end >= arr[i]) return false;
right_end += t;
right_end = max(right_end, arr[i]);
}
return true;
}
이 다음으로는 다시 B로 넘어갔다. rubix도 B 풀이를 아직 못 낸 상황이었고, 그래서 그 사이에 퍼솔이 나온 C와 담당을 교체했다. 이 시점부턴 루트분할, FFT, SIMD로 뚫기 같은 잡생각들을 했으나 9분 퍼솔인 문제에 그런 문제가 튀어나올 것 같진 않았다. 그렇게 10분 정도를 더 있다가 갑자기 map에 small-to-large 끼얹으면 될 거 같다는 사실을 발견했다. 시간복잡도가 바로 떠오르진 않았으나 이 정도 풀이면 9분 퍼솔이 말이 된다고 생각해서 바로 코딩에 들어갔고, 제출하니 샤레롱답지 않게(?) 한 번에 맞았다. B AC (46 min, +0) 덕분에 같은 솔브수에서는 패널티가 꽤 작아서 상위권을 유지하고 있었다.
Phase 3
rubix가 C번을 잡다가 런타임 에러를 내고 있었고, 나는 F로 넘어갔다. 도중에 C를 디버깅하는 걸 도와주다가 sort 함수를 잘못 만들었다는 걸 고치는 성과는 있었는데, RTE가 WA로 바뀌었다. 슬슬 문제가 한 번에는 안 보이는 시점이었던 것 같다. F가 거의 한 시간이 다 되어갈 때까지도 퍼솔이 슼보에서 돋보였는데, 그 퍼솔을 낸 팀이 앞에서 말한 억까로 인해 삭제된 팀이었어서 유추를 좀 했다. 문제가 아주 전형적이지는 않아보여서, 저 중에서 @whqkrkt04이 풀어낸 게 아닐까라는 추정을 했다. 이 분은 독보적인 약자멸시 스킬을 가진 오렌지 원주민이기 때문에, F가 쿼리들이 괴랄하긴 해도 쉽게 생각하면 쉽게 풀릴 문제라고 보는 게 타당해보였다. 그렇게 3분 정도 생각을 하니 행과 열의 기우성에 따라 모든 숫자들을 4개 그룹으로 분류해서 본다는 아이디어를 떠올렸다. 그리고 S 타입의 쿼리를 처리할 아이디어를 생각하다 보니, \(\frac{n}{2} \times \frac{n}{2}\) 꼴의 subboard들을 \(2 \times 2\)개 가지고 있으면, 각 subboard 내의 숫자들은 상대적인 위치를 유지하고 있다는 걸 관찰했다. 다만 \(\frac{n}{2}\) 주기로 유지되는 상대 위치이기 때문에 offset은 따로 관리해주어야 하고, 이러면 자연스럽게 S 타입 쿼리들까지 처리할 수 있다는 걸 발견했다. 이건 로컬에서도 비교적 자주 코드를 수정하느라 시간이 꽤 소요됐다. 제출해보니 RTE. off-by-one 에러인가 싶어서 경계선에 가까운 S 쿼리들을 넣어봤는데 답은 잘 나오길래, 다시 코드를 읽다가 offset에서 mod \(\frac{n}{2}\) 처리를 제대로 안 해줬다는 게 보여서 수정해서 제출. F AC (97 min, +1)
이제는 J를 제외한 모든 문제가 퍼솔은 나온 상황이었다. E는 지문도 간단한 데다가 문제도 inversion이 소재고 mod도 998244353이길래 모 수학 덕후의 다항식 사랑이 만든 문제일 거 같아서 바로 튀었고, G는 parameter P가 쿼리로 들어오는 형태길래 offline + 자구비빔밥의 향기가 강하게 난다는 것까지만 보고 넘어갔다. H는 출력 파트에 명세가 너무 길어서 문제도 안 읽었다. 이건 다시 생각해보니까 잘못 판단한 거긴 했다. 이 시점에서 rubix한테 C를 넘겨받고 rubix가 E, G, H를 읽으러 갔다. C도 퍼솔이 나온 시점, 풀린 정도를 봤을 때 풀이가 틀릴 리는 없어보였다. 기하라서 뭔가 처리 못한 예외 케이스가 있나도 의문이었는데, 그러기엔 모든 팀이 패널티도 별로 없었다. asin()
을 써서 오차가 심해졌나 싶었는데, long double을 써도 여전히 WA가 뜨고 있었다. 지문도 다시 읽어봤으나 잘못된 부분이 없었다.
그렇지만 그 사이 H에서 rubix가 강력한 framework를 제시했다. 팔찌를 최대한 reduction시킨 다음 그 최종 형태끼리만 비교하면 가능성을 판정할 수 있다는 것이었다. 아주 많이 본 패턴이었기 때문에 나도 이게 맞다고 확신을 했고, rubix는 가능한 모든 reduction 형태를 찾으러 갔다. 그리고 얼마 뒤 이런 답장이 왔다.
갑자기 H가 대회 끝날 때까지 풀리긴 할까라는 의문이 들었다. 그래도 할 게 없으니 C랑 H를 잡는 게 맞는 판단이었다. 그러다가 갑자기 C에서 틀린 게 보였다. 왜 for loop 안에서 원본 배열에 swap을 쓰고 있는 거지...? 고쳤더니 바로 맞았다. C AC (126 min, +3)
그 후엔 G를 잡아볼까 싶었는데 마땅히 좋은 생각이 안 떠올랐다. 그 와중에 rubix가 H를 한 번에 맞아서 왔다!! H AC (129 min, +0) 코드 길이 보니까 python인데다가 4800 byte가 나왔더라.
이 때 50분이 남았고 8솔이었기 때문에, 아마 본선은 가지 않을까라는 생각으로 이 때부턴 별 거 안 했다. E가 그들만의 웰노운인 거 같아서 생성함수스러운 뭔가를 만들어보려고 했는데, 그 이상의 진전이 없어서 이후로는 별 성과가 없었다.
Conclusion
기분 좋게 8솔로 마무리했다... 말고는 딱히 결론이 없어서, 여담이나 써볼까 한다.
- F 20분 퍼솔을 보고 빌조갓을 외쳤고, 빌조가 푼 게 맞는 줄 알았으나... 알고 보니 퍼솔의 주인공은 @whqkrkt04가 아니라 @gina였다. 그럼에도 불구하고 쉽게 생각할수록 쉬운 문제가 정말로 맞았기 떄문에 이득이 아니었나 싶다.
- 초반 30분 동안 '대회장에늦게도착할수록강한팀이다'와 '샤레롱은 미국갔어'의 치열한 1,2위전은 매우 가슴이 웅장해지는 광경임과 동시에... 슼보에 내 닉네임이 계속 등장해서 좀 정신 없었다. ㅋㅋ.
- K는 greedy + simulation이 실제로 가능하다고 한다. 그런 점에서 다시 보면 은근 재밌는 방식을 찾은 것 같다.
- H의 수학적인 구조를 다음과 같이 표현할 수 있다고 전해들었다. 팔찌들의 문자열 표현 집합과 concat 연산이 정의된 group으로부터 \(Z_2 \times Z_2\)로 가는 group homomorphism이 존재한다. 예를 들면 \(\phi(BB) = (0, 0)\), \(\phi(B) = (1, 1)\) 등등.