UCPC 2023 예선 후기

Sat Jul 01 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솔로 마무리했다... 말고는 딱히 결론이 없어서, 여담이나 써볼까 한다.

  1. F 20분 퍼솔을 보고 빌조갓을 외쳤고, 빌조가 푼 게 맞는 줄 알았으나... 알고 보니 퍼솔의 주인공은 @whqkrkt04가 아니라 @gina였다. 그럼에도 불구하고 쉽게 생각할수록 쉬운 문제가 정말로 맞았기 떄문에 이득이 아니었나 싶다.
  2. 초반 30분 동안 '대회장에늦게도착할수록강한팀이다'와 '샤레롱은 미국갔어'의 치열한 1,2위전은 매우 가슴이 웅장해지는 광경임과 동시에... 슼보에 내 닉네임이 계속 등장해서 좀 정신 없었다. ㅋㅋ.

가슴이 웅장해지는 광경

  1. K는 greedy + simulation이 실제로 가능하다고 한다. 그런 점에서 다시 보면 은근 재밌는 방식을 찾은 것 같다.
  2. H의 수학적인 구조를 다음과 같이 표현할 수 있다고 전해들었다. 팔찌들의 문자열 표현 집합과 concat 연산이 정의된 group으로부터 \(Z_2 \times Z_2\)로 가는 group homomorphism이 존재한다. 예를 들면 \(\phi(BB) = (0, 0)\), \(\phi(B) = (1, 1)\) 등등.