2026 겨울학교 1차 모의고사 후기

337점으로 1등했다. ^ㅗ^

25737 ARC 183 E 24438 34581 로 구성된 셋이었다.

0:00 ~ 0:36 (0 0 0 0)

1번부터 4번까지 문제를 읽었다. 1번은 왕자구 문제, 2번은 이상한 문제, 3번은 적당한 인터랙티브 문제, 4번은 조건 잘 분석하면 쉬워지는 문제처럼 보였다. 1번부터 건드려봤는데, 생각보다 복잡하고 섭테에서부터 구간 cht 같은 걸 써야 해서 어려운 문제라고 판단하고 2번으로 갔다. 2번에서는 인접한 두 개만 바꿀 수 있는 것이 아니라 아무 두 개나 바꿀 수 있는 것으로 문제를 잘못 읽어서 짧은 풀이를 냈고, 당연히 0점을 받았다. 문제를 다시 읽고 잘못 읽었음을 깨닫고 슬펐다.

0:36 ~ 1:09 (0 0 100 0)

2번을 다시 보니 잘 모르겠어서 3번으로 넘어갔다. 3번은 문자를 하나씩 추가하면서 이분탐색으로 위치를 정할 수 있을 것 같았다. 그런데 문자의 위치가 최악으로 주어지는 경우 $N \log N$번의 쿼리를 날려야 한다는 것을 알게 되었고, 잘하면 5000번을 넘길 수도 있을 것 같아 shuffle로 문자의 순서를 적당히 섞고 진행했다. 두 번 틀리고 바로 맞았다.

1:09 ~ 1:20 (0 0 100 30)

앞선 시간 동안 4번에서 적당한 필요 충분 조건을 구해 놓았고, 구현해서 맞았다. 대충 이분그래프를 구성한 뒤 각 컴포넌트에서 둘 중 더 작은쪽을 선택하면 된다.

1:20 ~ 1:35 (0 0 100 64)

뒤쪽 섭테들은 간선을 하나 끊고 다시 연결해서 답의 최솟값/최댓값을 구해야 한다. 잘 최적화하면 $O(N)$ 정도에 풀릴 것 같았지만 귀찮아서 일단 $O(N^2)$을 짜서 맞았다. 각 간선을 직접 끊어보고 최소/최대가 되는 곳에 연결하는 방식으로 하면 된다.

1:35 ~ 2:33 (37 0 100 64)

4번의 $O(N)$ 풀이는 구현하기가 너무 귀찮아서 2번을 보다가 잘 모르겠어서 일단 1번의 섭테를 긁기로 했다. $N, Q$가 작은 경우와 성게인 경우를 풀었다.

2:33 ~ 3:29 (37 0 100 100)

1번은 풀 만큼 풀었다고 생각하고 남은 시간에는 2, 4번을 풀기로 했다. 그런데 2번을 너무 모르겠어서 4번의 구현하기 귀찮은 풀테를 짰다. 각 이분 그래프를 BCC로 묶어서 단절선을 끊는 경우와 단절선이 아닌 간선을 끊는 경우로 나눠서 구현하면 된다. 제출했더니 $k=0, 2$는 맞고 $k=1$은 틀리길래 몇 가지 예외 처리를 추가했더니 맞았다.

3:29 ~ 3:51 (37 27 100 100)

일단 2번에서 간단하게 풀 수 있는 기본 섭테들을 구현했다. $M \le 10$인 경우를 구현했는데 실수가 있어서 몇 번 틀렸다.

3:51 ~ 4:36(37 51 100 100)

적당히 구현하면 될 것 같은 $O(M^2)$ 풀이를 하나 찾아서 구현했다. 각 수가 갈 수 있는 범위를 구간으로 나타내면 모든 두 구간은 서로 포함하거나 서로소이다. 따라서 좁은 구간부터 보면서 놓을 수 있는 위치에 수를 적당히 배열하고 구간이 막히면 막으면 된다. 사실 맞는지도 잘 모르겠고 구현하기도 귀찮아서 안 짜고 있었는데, 이거라도 해야 될 것 같아서 구현하고 디버깅해서 맞았다.

4:36 ~ 4:47 (37 100 100 100)

사실 $O(M^2)$이 풀리면 세그로 적당히 최적화할 수 있는데, 안 될 수도 있을 것 같아서 일단 제곱을 짠 거였다. 시간이 24분밖에 안 남아서 엄청 서둘러서 합, 최소, 최대를 모두 저장하는 세그를 짰고 제곱인 부분을 최적화해서 제출했다. 다행히 바로 맞았다. ㅎㅎ

 

4:47 ~ 5:00 (37 100 100 100)

1번을 시간 안에 점수를 더 못 받을 것 같아서 놀았다.