대회 도중에 많이 고민했는데 못 풀었거나 관심이 생겨서 꼭 해결하고자 하는 문제들의 경우 에디토리얼을 보고 공부하였다. 본인 기준으로 수준이 너무 높다고 생각하여 도움이 되지 않을 것이라 판단한 문제들 혹은 그냥(?) 풀기 귀찮은 문제들은 대회 종료 후 별도로 공부하지 않았다. 업솔빙 관련 글도 올리고 싶은 경우에만 올릴듯.
C. Tsundoku (300 pt)
처음에 greedy 문제인줄 알고 삽질하다가 반례를 하나 발견하고나서 포기했던 문제이다. 풀이법은 구간합(prefix sum)과 탐색이다. a를 A의 구간합 배열, b도 B의 구간합 배열으로 정의하고 아래 방법으로 구한다.
a0 = 0
aN = A1 + A2 + ··· + AN = aN-1 + AN
그렇다면 우리는 문제의 답을 "ai + bj ≤ K를 만족하는 최대의 i + j 값" 으로 생각할 수 있다. 이제, 조건을 만족하는 (i, j) 쌍을 어떻게 찾을 것인가? 완전 탐색은 시간 복잡도가 O(NM) 이므로 TLE가 날 것이다. 이렇게 시도해보자. i가 0일 때 bj ≤ K - ai 조건에 맞춰서 최대의 j 값을 찾는 상황을 가정하면, j = M, M - 1, M - 2, ... 순으로 탐색할 것이며 이때 탐색된 j 값을 best라고 하자. K는 조건 상 반드시 양수이며, 구간합 배열 a와 b는 단조 증가한다. 그렇다면, i가 1일때 최대의 j 값은 반드시 best 미만일 것이다. 이렇게 완전 탐색을 피해갈 수 있으며 시간복잡도 O(N + M) 내로 정답을 구할 수 있다. i와 j의 경우를 바꿔서 생각해도 동일하다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
long long apsum[200001] = {0}, bpsum[200001] = {0};
for(int i = 1; i <= n; i++) {
cin >> apsum[i];
apsum[i] += apsum[i - 1];
}
for(int i = 1; i <= m; i++) {
cin >> bpsum[i];
bpsum[i] += bpsum[i - 1];
}
long long ans = -1e9, j = m;
for(int i = 0; i <= n; i++) {
if(apsum[i] > k) {
break;
}
while(bpsum[j] > k - apsum[i]) {
j--;
}
ans = max(ans, i + j);
}
cout << ans << '\n';
return 0;
}
D. Sum of Divisors (400 pt)
임의의 수 X의 약수의 개수를 O(√X) 내로 구할 수 있지만 정답을 구하기 위해 필요한 연산을 일일이 수행한다면 TLE가 발생한다. 그런데 이 문제는 각 수의 약수의 개수를 구하지 않고도 정답을 구할 수 있다! 문제가 요구하는 수식의 값을 구하는 의사코드는 에디토리얼에 나온 것처럼 아래와 같다.
ans = 0
for i = 1, ..., N:
for j = 1, ..., N:
if i % j == 0 then ans += i
print ans
그런데 위 코드는 모든 (i, j) 쌍에 대해 고려하기 때문에 결국 2, 3번째 줄을 바꿔서 아래와 같은 코드를 실행시켜도 같은 결과를 도출한다.
ans = 0
for j = 1, ..., N:
for i = 1, ..., N:
if i % j == 0 then ans += i
print ans
위 코드의 동작을 관찰했을 때, "N 이하 모든 j의 배수들의 합을 g(j)으로 정의하면, j = 1, 2, ..., N일 때 모든 g(j)의 합"을 구하는 것으로 이 문제를 다시 정의 해볼 수 있다. g(X)를 구하기 위해서 Y = ⌊N/X⌋ 으로 정의하면, g(X) = X + 2X + ··· + YX = (1 + 2 + ··· + Y)X = Y(Y + 1)X/2 로 표현할 수 있으며, 결국 정답을 O(N) 내로 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
long long ans = 0;
for(int i = 1; i <= n; i++) {
long long y = floor(n / i);
ans += (i * y * (y + 1)) / 2;
}
cout << ans << '\n';
return 0;
}
고등학교를 졸업한 이후로 수학을 하지 않았고 지금까지도 수학적 사고를 전혀 한 적이 없다. 그래서 문제 조건 속에서 수학적 사실을 도출하여 수식을 변형하는 작업이 필요하다거나 수학 지식이 필요한 경우 너무 풀기가 힘들고 자꾸 이상한 방향으로 생각이 빠진다. 계속 문제들을 열심히 풀어서 수학 문제의 경우는 모르는 개념을 하나씩 알아나가고 풀이 방향에 대한 감각을 익혀야 겠다. 물론 업솔빙도 열심히 하고.