ps 갤러리에서 대회를 연다고 해서 참여해보았다.
나보다 잘하시는 분들이 꽤 많이 참가하셨는데, 운이 좋아서 이길 수 있었다. 아마 G를 빨리 푼게 크게 작용했던 것 같다. 또한 운 좋게 추첨에 당첨되어 버거를 하나 더 받을 수 있었다.
전반적인 문제 퀄리티는 정말 좋다. 전형적인 문제가 거의 없고, 쉬운 문제와 어려운 문제 모두 재미있다. 특히, 전반적으로 구현이 매우 짧고 깔끔하다.
간단한 문제 풀이
- A: 제한이 작아서 무슨 방법을 써도 다 풀린다. 나의 경우, 앞에서부터 보면서 PS4나 PS5가 나올때마다 숫자를 제거하는 방법으로 $O(N)$에 풀었다.
- B: $i$라운드만에 $K$명을 뽑을 수 있는지 판정하려면 주어진 모든 문자열들의 크기 $i$의 prefix들만 고려할 때 $K$번 이하로 등장한 것이 있는지만 판별하면 된다. 제한이 작아서 모든 $i$에 대해 다 해봐도 된다. 답을 출력해야 하는데, 각 문자에 대해 그 문자에 대해 지는 문자를 출력하면 된다.
- C: 자르는 직선을 최대한 기울여서 답을 계산해보고, $F$ 배열을 뒤집은 뒤 한번 더 계산해서 둘 중 최솟값을 출력하면 된다. 좀 귀찮다.
- D: $1, (\text{1, 7을 제외한 N 이하의 모든 홀수}), 7, 2, (\text{2, 8을 제외한 N 이하의 모든 짝수}), 8$ 배열을 cyclic shift하고 출력하는 것을 $N$번 반복하면 된다. 홀수와 짝수가 인접한 경우는 합이 9이고, 그렇지 않은 경우는 합이 2를 넘는 짝수이므로 올바른 해이다.
- E: 답을 고정하면 한 $i$에 대해 히터가 있을 수 있는 위치의 범위를 알 수 있다. 이러한 범위들의 교집합이 있으면 그 답이 가능한 것이고, 이를 이용해 이분탐색으로 풀 수 있다.
- F: 초기 상태에서 $1$ 이상 $N^2$미만의 각 $i$에 대해 $i$와 $i+1$은 같은 행이나 같은 열에 있어야 한다. 만약 같은 행(열)에 있다면, 최종 상태에서 두 행(열)은 인접하다. 이를 통해 어떤 행이 어떤 행과 인접해야하는지를 알 수 있고,(열도 마찬가지) 최종 상태에서 행과 열의 배치가 특정된다. 해가 있으면 그 해의 행이나 열의 순서를 reverse한 것도 해가 되므로, 총 4가지 경우에 대해서만 필요한 연산의 횟수를 계산해 최솟값을 출력하면 된다.
- G: 첫 번째 실행에서는 주어진 격자그래프를 G 문자가 있는 곳에서부터 maximal한 가로 선분, 세로 선분으로 쪼개고, 모든 세로 선분을 구성하는 정점에 돌을 놓는다. 두 번째 실행에서는 선분을 따라가다가 벽이 나오면 방향을 바꾸고, 다른 선분이 나오면 그 선분을 바꿔 타 가는 방법을 사용하면 된다.
- H: $l$을 $N$부터 $1$까지 줄여가며 $r$에 대한 조건을 찾을 것이다. $l$ 앞쪽에 있는 피돌이들의 경우 $l$과 $r$의 크기 조건을 구할 수 있다. $l$ 뒤쪽에 있는 피돌이들의 경우 $r$이 구간 $N-l+1$개에 동시에 포함되어 있어야 한다는 조건이 나오는데, 교집합이 있는지 없는지 판단하는 것은 세그먼트 트리를 사용해 할 수 있다.
타임라인
대회 1시간 반쯤 전 잠깐 잤는데, 운 좋게 대회 2분전에 일어났다.
0:00 ~ 0:07
순위상이 없고, 퍼솔상만 있는 대회라 시작 전부터 C를 잡기로 생각했었다. 그러나 C는 그림을 보니 빨리 짤 수 없겠다는 생각이 들었고, B로 넘어왔다. 풀이가 금방 나왔고 짜서 맞았으나 퍼솔은 아쉽게 실패했다.
맞은 문제: B
0:07 ~ 0:08
A가 구현이 쉬워보여서 풀어도 딱히 퍼솔에 영향을 안 줄 것이라 판단해서 풀었다.
맞은 문제: A, B
0:08 ~ 0:36
A를 맞을때쯤 E가 풀려있는 것을 봤고, E까지는 크게 어렵지 않을 것이라 생각하여 투스텝인 G를 읽었다. 처음엔 어떻게 풀지 막막했는데, + 모양에 대해 어떻게 풀까 생각해보니 바로 풀이가 나왔다. break를 continue로 써서 한번 틀렸다.
맞은 문제: A, B, G
0:36 ~ 1:09
G를 푼 시점에서 노려볼만한 퍼솔이 F, H, I가 있었는데, I는 좀 어려운 것 같아서 H를 잡았다. 중간에 풀이가 터져서 약간 고쳤는데, 한 번에 맞은 것은 운이 굉장히 좋았다고 생각한다.
맞은 문제: A, B, G, H
1:09 ~ 1:42
이제 퍼솔을 노려보는 것은 사실상 불가능했고, 그래서 쉬워보이는 순서인 D, E, C 순서대로 풀었다. C는 사소한 구현 실수로 한번 틀렸었다.
맞은 문제: A, B, C, D, E, G, H
1:42 ~ 2:05
F를 풀었다. 비슷한 다른 문제랑 햇갈려서 풀이를 떠올리는데 좀 오래 걸렸다.
맞은 문제: A, B, C, D, E, F, G, H
2:05 ~
I를 30분쯤 고민해보다가, 더 이상 머리가 안 돌아가서 이 글을 썼다.