PS 재활하기 with AtCoder

PS 재활의 필요성을 체감했습니다. KOI 2차를 매우 심하게 망쳤기 때문입니다. 3달 정도 PS를 안 했더니, 골드 중위 문제도 못 푸는 수준의 실력이 되었더라고요. 문제는 AtCoder에서 찾아 풀기로 했습니다. 문제 양도 상당하고, 전형적인 테크닉을 많이 배울 수 있으며, 무엇보다 모든 문제의 풀이가 공개되어 있기 때문입니다. 여름방학 동안 푼 AtCoder 문제들을 정리해 보았습니다. 괄호 안의 수는 Kenkoooo에서 볼 수 있는 난이도입니다.

ABC170D. Not Divisible (1033)

수열 $A$ 내에서 약수가 자신뿐인 수의 개수를 구하는 문제입니다. $A$에 중복 원소가 있다면 서로가 서로의 약수가 되므로 중복 원소를 모두 배제합니다. 그 다음 각 $A_i$에 대해 $A_j=nA_i\le10^6~(n\in\N)$을 만족하는 $A_j$를 모두 찾습니다. 찾은 $A_j$들은 답의 개수에 포함될 수 없습니다. 이 작업을 모든 $A_i$에 대해 반복해 주면 됩니다. $A_i$의 중복이 없고 그 최댓값 $M=10^6$이므로, 조화수열의 합에 의해 시간 복잡도는 $O(M\log{}M)$이 됩니다.

ABC163D. Sum of Large Numbers (960)

$10^{100}$ 때문에 귀찮아 보이지만, 사실 $1$, $2$, ..., $N$에서 뽑은 수의 개수와 합 쌍이 몇 종류인지 묻는 문제와 같습니다. $x$개의 수를 뽑는다고 할 때 가능한 최솟값과 최댓값은 $O(1)$에 쉽게 구할 수 있고, 이들 사이의 수를 모두 만들 수 있음 또한 자명합니다. 이것을 $K$ 이상 $N+1$ 이하의 모든 $x$에 대해 실행하면 $O(N-K)=O(N)$에 문제를 해결할 수 있습니다. 더욱 최적화하면 전체 문제를 $O(1)$에도 해결할 수 있지만, $N$의 범위가 그렇게까지 크지 않으므로 필요는 없습니다.

ABC178E. Dist Max (1054)

$N$개의 점 중 맨해튼 거리가 가장 긴 두 점 사이의 맨해튼 거리를 구하는 문제입니다. 일반성을 잃지 않고 $x_i\ge{}x_j$일 때, 맨해튼 거리는 $\max((x_i+y_i)-(x_j+y_j),(x_i-y_i)-(x_j-y_j))$입니다. 따라서 각 점에 대해 x좌표와 y좌표의 합과 차를 각각 저장해 주고, 합의 최댓값과 최솟값 차이 $D_{add}$, 차의 최댓값과 최솟값 차이 $D_{sub}$ 중 더 큰 것을 출력하면 됩니다.

ABC165C. Many Requirements (1136)

중복조합 $_{10}\textrm{H}_{10}$의 값은 $92\,378$입니다. 따라서 가능한 모든 수열 $A$를 한 번씩 조사해 볼 수 있습니다. 모든 $A$에 대해 점수를 계산하고 최댓값을 출력하면, $O(_N\textrm{H}_{M}Q)$의 시간 복잡도에 문제를 해결할 수 있습니다.

ABC132D. Blue and Red Balls (1167)

파란 공을 모으기 위해 $i$번의 시행이 필요하다는 것은 연속된 파란 공의 묶음이 $i$개라는 것과 같습니다. 따라서 파란 공을 $i$개의 묶음으로 나눈 뒤 다음 중 하나를 선택하면 됩니다.

• $i-1$개의 빨간 공 묶음을 파란 공 묶음 사이에 배치
• $i$개의 빨간 공 묶음을 각 파란 공 묶음의 왼쪽에 배치
• $i$개의 빨간 공 묶음을 각 빨간 공 묶음의 오른쪽에 배치
• $i+1$개의 빨간 공 묶음을 파란 공 묶음 사이와 양 옆에 배치

따라서 경우의 수는 $\binom{K-1}{i-1}\times(\binom{N-K-1}{i-2}+2\binom{N-K-1}{i-1}+\binom{N-K-1}{i})$가 됩니다. $N$과 $K$가 각각 최대 $2\,000$이므로, $O(N^2)$에 조합을 구하는 DP를 이용하여 쉽게 해결할 수 있습니다. $N=K$일 때의 예외 처리에만 신경 쓰면서 풀어 줍시다.

ABC467A. Obesity (76)

주어진 식 그대로 계산하면 됩니다. 부동소수점 오차가 없도록 실수 나눗셈 대신 정수 곱셈을 활용해 줍시다.

ABC467B. Keep the Change (39)

$S_i$가 keep일 때만 $B_i-A_i$를 결과에 더하여 출력하면 됩니다.

ABC045C. Many Formula (1089)

$N=|S|$, $S_i$, $S_{i+1}$, ..., $S_j$로 이루어진 정수를 $X_{ij}$라고 합시다. 인덱스는 1-based입니다. 그러면 모든 식에서 $X_{ij}$가 등장하는 횟수는 $2^{\min(0,i-2)+\min(0,N-j-1)}$입니다. 따라서 $\displaystyle \sum_{1\le{}i\le{}j\le{}N}2^{\max(0,i-2)+\max(0,N-j-1)}X_{ij}$가 문제의 답이 됩니다.

ABC464E. Fill-Rect Query (1075)

2차원 배열 $A$를 만들고, 각 쿼리마다 $A_{R_i,C_i}=i$ 대입을 합니다. 이제 오른쪽 아래에서 왼쪽 위로 가는 누적 max를 적용해 주면, 각 칸에 적용되는 마지막 쿼리의 번호를 알 수 있습니다. 번호에 맞추어 문자를 출력해 줍시다. 시간 복잡도는 $O(HW+Q)$입니다.

ABC445D. Reconstruct Chocolate (1102)

$1$부터 $N$까지의 정수가 하나씩 저장된 두 배열 $A$, $B$를 만듭니다. $A$는 각 원소 $i$에 대해 $h_i$가 큰 것부터 순서대로 정렬되어 있습니다. $B$는 각 원소 $i$에 대해 $w_i$가 큰 것부터 순서대로 정렬되어 있습니다. 이제 주어진 분할 방식에 의해 다음 중 적어도 하나가 성립합니다.

• $h_{A_1}=H$
• $w_{B_1}=W$

전자가 참이라면 $A$부터, 후자가 참이라면 $B$부터 탐색을 진행합니다. 여기에서는 전자가 참이라고 가정합시다. 그러면 $h_{A_i}=H$가 성립하는 가장 큰 $i$까지 왼쪽부터 차례대로 놓습니다. 남은 열의 개수는 $W'$입니다. 그러면 $B$로 탐색 대상을 바꾸어, $w_{B_i}=W'$이 성립하는 가장 큰 $i$까지 위부터 차례대로 놓습니다. 물론 이전에 이미 놓은 조각은 우선적으로 지나칩니다. 남은 행의 개수는 $H'$입니다. $A$로 탐색 대상을 다시 바꿉니다. 이러한 작업을 모든 조각을 사용할 때까지 진행하면, 전처리를 제외하고 시간 복잡도 $O(N)$에 문제를 해결할 수 있습니다. 전처리를 포함하면 $O(N\log{}N)$입니다.

ABC468E. Sum of Average (1038)

길이가 $x$인 부분 수열에 대해, 그 평균은 합을 $x$로 나눈 것입니다. 따라서 길이가 $x$인 모든 부분 수열에 대해 그 합의 총합을 먼저 구해 봅시다. 길이가 $x$일 때 $y=\min(x,N-x+1)$을 정의합니다. 그러면 각 $A_i$가 총합에 등장하는 횟수는 $1,2,\cdots,y-1,y,\cdots,y,y-1,\cdots,2,1$입니다. 누적 합을 잘 이용하면 모든 $x$에 대한 부분 수열의 합의 총합 $S_1,S_2,\cdots,S_N$을 $O(N)$에 구할 수 있습니다. 따라서 구하는 값은 $\displaystyle\sum_{i=1}^{N}\frac{S_i}{i}$이고, 각 $\dfrac{S_i}{i}$마다 모듈러 곱셈 역원을 취해 더해 주면 됩니다.

ABC145D. Knight (1009)

$(1,2)$ 이동을 $a$번, $(2,1)$ 이동을 $b$번 해야 한다고 하면, $a=\dfrac{2Y-X}{3}$, $b=\dfrac{2X-Y}{3}$입니다. 이때 $a$와 $b$ 중 정수가 아니거나 $0$보다 작은 것이 있다면 답은 $0$, 그렇지 않으면 답은 $\dfrac{(a+b)!}{a!b!}$입니다.

ABC102C. Linear Approximation (1089)

ARC100의 첫 번째 문제와 같은 문제입니다.

$B_i=A_i-i$를 정의합시다. 그러면 구하는 값은 $\displaystyle\sum_{i=1}^N|B_i-b|$의 최솟값이고, 이것을 최소로 하는 정수 $b$는 수열 $B$의 중앙값임이 잘 알려져 있습니다. 따라서 $b$를 그 값으로 놓고 계산해 주면 됩니다. 시간 복잡도는 중앙값 계산을 위해 정렬을 수행하므로 $O(N\log{}N)$입니다.

ABC125C. GCD on Blackboard (1197)

$A_i$를 $\gcd(A_1,\cdots,A_{i-1},A_{i+1},\cdots,A_N)$으로 바꾼다면, 이것은 $A_i$를 제거하는 것과 동일합니다. 따라서 원소 하나를 제거했을 때 GCD의 최댓값을 구하면 됩니다. 이는 양쪽 방향에서 누적 GCD를 계산하는 방법으로 쉽게 구할 수 있습니다. 시간 복잡도는 $O(N)$입니다.

ABC077C. Snuke Festival (1096)

ARC084의 첫 번째 문제와 같은 문제입니다.

먼저 각 부분을 크기 순으로 정렬하여 순서를 다시 매깁니다. 이제 상부를 고려하지 않고, 중부와 하부만으로 제단을 만들 수 있다고 합시다. 이때 각 중부에 대하여 만들 수 있는 제단의 수는 이분 탐색으로 쉽게 알 수 있습니다. $i$번째 중부와 임의의 하부로 만들 수 있는 제단의 수를 $X_i$라고 합시다.

이제 $i$번째 상부보다 큰 최소 번호의 중부를 $j$번째 중부라고 합시다. 그러면 $i$번째 상부로 만들 수 있는 제단의 수는 $X_j+X_{j+1}+\cdots+X_N$입니다. 이 값은 역방향 누적 합으로 쉽게 구할 수 있으므로, 그 합을 구해주면 시간 복잡도 $O(N\log{}N)$으로 전체 문제를 해결할 수 있습니다.

ABC046D. AtCoDeer and Rock-Paper (1256)

ARC062의 두 번째 문제와 같은 문제입니다.

아래 제시한 문제는 원래 문제와 동치입니다.

• 길이 $N$의 문자열 $s$가 주어집니다. 각 인덱스 $i$에 대해, 부여된 점수는 $s_i$가 g일 경우 $1$, p일 경우 $0$입니다.
• 각 인덱스마다 g나 p를 선택할 수 있습니다. g를 선택하면 부여된 점수에서 $1$을 뺀 점수를 얻고, p를 선택하면 부여된 점수를 그대로 얻습니다.
• 모든 인덱스 $i$에 대해 다음이 성립해야 합니다: $1$번 인덱스부터 $i$번 인덱스까지, g를 선택한 횟수는 p를 선택한 횟수 이상이다.
• 얻을 수 있는 최대 점수를 출력하세요.

g는 적어도 $\left\lfloor\dfrac{N+1}{2}\right\rfloor$번 선택해야 하므로, 부여된 점수의 합에서 이 값을 빼면 정답이 됩니다. 시간 복잡도는 $O(N)$입니다.

ABC048C. Boxes and Candies (1164)

ARC064의 첫 번째 문제와 같은 문제입니다.

$a_1>x$라면 $a_1$을 $x$까지 줄여 주어야 함은 자명합니다. 이제 그 다음을 봅시다. $a_1+a_2$를 $x$ 이하로 줄이기 위해서는 $a_1$을 줄이거나 $a_2$를 줄일 수 있습니다. 그런데 $a_2$를 줄이면 $a_2+a_3$도 함께 줄어들기 때문에 $a_2$를 줄이는 것이 반드시 더 유리합니다. 이를 $a_N$까지 반복해 주면 시간 복잡도 $O(N)$에 전체 문제를 해결할 수 있습니다.

ABC054. One-stroke Path (1244)

$N\le8$이므로, 브루트 포스가 충분히 가능합니다. 완전 그래프에서 가능한 경로는 $(N-1)!$개인데, 이 $(N-1)!$개의 경로를 전부 확인하면서 거치는 모든 간선이 주어진 그래프에 있는지 확인하면 됩니다. 시간복잡도는 $O((N-1)!\times{}N)=O(N!)$입니다.