CONTEST
- HANDLE
- kolorVXL
- DATE
- 2026. 09. 08 · 23:35 KST
- RESULT
- 5솔브 · 110분 · 공동 140위
원래 오늘 라운드에 참가할 생각은 없었지만, 일어나보니 23시가 조금 넘었는데 오늘 Education Round가 있다고 해서 참가했습니다.
이 글은 가볍게 쓰는 거라 독자 분들이 이 대회의 문제를 알고 있다고 가정하고 작성했습니다. 추후 수정하여 내용을 보강할 수도 있습니다.
REFLECTION
A, B, C, E는 제 능력상 괜찮은 수준으로 풀었다고 생각합니다. 물론 이 과정에 개선할 점이 없진 않겠지만 우선순위가 낮을 것 같습니다.
D에 대해서 문제를 잘못 읽은 것도 문제지만, 문제를 잘못 읽은 것을 파악하고 다시 답을 찾고는 흥분하여 범위 검증을 제대로 하지 않고 문제를 해결하려 한 것이 패착이었습니다. 물론 이로 인해 최정상급 선수들과의 패널티는 벌어졌지만 패널티 문제가 크게 도드라지지는 않았던 것 같습니다.
F에 대해서는 생각이 많습니다. 너무 깊게 생각했고, 중간에 사이클의 모든 정점의 차수가 $2$여야 한다는 점도 잠시 고민해봤지만 제대로 써먹지 못했습니다. 모든 사이클을 다 돌아보면 무조건 터질 것이라고 성급한 가지치기를 했고, 사이클의 개수가 $2^{m-n+1}$개 이하일 것이라고는 아예 생각을 못했습니다. 가망이 없어 보이는 풀이여도 그게 어렵지 않다면 성급하게 가중치 $0$을 부여하기보다 가중치 $at - b$ 형식으로 부여해서 계속 말렸을 때 다시 고민할 수 있는 PS러가 되어야겠습니다.
별개로 Division 1에서 41등인데 전체에서 140등 남짓을 했습니다. 어느 정도는 피해의식일 수도 있으나 솔직히 상위 140명 중에 Division 2가 100명이라는 것이 제대로 된 수치라고는 절대 믿기지 않습니다. 제발 치팅 좀 그만했으면 좋겠고, 치팅도 치팅이지만 정말 체스나 바둑과 같이 AI에게 밀리고 있다는 생각이 들어서 아쉽습니다. 앞으로 CP 플랫폼의 경쟁력 중 하나는 AI 치팅을 얼마나 잘 막을 수 있느냐도 포함이 될 것 같습니다.
0:03
A 치고 거슬리는 조건 분기여서 기분이 좋지 않았습니다.
0:09
B라는 것을 생각하며 최대한 쉽게 접근했습니다. 제한을 유심히 읽어보니 바로 답이 나왔습니다.
0:16
C는 쉽지는 않았지만 어느 정도 접근법이 고정되어 있습니다. $x \oplus y \leq x + y$이고, 실제로 $x + y$가 되려면 비트가 겹쳐서 사라지는 경우가 없으면 된다고 접근했습니다.
0:27
D는 처음에 비용의 합을 최소화하는 줄 알았습니다. 이후 비용의 최대가 $3$ 이하라는 것을 관찰했으나, DP 범위를 너무 작게 잡아서 틀렸습니다.
0:36
D는 불가능한 경우를 제외하고 항상 비용이 $3$ 이하임을 관찰하고, 이를 토대로 $[-4, 4]$에서만 움직일 수 있게 하고 DP로 풀었습니다.
0:45
E를 읽어봤을 때 00, 01, 10, 11의 개수만 세고 결정해주면 된다고 생각했습니다. 빠르게 atcoder::fenwicktree를 불러왔습니다.
0:54
E를 구현하다 막혔지만, 바로 이분탐색이라는 방법을 생각하고 맞았습니다.
1:00
F를 읽어봤는데 $m \leq n + 9$라는 조건이 돋보입니다. 우선 그래프를 Connected graph + Cycle로 분리해야 함은 관찰했습니다.
1:10
편의상 $c = m - n + 1$이라고 하겠습니다. $O(c2^cn), O(cn^2)$등을 열심히 고안했습니다.
1:20
우선 스패닝 트리를 구한 후 남은 $c$개의 간선을 가지고 비트 DP를 하는 것을 고안했습니다.
1:30
그런데 쉽지 않았습니다. DFS Tree로 한정했음에도 불구하고 Back edge가 담당하는 구간이 겹치는 경우를 해결하지 못했습니다.
1:40
스패닝 트리를 구한 후 남은 $c$개 간선마다 하나를 Cycle에 무조건 포함된다고 보는 풀이도 생각했습니다.
1:50
그러나 아무리 생각해도 결정적인 풀이가 안 나와서 포기했습니다.
내 제출 기록 6개
- AMonocarp's ContestAC1솔브 · 2분 · 287위 → 278위
- BMonocarp and ProjectsAC2솔브 · 8분 · 293위 → 58위
- CMaximize XOR, Minimize OperationsAC3솔브 · 19분 · 70위 → 23위
- DSigns of Prefix SumsWA
- DSigns of Prefix SumsAC4솔브 · 60분 · 79위 → 50위
- ECyclic BalanceAC5솔브 · 110분 · 65위 → 22위