jay153의 PS 일지
SUAPC 2025 Winter Open Contest 본문
https://www.acmicpc.net/contest/view/1450
A
$\mathrm{min}(t_1,t_2)$를 구하는 문제였다.
B
전형적인 스택 문제라는 생각이 들었다. 검사하는 문자열도 "skeep"으로 5글자이기 때문에 매번 스택의 뒷 5글자가 "skeep"인지 검사를 해도 된다. 스택에 문자를 하나씩 집어넣고 "skeep"이 나온 경우에는 뒷 2글자를 추가적으로 보면서 "skeep"이 최대한 많이 나오도록 글자를 넣어주었다.
C
스코어 보드를 보고 J가 많이 풀렸길래 J로 가려고 했는데 J인 줄 알고 C를 먼저 풀었다. 문제를 보고 3분 만에 풀린 문제 치고는 너무 어렵다는 생각을 했지만 내가 부족해서 그렇다고 생각하고 풀기 시작했다. 문자열에 처음 J가 나올 때 빼고는 점프를 할 때 나온 A의 개수와 D의 개수가 주기적이라는 사실을 깨닫고 첫 점프에만 유의해서 코드를 짜려고 했다. 주기성을 잘 고려해서 코드를 짰다고 생각했고 제출을 하면서 내가 푼 게 C였음을 깨달았다. 제출 결과는 WA였고 J부터 풀고 다시 와서 풀기로 했다. J, L, F를 풀고 나서 코드를 다시 보니 $v[1]$이라고 써야 하는 부분에 $v[2]$라고 써서 틀린 것이었고 고쳤다.
D
문제를 훑어보면서 D를 봤을 때 전혀 감이 잡히지 않아 다른 문제들을 풀다가 스코어보드를 보니 반드시 풀어야 하는 문제라는 생각이 들어 풀기 시작했다. 조금 생각해보니 $D$를 기준으로 정렬하면 다익스트라 알고리즘에서 노드가 나오는 순서라는 것을 깨달았다. $D$를 기준으로 정렬하여 노드를 하나씩 뽑아준다. $D$의 값이 현재 노드$(i)$보다 큰 곳 중 간선이 있는 곳$(j)$에 대해서 $D_i$, $D_j$ 값을 바탕으로 $L$, $R$ 사이의 값 중 선택할 수 있는 경우의 수와 다음 노드의 값을 $D_j$로 만들 수 있는지를 판단하여 저장해 놓는다. 각 노드에 도달할 때마다 저장된 값을 바탕으로 경우의 수를 구해 곱해주어 답을 구했다.
E
40분을 남겨놓고 시작했으나 접근조차 못했다.
F
L을 풀고 스코어보드 보고 F로 왔다. 가로 세로의 길이가 $x$, $y$일 때 무조건 $x\leq y$가 되도록 놓는 것이 이득일 것 같았다. 대회 중이라서 엄밀한 증명은 하지 않고 냈다.
G
E, G, M 3개를 남겨놓고 G에 먼저 손을 대보았다. 강화를 하는 데 강화석이 몇 개가 들던 이를 금화 1개로 대체 가능하므로 강화를 하는 데 드는 금화 개수가 다르다면 금화가 적게 드는 것을 고르는 것이 이득이라는 것을 20분 정도 고민하고 깨달았다. 이를 깨닫고 각 쿼리에 대해 강화를 할 수 있는 최대 개수를 먼저 계산해놓고 이 개수에 도달 가능한지를 판별하는 문제로 바꾸어 풀 생각을 했는데, 예제에서 반례가 나왔다. $X$, $Y$만 보고는 최대 개수를 특정하기 힘들다는 것을 알게 되었고 그냥 병렬 이분탐색을 하면 될 것 같다는 생각이 들었다. $X$, $Y$에서 특정 개수를 강화하는 것이 가능한지는 펜윅 트리와 이분탐색을 활용하여 판별해 주면서 병렬 이분탐색을 하여 답을 구했다.
H
스코어보드를 보고 H로 왔다. 우선 모든 서로소 쌍은 1번 쿼리로 처리를 해주고 $gcd$가 1보다 큰 모든 쌍을 처리할 생각을 했다. 서로소 쌍을 처리하는 것부터 실수를 했는데 1 차이가 나는 수들은 모두 서로소이므로 $1$을 한 번 해주고 $3$부터 $(N-1)$까지 모든 수를 한 번씩 해주어야 한다고 생각했다. 서로소가 아닌 쌍을 처리하는 것도 실수를 했는데, 특정 소수의 배수인 것들끼리 모두 연결되어 있도록 하면 충분한데, 이를 합성수까지 해주다가 중복이 나오는 말도 안되는 답안으로 WA를 받았다. 서로소 쌍에 대해 연결해 주는 작업은 $N$이하의 홀수들에 대해서만 1번 쿼리를 해주어도 충분하고, 어떤 소수 $p$에 대해서 $p$의 배수 중 $p$를 제외하고 $N$이하인 것들만 2번 쿼리를 해주어도 충분하다는 것을 깨닫기까지 여러 번을 틀렸다.
I
C를 풀고 문제를 둘러보다가 I 풀이가 떠올라서 I를 풀기 시작했다. $p_i<i$라는 조건이 매우 강력한데, $l\leq i\leq r$인 $i$에 대해 $p_i\geq l$이면 $i$는 부모 노드와 연결되어 있으므로 셀 필요가 없다. 즉 문제가 $l\leq i\leq r$인 $i$ 중 $p_i<l$인 $i$의 개수를 세는 것으로 바뀌는데 이는 머지소트 트리로 해결했다.
J
C를 틀리고 스코어보드 보고 J로 왔다. $a_i$ 중 $b_j$ 이상인 것의 개수를 구하면 되는 문제였고 이분 탐색을 하여 답을 구했다.
K
I를 풀고 문제를 보던 중 이 문제가 정렬 + Knapsack으로 풀릴 것 같아 시작했다. 우선 가격 순으로 물건들을 정렬하면 앞에서 부터 물건을 담을 때 개수의 합이 $N$을 넘지 않으면 일부만 고르는 선택지가 없어진다. 일부만 사면 물건의 종류는 늘어나는데 뒤에 있는 물건을 살 바에는 앞에 있는 물건을 더 사는 게 가격적으로 이득이기 때문이다. 개수의 합이 $N$개가 될 때에만 일부 물건을 사는 것이 허용되기 때문에 이를 바탕으로 $O(M^2N)$ Knapsack dp를 짰다. 처음에 WA를 받아서 로직의 문제를 찾다가 단순 오버플로우 문제였음을 깨닫고 $\mathrm{LINF}$의 값을 $10^{16}$으로 고쳤다.
L
J를 풀고 스코어보드 보고 L로 왔다. "ANZ"가 나오면 안되는데, $N\geq 2$인 경우 A를 $N\times N$ 블록으로 3개, N을 $N\times N$ 블록으로 3개, Z를 $N\times N$블록으로 3개 배치하면 "ANZ"가 나올 수 없고 $N=1$인 경우에만 "ANZ"가 나오지 않도록 잘 배치해 주었다.
M
E의 솔브수가 0인 것을 보고 M으로 왔다. M을 보니 X가 작아 그래프 모델링을 하면 모든 쌍에서 최단거리를 구할 수 있겠다는 생각이 들었다. $5X$개의 정점을 가지는 그래프로 모델링할 생각을 했다. 각 학교별 노선 수가 $X$개이므로 각 노선들을 그래프의 정점으로 하고 같은 역에서 만나는 서로 다른 학교의 노선끼리 간선을 추가해 주는 것이다. 이를 바탕으로 $5X$개의 노드 사이의 최단거리를 BFS로 구해놓으면 하면 쿼리별로 $5\times 5$개의 노드 쌍 사이의 거리만 구하면 답이 나오게 된다.
