제 2회 소프트콘 후기

소프트콘 할 때는 항상 다른 일이 있는 상태로 도서관에 있게 되더라...

최근 친 대회중에 가장 돌돌 말린 것 같아서 간단하게 후기를 쓰기로 했다.

눈을 준 건 ABCDE. 그 중 ABCD를 풀었고 등수는 13등이다. 도서관에서 굳이 서브태스크까지 긁고 싶지는 않아서 더 건드리진 않았다.

A. 스승님 찾기

(n,m) = (0,0)인 경우 답은 0이다.

gcd(n,m) = 1인 경우 정의에 따라 1번만에 갈 수 있다.

gcd(n,m) != 1인 경우 (0,0) -> (n-1,1) -> (n,m)으로 2번만에 갈 수 있다.

B. 명상 방해꾼

그냥 brute force + prefix sum...이라기보단 모든 방해꾼을 다 더한 놈을 가지고 다니면 된다.

지문 독해를 잘못해서 쫄았다. 교내경시의 트라우마가 스멀스멀

C. 상자 열기

트라우마 #1.

N = 3일 때를 보고 잘못 추측해서 맨 처음에 답이 N-1인 줄 알았다.

한 번 틀리고 난 뒤에는 \(\frac{2}{3}N\)근처일 줄 알았다.

도저히 최소 횟수 자체가 감이 잡히질 않았다. 이렇게 틀린 선발고사의 apple이 떠올랐다. 잘못된 최적해에 꽂혀서 다 말아먹는...

하지만 답이 linear 근처라면 채점하는 데도 \(O(N^2)\)이다. 이 생각을 가지고 답이 루트 아니면 로그라는 생각을 했다. 루트는 너무 비현실적이어서 로그를 붙잡았고, 결국 정해와 동일한 풀이를 생각해냈다.

맞기까지는 5틀이 필요했다.

D. 국제 소 줄서기 사진 콘테스트

트라우마 #2.

수열과 쿼리 0을 31WA한 이래로 뭔가 쿼리 문제에서 자료구조 insertion - deletion이 있는 문제 구현을 꺼리게 되었다.

멘탈을 꽉 붙잡고 std::set + 음수 idx 예외처리를 했고, 1WA만에 맞을 수 있었다. 구현 실수도 goto문을 잘못 사용해서 나온 것.

E. 순간이동 발판

트라우마 #3.

문제 자체는 어렵지 않아보였다. 다익스트라 각을 쉽게 잡아냈다.

하지만 사이클 간의 교점을 찾는데 무려 확장유클리드가 필요해보였다. 난 그런 거 못 짜는데... 심지어 확장유클리드 이외에도 예외처리가 너무 더러워보여서 던졌다.

하지만 에디토리얼을 보니 확장유클리드 없이도 \(O(NK^2)\)으로 짜면 되더라. 부들부들...

여담으로 확장유클리드 트라우마는 KOI 엘리베이터에서 비롯된 건데, 이 문제의 풀이를 보고 나서 엘리베이터의 \(O(M^3 + M^2 \sqrt{N})\)짜리 솔루션을 생각해낼 수 있었고 한 방에 AC까지 받았다. Yeah!