2025 숭고한 참가 후기
블로그를 쓰기로 시작해놓고, PPS개발 때문에 (N년 동안) 미뤄놨다가 후기글 이벤트를 한다는 소식을 듣고 후다닥 작성합니다.
서론
제가 참가한 숭고한 Div1 난이도는 1~3명으로 구성된 팀으로 참가하는 대회였지만, 이번 대회는 애초에 수상할 생각이 없었기도 했고 (제대로 해도 3등도 못 할 걸 알았음) 재밌게 대회 치고 오자는 생각 때문에 눈치 보지 말고 키보드를 맘대로 잡을 수 있게 혼자 참가했습니다.
그리고 원래 문제를 풀 때도 빨리 정확하게 짜는 실력이 매우 부족하기 때문에 (팀 내 페널티 담당) 속도전으로도 이길 수 없다는 것을 알았기에 재미를 챙기기 위해 모든 제출을 프리즈 이후에 제출하기로 결정했습니다.
팀명은 PPS 불법 홍보(?)를 위해 project-ps.com으로 하려 했으나, 제출 폼 정규식에서 .을 허용하지 않아서 project-ps_com으로 참가했습니다.
대회 결과
결과부터 이야기하자면 꼴지를 했습니다. 페널티 핑계를 대기도 애매한게 애초에 솔브 수도 많이 밀리기 때문에 그냥 실력으로 꼴지를 했습니다.
대회 바로 전날에 SCPC를 치고 왔는데 SCPC도 망치고 온 걸로 보아 실력이 많이 떨어졌음을 알 수 있습니다.
N년 전부터 은퇴해야겠다를 반복하며 살았는데 알고리즘으로 원하는 모든 목표를 최근에 모두 이뤘기 때문에 이제 진짜 은퇴하고 개발을 더 열심히 하려고 합니다. (그래도 취미로는 조금씩 이어갈 예정입니다 ㅋㅋ)
문제 풀이
저는 어차피 프리즈 이후에 제출하기로 결정했으니 문제를 빨리 풀 이유가 없었습니다. 따라서 난생 처음으로 투어리스트 전략을 실행해보게 됐습니다.
투어리스트 전략이란 존재하는 모든 문제를 읽어본 뒤 구현 난이도가 가장 낮은 문제부터 차례대로 푸는 전략입니다.
실제 대회에서 해본 거는 처음인데, 제출 속도에 관련된 페널티가 없으니 확실히 긴장이 덜 됐습니다. 원래도 긴장을 많이 하는 편은 아니긴 하지만, 코드포스와 같이 속도전에서는 긴장보다 마음이 급해서 실수하는 경우가 꽤 많았는데, 차분히 문제를 풀 수 있었던게 좋았습니다.
대회가 시작하고 A부터 K까지 차례대로 천천히 읽어봤습니다. 이때는 풀이에 집중하기 보다는, 문제를 특징화 시켜서 외우고 대략적인 풀이 방향성이 보이는지 안 보이는지 정도만 생각하기로 했습니다. 문제 수가 11문제로 꽤 많은 편이라, 문제를 어느 정도는 외워야지 어떤 순서대로 풀어야 할 지를 정할 수 있을 것 같았습니다.
1회독은 대략 10~15분 정도 걸렸던 것 같았습니다. 1회독을 하면서 생각했던 것들은 다음과 같습니다.
- A: 그래프에서 특정 형태의 케이스워크를 해야만 할 것 같았습니다.
- B: (제한을 제대로 확인하지 못 하고) 격자에서 유니온 파인드 후 판별하는 문제라고 생각했습니다. 다만, 좌표가 격자 좌표가 아닌 점 좌표로 주어지기도 하고 구현 자체가 귀찮은 문제라고 판단했습니다.
- C: 매칭의 향기가 진하게 났지만 제한을 보고 어려운 문제라고 판단했습니다.
- D: 간단한 컨스트럭티브 (인줄 알았습니다….) 문제라고 판단했습니다.
- E: 아무런 생각도 안 들었습니다. 경로를 가지고 무언가 해야 된다고 판단했습니다. (ETT + SEG, HLD, CENTROID) 등 키워드는 있었으나 아예 감도 안 왔습니다.
- F: 보자마자 그리디를 알아챘습니다.
- G: 보자마자 모스의 향기가 났습니다. 근데 Disjoint Set Roll Back과 Disjoint Set이 쿼리당 $O(log(N))$ 이므로 결국 모스 쿼리당 $O(\sqrt{N}log(N))$ 이 되어야 한다고 생각했고, 풀 것이 없을 때 시도해 보는 것이 좋겠다고 판단했습니다.
- H: (문제를 잘못 읽어서) 보자마자 주어진 a, b범위에서 bitcount가 가장 적은 수를 찾으면 되는 줄 알았습니다.
- I: 결국 마지막 한 수를 남기는 문제로 치환되므로 trie를 사용해서 xor 최댓값을 구하면 된다고 판단했습니다.
- J: 지문부터 말이 안 돼서 대충 보고 넘겼습니다. 유일하게 제대로 읽지 않은 문제입니다.
- K: $A_i$의 범위를 보자마자 제곱 꼴의 디피임을 알 수 있었고, 세제곱 풀이는 금방 나왔으나 최적화를 잘 하면 되겠다는 판단을 했습니다.
1회독을 마치고 가장 쉬웠던 F를 잡았습니다.
간단한 문제였던 만큼, 빠르게 풀고 넘겼습니다. (대략 5분 정도 걸렸던 것 같습니다.)
그 다음으로는 간단할 것 같았던 D를 잡았습니다.
홀수의 경우 $\lfloor N/2 \rfloor \times (\lfloor N/2 \rfloor + 1)$ 인 두 사이클을 구성하는게 최적임을 알 수 있었고 짝수가 문제였습니다.
결국 두 수의 gcd가 1이 아니라면 중복되는 사이클을 모두 활용하지 못하고 중복되기 때문에 gcd가 1이 아닌 가장 가까운 두 수를 찾아서 사이클을 구성하도록 했습니다. (이 문제도 5분 정도 걸렸습니다.)
프리즈가 되려면 한참 남았기 때문에 일단은 넘겼습니다. (이후 대회 중간에 나정휘팀을 포함해 다른 많은 팀들이 빨간 불을 켜고 있는 것을 보고 간단하지 않은 문제임을 꺠달았습니다.)
그 다음으로는 H를 잡았습니다. 빠르게 코드를 짜고 확인해본 결과 마지막 예제에서 15가 나와야 하는데 10이 나왔습니다. 이후 풀이가 틀렸음을 깨닫고 일단 넘어갔습니다.
그 다음으로는 I를 잡았습니다. 문제를 보자마자 풀이를 떠올렸기 때문에 막힘 없이 진행할 수 있었습니다. 이후 예제를 출력해보니까 3이 나와야 하는데 1이 나왔습니다.
trie구현에도 자신 있었고 풀이에도 자신이 있었어서 풀이 자체가 틀렸다고 판단하고 손으로 문제를 풀어봤습니다. 결과론적으로는 A와 B를 바꿔서 적었다는 사실을 꺠달았습니다. 이후 제대로 된 풀이를 작성했으나 여전히 1이 나오고 있었습니다.
도저히 이해가 안 돼서 다른 예제들을 많이 넣어보고 최대 최소 등을 계속 바꿔가며 확인했는데 왜인지 계속 1 아니면 큰 값을 뱉었습니다.
구현하는데는 10분도 안 걸렸지만 디버깅을 한참 하다가 풀이에는 잘못이 없으니 일단 H를 잡기로 결정했습니다.
원래 생각했던 H는 10001이라는 수가 있으면 한 경기 후 1000이 될 줄 알았으나 1001이 된다는게 함정이었습니다. 결국 1이 처음 등장한 이후 존재하는 0의 개수가 가장 적은 것이 답이라는 것을 깨닫고 어렵지 않은 구현 끝에 풀어낼 수 있었습니다.
딱 이 시점이 1시간 조금 안 되게 지난 시점이었고, A와 E가 많이 풀리기에 A를 잡기로 결정했습니다.
A는 결국 노드 4개를 완전그래프로 만들면 되는 간단한 문제였고 주어진 그래프가 트리이기 때문에 답은 항상 3으로 고정이었습니다. 케이스워크를 해본 결과 두 가지 경우밖에 존재하지 않기 때문에 (한 줄로 이어지거나, 한 노드에 세 개가 모두 달린 경우) 두 가지 케이스를 찾아 답을 출력하도록 만들었습니다. (이 문제도 5분 정도 걸린 것 같습니다.)
이후 E를 고민하다가 도저히 모르겠어서 I부터 디버깅을 하기로 했습니다.
결국 트라이가 잘못됐다는 것을 깨닫고 트라이에 삽입과 쿼리를 날려본 결과 매우 이상한 답이 나왔습니다. (7을 하나 넣고 3과 xor 최소? 최대? 가 되는 값을 찾는 쿼리를 날렸는데, 답은 4가 나와야 하지만 계속 1이 나오고 있었습니다.) 트라이를 오랜만에 짰지만, 워낙 간단한 템플릿을 사용하고 있었기에, 쿼리가 문제인가 하고 디버깅을 찍고 있던 와중에 한 가지를 발견했습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
int trie[303030 * 31][2];
int nn() {
static int cnt = 1;
return cnt++;
}
void ins(ll x) {
int p = 1;
for (ll i = 31; i--; ) {
int nxt = !!(x & (1LL << i));
if (!trie[p][nxt]) trie[p][nxt] = nn();
p = trie[p][nxt];
}
}
기본적으로 0은 쓰레기 노드 (null 노드), 1은 루트, 2이상부터는 삽입된 노드로 사용하고 있었습니다. 근데 특정 출력에서 모든 노드의 번호가 1번으로 나오고 있었습니다.
nn함수 (new node)에서 ++cnt를 뱉었어야 했는데, cnt++을 뱉고있어서 생겼던 문제였습니다. 고치니까 바로 정상적으로 동작하는 걸 보고 넘어갔습니다.
사소한 실수였지만 이를 발견하지 못한 내 자신을 자책하며 다음 풀이를 이어 나갔습니다.
A다음으로 많이 풀린 E를 보며 E풀이에 대한 고민을 했습니다. 이때 스코어보드에서는 14분 정도에 퍼솔이 나온 문제이므로 어려운 문제는 아닐거라고 생각은 했지만, 자꾸 A부터 B까지 경로를 생각하니 막막했습니다. (이게 패착인 것 같습니다.)
이때 남은 시간은 한 시간 반 정도 남았지만, B, C, J는 어려운 문제이므로 결국 D혹은 E혹은 K혹은 G 넷 중 하나를 먼저 풀어야 한다고 생각했습니다.
근데 D는 많은 사람들이 틀려주고 있었기 떄문에 내가 생각하지 못 하는 어려운 관찰 하나가 있을 거라고 판단했고, G는 유파 롤백을 어떻게 했는지 기억이 가물가물하고 로그가 붙은 모스가 돌 지 확신이 없어서 건너 뛰었고, K는 세제곱에서 허둥대고 있었기 때문에 그나마 많이 풀린 E를 풀어야 그 다음 어떤 문제든 풀 수 있겠다 생각해서 E에 올인을 하기로 결정했습니다.
E를 풀고있다가 결국 스코어보드가 프리즈 됐고, A, F, H, I는 바로 맞았습니다를 받았습니다. D는 제출은 했지만 예상대로 틀렸습니다를 받았습니다.
E를 잡고 처음엔 리루팅 + 세그로 업데이트 같은 느낌으로 접근하려고 했으나 말도 안 된다는 것을 꺠닫고 이 풀이를 조금 발전시키다 보니까 바로 스몰투라지가 보였습니다. 하지만 다른 문제를 제쳐두고 14분만에 스몰투라지를 짠 건 아닐거다 라는 생각을 조금 하다가 도저히 모르겠어서 결국 스몰투라지를 짜기로 결정했습니다. 하지만 스몰투라지에서 서브트리를 부모로 합쳐주는 과정에서 특수한 업데이트가 필요했고, 이를 어거지로 구현하다가 어딘가에서 실수를 하는 바람에 1시간 30분동안 디버깅만 하다가 대회가 종료됐습니다.
결과론적으론 간단한 그래프 탐색 문제였지만, 왜 생각을 못 했는지 아쉬움만 남았습니다.
E관찰을 할 수 있었더라면 E를 풀고 K도 충분히 풀만해 보였습니다. (실제 정해에서 사용하는 풀이를 냈지만, 복잡도 계산을 잘못 해서 안 짰었는데 그게 정해였습니다.) K도 풀었다면 남은 시간에 D도 풀지 않았을까 싶습니다.
하지만 그렇게 해도 7솔브에 페널티가 많으므로 4등을 하지 않았을까 싶습니다.
여러모로 아쉬움이 많이 남는 대회였지만, 그래도 투어리스트 전략을 실제로 해본 첫 번째 대회라 재미는 있었습니다.
대회 열어준 모든 분들에게 감사의 말씀 올리면서 다음에도 불러주시면, 도파민 전용 같은 전략 실천하러 가보겠습니다. 그때는 조금 더 잘 풀어보는 걸로…