제2회 IDTcup

이틀동안 치뤄진 온라인 대회다. 예전에 한 건데 블로그에 글 쓰기 귀찮아서 뒹굴거리다 이제서야 올림

A. N!!!...! mod P

$(N!\ mod\ P)!\ mod\ P\ ...$의 값을 구하는 것으로 착각했다가 뒤늦게 문제를 다시 읽고 풀었다... $n!\ mod\ P$에서 $n \geq P$라면 $n!$은 $P$의 배수라서 0이란 걸 생각한 뒤엔 케이스 분류만 잘 해주면 된다.

한 가지 놓치기 쉬운 점은 $K=2$이고 $N=12$일 때인데, 윌슨의 정리를 쓰거나 N! mod P (2)의 코드를 복붙해야 한다.

H. 전자식 계산기 (Calculator)

자고 일어나 보니 A 다음으로 가장 많이 풀린 문제길래 시도해봤다. 뭔가 어려워 보이길래 걱정했는데 그런 거 없고 그냥 라빈카프 해싱 쓰는 문자열 문제였다. 다만 FFT로 푸신 분도 계시다고 한다... 그저 빛;

두 해시가 같은지 확인하는 부분이 까다로울 수 있는데, $a=b$이면 $a-b-1=M-1\ (mod\ M)$이니 $\lfloor{\frac{a-b-1}{M-1}}\rfloor$을 해주면 쉽게 구현할 수 있다. 실수하기 쉬우니 채점기를 직접 만들고 로컬에서 확인해보는 게 좋은 것 같다.

대회 후반엔 심심해서 출력이 최대한 작게 나오도록 해서 제출해 봤다.

C. 착한 말 나쁜 말

다른 건 풀만한 문제가 안 보여서 이걸로 도피했는데 대회 끝나고 보니 세 번째로 어려운 문제; 체감 상으로도 내가 푼 문제 중 가장 어려웠던 것 같다.

풀이는 잘 기억이 안 나는데 크게 어렵진 않았던 것 같다. 문제는 시간이었는데, 가중치가 두 종류여서 $O(N)$ 다익스트라를 짜고 무수한 시간초과를 맛보다가 set을 유니온 파인드로 바꿔준 뒤에야 간신히 통과했다.

시간복잡도 자체는 괜찮은 것 같지만 뚫었다는 느낌이 좀 있다. 문제와 큰 관련은 없는 얘기지만 은근히 set을 유니온 파인드로 바꿔서 최적화하는 상황이 자주 생기는 것 같다.

I. XOR과 집합과 트리와 쿼리

문제를 탁 켰는데 수식이 가득해 보이길래 수학십덕문제인가? 하고 바로 껐다가, 스코어보드에서 많이 풀리길래 다시 켜서 봤다.

기억이 흐릿하지만 의외로 풀이 정리하는 데까지 30분이 안 걸렸었다. 아마 증명 안 하고 Proof by AC를 했더니 쉬웠던 것 같음.

별 의미는 없지만 대회 끝나갈 때 심심해서 커팅을 하고 제출해봤다.

G. 이메이미의 수쿼 노트

설마 레이지 PST를 짜는 문제겠어? 하고 고민해 봤는데 PST를 안 쓰는 방법이 떠오르질 않았다. 결국 메모리랑 시간이 맞기를 기도하면서 짜고 냈다. 풀이 자체는 어렵지 않았지만 대회 중엔 많이 헷갈렸다.

대회 끝나고 찾아보니 PST 없이도 풀 수 있다고 한다. 근데 그냥 PST 쓰는 게 이득인듯

여기까지 푼 뒤 은광을 계속 트라이했다. 10틀을 하고도 결국 못 푼 채로 대회가 끝났는데 많이 아쉬웠다.

E. 은광

풀이 떠올리는데 한참 뇌절하고 대회 중에 10틀하다 못 풀고 대회 끝나고 나서도 20틀하고 진짜 뇌절의 끝을 달렸다. 이게 왜 이렇게 빨리 많이 풀렸는지 모르겠음.

기타

실력에 비해 순위가 좀 높았는데 그냥 사람들이 한두 문제만 풀고 탈주하거나 느긋하게 쳐서 이런 것 같다. 아니었으면 20~30등쯤 했을 듯. 이전 대회인 전시관이 너무 무시무시했던 것도 탈주에 좀 기여하지 않았을까?

B. 함수의 맛은 뭔가 링컷으로 적당히 해주면 될 것 같던데 링컷을 모른다. 대회 중에 고인물 분들이 한두시간만에 슥슥 풀어대시는 걸 보고 너무 무서웠다..

D. 트리와 K번째 지름은 글을 쓰는 지금까지도 풀지 않았다. 왜지?