2022 Sogang Programming Contest (Master) 후기

스코어보드

문제 난이도

 업솔빙을 다 할 때까지 후기를 쓰지 않으려 했고, 그렇게 업솔빙을 끝낸 지금 후기를 쓴다.

 

 대회 결과는 4등이다. F에서 말린 것을 풀지 못하여 H도 못 풀었고, 꽤나 아쉬움이 남았다. 대회 때 무슨 일이 있었는지와 풀이는 간략하게만 쓰도록 하겠다. 문제는 앞에서부터 풀었다.

 

 

A

 시작하자마자 A 지문을 건너뛰고 예제를 보고, 바로 사칙연산 식을 만들어서 코드를 제출하고 AC받았다.

 

B

 B는 그냥 빡구현 문제였기에, 열심히 코딩했다. fastio가 빠져서 1틀 적립. 

 

C

 조합론 기초 문제다. \(k\)개가 같은 경우, \(k!\)으로 나누어주기만 하면 된다.

 

D

 맨 처음에 한 쌍을 지울수만 있다면, 0과 1의 개수가 짝수인 한 모든 쌍을 지울 수 있다. 불가능한 경우에 -1이 아닌 0을 출력해서 1틀 적립.

 

E

 재밌는 문제였다. 마지막 정렬 쿼리 이전의 수들의 순서는 중요하지 않다. 이 이후에 들어오는 수들은 deque로 관리해주면 된다. 대회가 시작한 지 43분이 지난 시점에 AC를 받았다.

 

F

 대회 당시 레이지 세그를 짰는데, 시간 초과가 떴다. 1.2초라는 매우 수상한 시간제한과 N, Q 제한을 보고 다른 풀이를 떠올렸어야 했다. 완전히 내가 멍청해서 말린 것.

 업솔빙때는 쿼리를 뒤집고, union-find로 어떤 점에서 어디까지 구간이 합쳐졌는지를 관리했다. 쿼리를 뒤집었기 때문에, 이미 채워진 곳은 다시 볼 필요가 없기 때문이다.

 

G

 대회 때 아이디어를 떠올려서 풀 수 있었을 지는 모르겠다. 지름의 끝 점부터 시작하여, 이 지름에서 뻗어나가는 가장 긴 길이를 추가하는 식으로 진행하면 되는데, 이는 트리dp와 우선순위 큐를 적절히 사용하면 된다.

 

H

 [2, 0, 0, 2]는 N=4,M=4을 만족하는 수열이다. 편의상 이를 좋은 수열이라 하자. 대회 때는 좋은 수열을 반복하여 이어붙이는 것까지 떠올렸지만, 그 뒤에서 생각이 막혔다.

 \(M\mod  4\) 의 값에 따라 마지막 좋은 수열을 바꾸면 된다. 그리고 그 뒤에 \(4\)를 쭉 붙여주면, 이들은 쓰레기 값을 채우는 것과 같기 때문에, 조건을 만족하는 수열을 항상 만들 수 있게 된다.

 

 

 대충 풀이는 이렇고.. 아쉬움만 남은 대회가 되었다.

 

 

앞으로의 계획

 일단, 대회 때 제대로 못 한 핑계를 좀 대고 싶다. 퍼플에서 블루로 강등당한 이후로 자신감이 꺾였는데, icpc 리저널 본선이 끝나니 내 실력에 대한 자신감이 또 꺾였다. (그리고 지금은 더 심해졌다)

 또 다른 건, 요즘 몸 상태도 말이 아니다. 너무 피곤해서 하루에 16시간 정도를 내리 자는 날도 있다. 중요한 건 꺾이지 않는 마음이지만, 몸이 먼저 꺾이게 생겼다.

 

 어쨌든, 종강 전까지는 컨디션 관리나 할 생각이다. 낮에 시간이 남을 때 골랜디를 하고, 플3 정도 되는 문제도 가끔 풀 생각이다. 올해 안에 퍼플로 복귀하고, 3월 전까지 무조건 오렌지를 찍을 거다.