이번에 충남대에서 외부 참가가 가능한 ps 대회가 열린다고 해서 참가하러 갔다. ICPC 팀인 Kokiri is cute로 대회를 치러 갔다.
팀원은 다음과 같다.
- 장근영(azberjibiou): 애드혹을 잘 푼다. 저점이 높은 편이다.
- 이온조(Onjo): 국밥 문제들을 잘 푼다.
- 오태인(octane): 기하 고슈이다. 구현을 잘한다.
충남대 대회에는 서울대 초고슈들이 오지 않기 때문에 1등을 하면 좋지 않을까 생각했다.
과거 3년 충남대 대회들을 보니 다이아 문제가 2~3개씩은 나와서 재미있는 대회가 될 것 같다고 생각했다.
여기에 스코어보드가 있다.
여기에서 특정 시점의 스코어보드를 구경할 수 있다. (챗지피티 딸깍으로 만들었다)
대회 타임라인
골드 이하를 열심히 밀었다. WA를 단 하나도 받지 않아서 상쾌한 출발이었다.
카이스트에서 참가한 다른 팀인 스피드런도 런이다 팀과 페널티 10 차이로 간당간당하게 이기고 있었다.
A, B, C, D, E, G, H, I, K AC (~0:21)
이때쯤에 F가 스코어보드에 풀리기 시작했다. 큰수를 진법 변환 하는 문제라서 파이썬을 쓰면 편한데, 파이썬을 온조 밖에 쓸 줄 모른다. 그래서 온조가 현재 잡고 있는 N번을 다 풀고 F번을 밀기로 했다. 태인이는 M번에 폴라드 로를 쓰면 된다고 말하면서 팀노트에서 열심히 폴라드 로를 베끼고 있었다. 나는 스코어보드에서 풀리는 문제인 L, J를 풀었다.
L번은 트리와 쿼리 문제로, 관상학적으로 무서워보였다. 하지만 유니언 파인드로 최적화한 나이브로 시간복잡도가 보장된다는 것을 깨닫고 빠르게 풀었다.
J번은 정수론이 들어간 쿼리 문제로, 역시 관상학적으로 무서워보였다. 하지만 쿼리를 prefix 쿼리 2개로 변경하고 단순하게 스위핑을 하면 쉽게 풀렸다. 이 문제 역시 빠르게 풀었다.
이때쯤에 경희대 팀인 cpp = competitive python programming 팀이 솔브 차이로 앞서고 있었다. 하지만 우리가 페널티 관리는 더 잘한 것 같아서, 적당한 페이스로 문제만 잘 풀어주면 이 팀은 이길 수 있을 것이라고 생각했다.
L AC (0:29), J AC (0:41)
이제 내가 풀 문제가 F번 밖에 없어서, 내가 C++로 bigint를 구현해서 F번을 풀기로 했다. 온조가 N번을 빠르게 풀고 나면 F번을 파이썬으로 병렬로 풀기로 했다. 각자 긴 시간 동안 구현을 마친 후, N M F번에서 AC를 받았다. (온조가 M번을 푼 시점에 내가 구현을 거의 다 마쳐서 그냥 내가 F번을 풀었다)
M AC (0:47), N AC (0:57), F AC(1:01)
1시간만에 올솔을 해서 1등을 확정짓고 남은 2시간을 딩가딩가 놀았다.
대회 후기
각 문제들의 지문이 깔끔하게 잘 서술되어 있는 것, 특별한 이슈가 없었던 것은 좋은 것 같다. L번과 M번 문제가 좋았던 것 같다.
M번의 정해를 보니 폴라드 로를 사용하지 않았던 것 같은데, 테스트케이스를 10만개 정도 줬으면 폴라드 로를 막을 수 있었을 것 같아서 아쉬웠다.
예전보다 셋이 쉬워져서 조금 아쉬웠다. 쉬운 셋으로는 잘하는 팀들을 변별하기 쉽지 않다. (다들 스피드솔브를 잘하는 것 같다. 1등을 못할까봐 조금 쫄렸다) 하지만 교내 대회라는 것을 생각해보면 적당한 난이도 커브라는 생각이 들기도 한다. 외부인 참가를 받지 않았으면 예쁜 스코어보드가 나왔을 것이라고 생각한다.
그리고 투스텝 문제가 나온다고 해서 조금 기대했는데, 그냥 구현하는 문제가 나와서 아쉬웠다. 요즘 지피티 돌리면 문제를 잘 깎아주는 것 같은데, 조금 더 재미있는 투스텝 문제가 나왔으면 재미있었을 것 같다는 생각이 있다.
전체적으로 잘 만들어진 ICPC 셋의 초반 1시간을 도는 느낌이었다.
내년에도 충남대 대회가 열리면 또 치러 와야겠다.