SUAPC 2022 Winter 검수 후기

검수 경험도 없던 내가 어쩌다 보니 엄청난 대회에 검수자로 참여하게 되었다..

다른 검수자분들에 비하면 실력이 부족해서 적어도 1인분은 하려고 그만큼 시간을 많이 투자한 것 같다.

문제는 여기에서 확인할 수 있고, 나는 B, H, M을 제외한 나머지 문제들을 검수했다.

*풀이에 대한 스포가 있을 수 있으니 주의해서 보자.

 

 

A. 튜터-튜티 관계의 수

 

평범한 문제를 조금 꼬아놓았다. 지문에 대한 코멘트를 했었는데, 후원사 측의 요청으로 자연스럽게 해결되었다.

 

 

C. 카카오뷰 큐레이팅 효율성 분석

 

노솔 방지용 문제의 역할을 훌륭히 해냈다.

 

 

D. Y

 

트리의 지름 문제의 풀이를 확장시키고, 이때 생기는 몇 가지 까다로운 케이스들을 처리해주니 풀렸다. 풀면서 골드 맞나 싶긴 했는데 역시나 플레를 가버렸다.

 

 

E. 놀이기구에 진심인 편

 

적절히 스위핑해주면 수쿼 문제로 변환되는데, 여기서 세그 트리와 PST로 겁나 뇌절했다. 나중에 풀이를 까보니 제곱근 분할법에 오프셋을 접목시키는 멋진 아이디어로 풀리더라. 그런데 수쿼가 요구하는 연산이 간단해서 고인물들의 흑마법이라는 SIMD로 뚫릴 수 있지 않을까 걱정됐다. 그래서 문제도 검수할 겸해서 심드를 열심히 배우고 코드도 작성해보았다. 진짜 내 실력 안에서 극한으로 최적화한 코드가 최악의 케이스에서 3초 이상이 걸리는 것을 보고 안심할 수 있었지만, 뚫릴거라 생각했었기 때문에 조금은 아쉬웠다. 여담으로 SIMD 개꿀잼이다.

 

 

F. mod와 쿼리

 

코포에서 비슷한 문제를 만난 적이 있어서 푸는 것은 수월했다. 그런데 데이터가 부족해서 내가 짠 야매 풀이가 통과하거나 느려야 하는 코드가 매우 빠르게 동작하는 것을 확인할 수 있었고, 각각의 코드를 저격하는 데이터 추가를 요청했다. 기본적으로 mod 연산에 루트질까지 해야 하다 보니 연산량이 상당히 많아서, 어떤 자료구조를 사용하고 버킷 크기를 얼마로 잡느냐에 따라 수행 시간이 크게 달라졌다. 출제자분이 처음에는 느린 풀이까지 다 통과시키기를 원하셨는데, 고심하시더니 시간 제한을 빡세게 조정하셨다. 아마 파이썬으로는 못 풀 듯.

 

 

G. 도로 정보

 

누적합 느낌의 좋은 문제인데.. 완전히 새로운 유형은 아니다.

 

 

I. 이 멋진 수열에 쿼리를!

 

대놓고 코노스바 컨셉의 문제인데, 놀랍게도 출제자분은 코노스바를 보지 않으셨다고 한다. (나도 아직 안 봤다) 이젠 봤다

문제가 마음에 들어서 검수자에 이름을 올리고 싶었지만, 풀이를 찾기가 쉽지 않았다. 나는 마법을 맞은 구간이 갖는 값이 정답에 어떻게 기여하는지를 관찰했고, 풀이를 정리해보니 구간 곱 업데이트, 노드 추가 쿼리, 전체 합 쿼리를 구현하면 문제를 해결할 수 있었다. 이는 스플레이 트리로 어떻게든 짤 수 있어서 정말 열심히 코드를 작성했고 다행히 원트에 맞았다. 내 풀이 기준 난이도는 D1인데, 실제로는 3*3 행렬을 금광 세그처럼 관리하는 더 쉬운? 풀이가 있어서 D4를 받았다.

 

대충 E, I 풀이 과정

 

 

J. 일이 너무 많아...

 

포함 배제를 비트마스킹으로 해결하는 흔한 유형이다. 그런데 오버플로우 관리가 좀 까다롭다. 생각했던 것보다 티어가 낮게 달리는 중

 

 

K. 올바른 괄호

 

무지성 세그 트리 가능한 문자열의 형태만 잘 생각하면 풀 수 있다.

 

 

L. 팰린드롬 게임

 

대충 DP를 돌려보니 규칙이 나와서 신기했다. 벌캠으로도 되나? 싶어서 연습할 겸 코드를 짜봤다.