2024 ICPC Seoul Regional 풀어보기

https://www.acmicpc.net/category/detail/4348

 

260412 시작

기한: 2주 (BOJ 연습최대기간)

목표: 10솔 (1등팀 솔브수)

서울 리저널에서는 24년부터 풀이 스케치를 제공한다. 참고할 예정

http://static.icpckorea.net/2024/regional/writeups.pdf

 

최종결산 - 10솔

 

0412

본 대회 때 풀었던 A, B, J, L을 밀었다. 별로 오래되지 않아서인지 대강 풀이의 결이 기억나서 편하게 밀었다. 다 미는 데 두 시간 안쪽으로 걸린 것 같다.

A는 뻔한 걸그냥 하면 된다. 대회 때도 시작 어리버리만 좀 타다 풀었던 것 같다.

B는 지금 보니 뻔한 그래프 모델링에 뻔한 유형이다. 각 간선이 양쪽 중 하나의 정점을 겹치지 않게 고르는 상황일 때 트리인 컴포넌트에서는 하나 빼고 다, 트리가 아니면 모든 정점을 고를 수 있다. 이분 매칭도 돈다는 얘기를 들었는데 아직도 왜인지 잘 모르겠다.

J는 풀이가 대강 기억나서 슥 풀었는데, 지금도 초면이면 무지성 그리디를 생각할 것 같다. 기억하던 것보다 구현이 쉬웠다.

L도 대강 기억나는 대로 풀었다.

 

본 대회 때는 여기까지 밀고 3시간 동안 아무것도 못했다. 

일단 C와 E를 출력했다.

 

0413

C를 풀어보려고 시도했다. 내 기억으로 커팅을 빡세게 해야 했던 문제고, 본 대회 때 F에 시간을 와락 박고 C에도 와락 박다 망했던 것 같다.일단 사분면마다 4개씩만 관리하면 된다는 건 기억에서 가져왔다. 어케어케 잘 관리한다 치고 (i,j)를 기준으로 쪼갤 때 답을 판별하는 방법을 생각해 봤다. 단순하게 하면 4^4*2000^2 = 1024000000 > 10억이기 때문에 안 될 것 같았고, 홀의 결혼 정리가 생각나서 사분면 - 수 이분 그래프를 만든 뒤 모든 사분면 조합 2^4가지에 대해 포함된 수의 개수를 세는 방법을 떠올렸다. 이러면 2^4*4*2000^2 = 256000000 ~ 2억5천 정도이니 돌 것 같았다.

 

짜서 냈더니 시간 초과를 받았다. 풀이를 까 보니 4^4*2000^2가 맞다고 한다. 엄

혹시나 해서 답 판별을 4^4로 바꿔도 시간 초과를 받았다. 아무래도 사분면마다 4개씩 뽑을 때 벡터 2*2000^2개를 쓴 게 병목인 것 같다. 에디토리얼을 읽어 보니 4개씩 뽑기를 이쁘고 상수 작게 하긴 한다. 흠.. 내일 짜 볼 예정

 

0415

중단

하려다가 아직 고민이 안 끝났으니 풀던 거라도 짜려 한다. QOJ에서 제출해야 해서 솔브드 기여 등등을 못 본다. 슬프다.

 

E는 컨벡스헐을 관리하며 대강 하면 될 것 같은데, 히스토그램 수평선이 바닥과 접하는 경우에 바닥에서도 뚫고 갈 수 있는? 그런 이상한 케이스가 있을까 무섭다. 나중에 짤 예정이다.

근무를 타다 F 풀이가 기억났다. 증명은 전혀 모르겠다. 그냥 찍맞인 것 같다. 이걸 어떻게 풀었나.. 하고 다른 팀 후기를 막 뒤져봤는데, 문제 특성상 모든 케이스를 로컬에서 검증할 수 있으니 다들 되겠지~ 마인드로 짜고 로컬에서 검증한 뒤 낸 것 같다. 풀이 스케치에 설명이 하나도 없어서 무슨 소린지 모르겠다. 내일 풀이 세션 영상을 봐야 할 것 같다.

C는 풀이에서 설명하는 이쁘고 상수 작게 4개 뽑기를 구현하면 풀린다. 

 

지금까지 6문제를 풀었고, 패널티 크지 않은 6솔까지 아챔을 갔다.

본 대회 때는 ABJL을 풀고 C, F에서 돌돌 말려있느라 다른 문제를 못 풀었다.

23년 셋을 돌 때는 그냥 본 대회 때 개못했었다는 생각이 들었는데, 24년도에 망한 이유는 조금 다른 것 같다. 23년 셋은 지금 돌면 그때보다 훨씬 잘 할 자신이 있는데, 24년 셋은 다시 돌아도 5솔 할 자신이 없다. 스코어보드상으로 C, F를 버리고 E, H를 잡는 선택은 정말 쉽지 않고, C/F를 대회 중에 풀어낼 자신도 없다.

24년 셋을 보니 의욕이 더 꺾인다. 25년 셋을 풀어 보고 앞으로 어떻게 할지 더 생각해봐야 할 것 같다.

 

일단 E, H, K를 풀어보고, 여유와 시간이 남는다면 EERTREE를 공부하거나 I를 풀어서 10문제를 채워 보려 한다.

 

0416
개인정비 내내 jungol.co.kr 탐방했다. 생각보다 나쁘지 않은 것 같다.

K가 문자 등장 횟수 최댓값인 줄 알고 냈더니 (당연히)틀렸다. 

 

0417

H는 로그제곱 아래로 줄이는 걸 도저히 모르겠다. 풀이 영상을 더 열심히 봐야 할 것 같다.

어제 냈던 무지성 K 풀이는 acabba같은 반례가 있다. 좀 더 생각해보니 26N 또는 세그를 이용한 NlogN 풀이가 떠올랐다. min 연산이 필요하지만 필요한 쿼리가 1..i 형태뿐이라 펜윅으로도 짤 수 있고, 26N보다 느리지 않을 것 같아서 펜윅 NlogN으로 풀었다. 풀이 스케치에서는 26 안 붙는 그냥 N 풀이를 설명하는 것 같은데 잘 모르겠다.

I는 될 것 같다는 확신이 강하게 들었고, 풀이 스케치에서도 같은 풀이를 설명하는 것 같다. 증명은 못 하겠는데 풀이 스케치에도 증명이 없다.. 

 

0418

오전에 GPT를 괴롭힌 끝에 H의 선형 풀이를 이해했다.

 

서브트리의 높이를 dep[a]와 같이 표시할 때, 두 서브트리를 합치는 시간복잡도가 O(min(dep[a], dep[b]))라면 전체 시간복잡도가 O(N)이라는 사실을 배웠다. hld처럼 깊이가 깊은 쪽으로 체인을 펼치면, 시간복잡도를 셀 때 각 노드는 한 번씩만 카운팅되게 때문이다. 풀이 스케치의 "각 부분트리에서 두 번째로 큰 깊이를 모두 더한 값은 (n − 1) − (트리의 깊이)" 문장이 이 뜻인 것 같다.

 

따라서 체인 분할을 한 뒤 각 서브트리마다 위험한 점 0, 1, 2, ... 개를 덮기 위한 최소 깊이를 관리하면, 적절한 처리를 통해 두 체인을 min(dep[a], dep[b])에 합칠 수 있으니 합치는 시간복잡도는 전체 O(N)이다. 두 체인을 합칠 때, 위험한 점을 X개 덮을 수 있는지 상수 시간에 확인할 수 있다. 정답은 최대 $\Sigma{k}$이니 전역에서 정답 변수 ans를 관리하고 합치는 매 과정에서 ans를 1 늘릴 수 있는지 확인하면 전체 $O(N + \Sigma{k})$에 문제를 풀 수 있다.

 

풀이가 좋은 문제라고 생각한다. 다만 센트 or 작큰 풀이가 너무 빨리 생각나고 해볼 만 해 보여서.. 대회였다면 로그제곱으로 어떻게든 뚫으려다가 말렸을 것 같다.

 

오전부터 하루종일 맞왜틀을 했다. 오후에 재원이형과 5시간 골드 많은 셋을 하나 돌았는데, 너무 못했다. 셋 다 돌고 한참 맞왜틀을 하다 또 GPT를 좀 괴롭히니 반례를 던져 줬다. 이러면안되는데

 

0425

주중에는 미뤄뒀던 다이아를 열심히 밀어서 레이팅을 올렸고, 한양대 내부 순위에서 두 명을 제쳤다.

E랑 I는 일주일 전과 상태가 똑같았다. I는 풀이가 될 것 같다는 확신이 있었지만 증명을 못 했고, E는 구현하기 쫄렸다.

 

I를 먼저 짰고, 사소한 실수를 고치니 맞았다. 풀이의 골자는 점을 y좌표에 따라 세 그룹 A : y = 9999, B : y = 0, C : y = -9999로 분리한 뒤 각각의 그룹을 x 오름차순으로 정렬하고 f(a,b,c) := A에서 앞 a개, B에서 앞 b개, C에서 앞 c개 남았을 때 최소 정사각형 개수 같은 DP를 돌리는 것이다. N = 100000인데 세제곱? 싶지만, f(|A|, |B|, |C|)를 계산하기 위해 방문하는 상태의 수는 O(N)개이므로 map dp를 돌리면 문제를 풀 수 있다.

여기서 상태의 수가 O(N)개라는 증명을 못 하고 있었는데, AC를 받고 좀 생각해보니 그냥 당연한 사실 같다. x가 가장 큰 점이 A / C에 있을 때는 분기가 없으니 무시하고, B의 b번째 점이 x가 가장 큰 점이려면 dp 전이 과정에 의해 a, c가 고정된다.

 

E 지문을 다시 읽어보니 simple polygon이라는 말이 있어서 상상했던 이상한 경우가 없으리라고 생각하고 E를 짰다. CCW를 헷갈리는 실수를 해서 좀 절었지만 생각했던 풀이를 그대로 짜니 맞았다.

 

후기

QOJ에서 24 서울 셋은 다른 서울 리저널 셋과 다르게 downvote가 몇 개 있는데, 그럴 만하다고 느꼈다. 아챔 컷이 사실상 C와 F 솔브 여부였는데, C와 F를 대회에서 만나면 긍정적인 인상을 받기 어려워 보인다. 셋을 다 알고 생각하면 E, K를 잡는 게 맞는 선택인데 이건 정말 쉽지 않다.. 잘은 모르지만 수상권도 eertree가 팀노트에 들어있는가 / H를 풀었는가 / E,K를 빨리 잡았는가 정도로 갈린 것 같다. 흠

본 대회 때 다른 문제는 거의 안 잡았던 것 같다. 풀이 큐가 비었으면 일단 모든 문제를 읽어보고 공유하는 작업이 중요한 것 같다. 무지성슼보따라가기에서 벗어나는 연습도 필요해 보인다.