한 달 돌아보기 (2024-01-23 ~ 2024-02-19)

푼 문제들이 그렇게까지 흥미롭지도 않고 뭐해서 한 달이나 쌓게 되었다.

그래도 나름 채점 현황을 보니 백준에서 평균 하루에 하나는 풀었는지라 많이 모였다.

 

BOJ #10979 가넷이나 버는게 낫지 않아요? (P4)

 

시간상 2등으로 도착하게 되면서, COST는 최대를 챙겨야 하는 문제

다익스트라를 잘 돌리면 된다!

각 N개의 정점에 대해서 (걸리는 시간, 가넷의 수)를 고려하여 제일 나은 2개의 결과를 저장한다.

 

BOJ #1785 팀 사모예드의 신작 (P3)

 

적당히 재귀를 돌리면 충분히 잘 돌아간다.

즉, SOLVE(N, K)에 대해서 2, 3, 4, 5배짜리 지폐를 만든 뒤에 SOLVE(N / i, K - 1) + N % i의 최솟값 구하기

이때 중복해서 (N, K)에 들어가는 것은 map으로 잘 처리를 해준다.

실제로 랜덤하게 테스트해보면 1e5 이상 방문하는 경우가 없는데, 확실한 증명은 애매;

 

BOJ #1209 단조수열 만들기 (P4)

 

일단 귀찮으니 단조수열 B는 증가수열일 때만 고려하자. (감소일 때에도 똑같이 할 수 있다.)

claim) B에 들어갈 값들은 모두 A에 존재한다

pf) 처음으로 A에 없는 숫자인 B[i]에 대해 A[x] < B[i] < A[y]일 때, A[x] 혹은 A[y]로 바꾸는게 무조건 이득이다.

 

따라서 DP를 굴리는데, DP[i][j] = (i번째 숫자가 j일 때의 |A1 - B1| + ... + |Ai - Bi|의 최솟값)

O(N^2)으로 가능하다.

 

BOJ #12766 지사 배정 (D5)

 

우선 사실상 거리는 본부와 지사까지의 거리만이 중요하다!

따라서 dist[i] = (i번 지사에서 본부까지의 거리) + (본부에서 i번 지사까지의 거리) 라고 하자.

 

이제 dist에 대해서 정렬하자. (즉, i < j라면 dist[i] < dist[j])

당연하게도 제일 거리가 가까운 b개 외의 지사들은 모두 버려도 된다.

S(i)를 i번 지사가 들어가 있는 프로젝트의 크기라고 가정한다면, i < j일 때, S(i) > S(j)가 성립하게 된다.

dp[i][j] = (i개의 프로젝트에 대해 j개의 지사가 배정되었을 때, 최소 비용)이라고 정의하자.

단순하게 dp를 돌리면 O(s * b^2)이 된다. (각 dp[i][j]에 대해, [j + 1, j + sz]를 다음 프로젝트에 배정해보기)

 

이때 [j + 1, j + sz]를 배정할 때, 이 프로젝트는 기존의 i개 프로젝트보다 크기가 더 작아야 한다.

따라서 sz <= j / i가 성립하고, 위의 복잡도보다 짧은 O(s * blgb)가 된다.

 

BOJ #10905 Actual visible points (P2)

 

문제에서 주어지는 S와 조금 다르게 S를 정의하자

S[X] = {(x1, x2, ... xn) | 1 <= x1 <= ... <= xn = X, 각 x는 자연수}라고 하자.

우선 S[X]의 크기는 H(i, N - 1) = C(i + N - 2, N - 1)이다.

다만, 단순히 S값들의 합만 구한다면, 원점에서 보았을 때 가려지는 점들이 있어서 안된다.

 

sol1) O(M*X^(1/3)*sqrt(X)) (약수개수 = X^1/3라 가정)

cnt[X] = (S[X]에 속하지만, S[1], S[2], ... S[X - 1]에 의해 가려지지 않는 점의 수)라고 하자

그렇다면 cnt[X] = |S[X]| - sum(cnt[Y]) (단, Y는 X의 약수)

 

문제에서 주어진 S는 Xi중 하나라도의 약수가 되는 모든 d에 대해서 cnt[d]를 더하는 방식으로 구할 수 있다.

따라서 모든 d를 구해주고, 또 이 각각의 d에 대해 약수를 모두 구해서 cnt[d]를 구한 뒤 더해주면 된다.

약수의 개수를 대충 X^(1/3)이라 생각하면, 대략 M * X^(1/3)에 대해 모든 약수를 구해야 해서 위와 같은 복잡도

 

sol2) O(Xlg(X) + Msqrt(X))

가만보면 모든 cnt 값을 미리 구해두고 그냥 더하는게 더 싸게 먹힐 것 같다.

즉, for(int i = 1; i < MAXX; i++) cnt[i] = (cnt[i] + C(i + N - 2, N - 1)로 cnt[i] 를 구한 뒤,

for(int j = i * 2; j < MAXX; j += i) cnt[j] -= cnt[i]를 통해서 i가 약수인 모든 j에서 cnt[i]만큼을 빼주면 된다.

이렇게 해서 cnt를 모두 구하고 X의 약수가 되는 모든 d에 대해 합을 구해주면 된다.

 

sol3) O(Xlg(X))

위에 cnt 값을 구하는 과정을 잘 보면, j = X인 순간이 존재하는 경우에만 cnt[i]가 답에 더해지게 된다.

따라서 chk[i]를 만들어서, 모든 X에 대해 미리 chk[X] = 1 처리를 해주고, chk[i] |= chk[j]를 하자.

그 다음 맨 마지막에 cnt[i] * chk[i]의 합을 더하면, 딱 필요한 애들만 더해져서 답이 된다.

 

BOJ #12926 쉽게 제한된 메모리 (P2)

 

물론 내가 이미 PBS라는 개념을 알아서 그렇게 느끼는 것일수도 있지만,

문제를 풀다보면 자연스럽게 PBS에 도달하게 되는 것 같아서 좋다고 느꼈다.

 

각 쿼리는 이분탐색으로 답을 구할 수 있다. O(Q * lg(MOD) * N) 

어떤 mid에 대해서 X[i] <= mid인 경우의 수(=cnt[mid])가 q보다 큰지 작은지 확인하면 되기 때문이다.

7초에 희망을 걸고 제출해보면 시간이 부족하다.

 

그러면 적당히 자연스럽게 굳이 X를 모두 구하는 O(N)짜리 과정을 이렇게 여러번 반복해야하나 싶어진다.

동시에 이분탐색을 돌릴 수도 있을 것 같다는 생각...

L[Q]와 R[Q]를 관리하면 된다. 

q[i] < q[j]라면, 당연히 cnt[i] <= cnt[j]임을 이용하여,

어떤 X[k]에 대해, mid 값 중에서 lower_bound에 1을 더해두고, 마지막에 누적합 하듯이 cnt를 구할 수 있다.

 

BOJ #16418 Inversions (D4)

 

claim) 비어있는 자리들은 모두 감소수열이다

pf) ? ? ? x ? ? ? y ? ? ?인데 x < y라고 가정하자. 이때 (x, x), (y, y) 중 하나가 반드시 이득이다.

따라서 다음과 같은 dp를 고려하자

dp[x][p] = (숫자가 정해지지 않은 x번째 자리에 대해, 이를 p로 정했을 때 최대 inversion의 수)

 

dp[x][p]를 구할 때에 단순히 생각하면 dp[x - 1][q]를 고려한다. (q >= p)

만일 q > p라면 dp[x][p]를 구하기가 쉽다. 

왜냐하면 앞에 있는 모든 "missing" 들과 p와의 관계가 inversion이 되기 때문이다.

하지만 dp[x - 1][p]에서 dp[x][p]로 넘어갈 때에는 몇 개의 missing이 p이고, inversion이 안되는지 모른다!

 

따라서 우리는 dp[x][p]를 구할 때 사실은 dp[y][q] (y < x, q > p)를 고려해야함을 알 수 있다...

즉 dp[x][p] = MAX(dp[y][q] + y * (x - y)) + (정해진 자리들과의 inversion)

단순하게 모든 y < x인 y를 모두 고려하면 너무 느려져서 TLE를 받을 것이다.

위의 식을 잘 보면 x * y - y + dp[y][q]임을 알 수 있고, 이것은 CHT가 가능한 형태이다.

따라서 dp[x][p] = cht[p + 1].query(x) + (정해진 자리들과의 inversion)로 구할 수 있고, 

이후에는 cht[p]에 (x, -x + max(dp[x][q]))라는 직선을 더해주면 된다.

기울기가 단조 증가하는 순서로 더할 수 있기에 선형 CHT이고, 로그 단위로 굴러가는 구조체들은 아마도 터질 것이다.

 

BOJ #14207 약수 도로 (P4)

 

흥미로운 BFS 문제

우선 A[i]가 S의 약수인 모든 i는 거리가 1이라고 생각할 수 있다.

어떤 cur번 도로가 거리가 x라고 생각한다면,

(A[cur] 배수) -> (B[cur] 배수) = (A[nxt] 배수) -> (B[nxt] 배수)로 넘어갈 수 있다면, nxt번 도로는 거리가 x + 1이다.

B[cur]과 A[nxt]의 최소공배수가 N이하인지 확인하여 nxt의 거리를 구해줄 수 있다.

B[i]가 T의 약수인 모든 i 중에서 거리가 제일 가까운 것을 구하면 된다.

 

BOJ #22346 일이 이어져야 좋다 (P1)

 

정해는 KOI 사이트에 있으니 확인해 보도록... (내 풀이보다 훨 빠르게 돌아감)

세그트리나 분할정복에 익숙한 편이라면, 사실 그리 떠올리기 어렵지는 않을 것 같다.

 

적당히 답이 되는 크기가 SZ 정도라고 생각해보자.

이때 pow(2, bit + 1) > SZ인 적당한 bit에 대해서, SZ라는 범위 내에는 2^(bit + 1)이라는 자리가 한 두개 들어간다.

그렇다면, 어차피 저 자리 외에 나머지는 계속 반복적으로 등장한다는 뜻이다. (S1 0 S2 꼴이거나 S1 1 S2 꼴)

그러면 적당히 bit번째 숫자가 u 이후에 나타나는 자리를 nxt[u][bit], 또 그 다음은 nnxt[u][bit]이라고 하자.

이 자리들에 대해서, 왼쪽으로 0이 k개 있는 것부터, 오른쪽으로 0이 k개 있는 것까지 한 칸씩 밀며 모두 확인하자.

즉, 예를 들어 S13을 생각하면 11101111111에서 한 칸 밀면 11111110111가 된다.

이렇게 모든 bit에대해 확인한 모든 0이 k개 있는 부분문자열에 대해서 제일 긴 것의 길이를 구하면 된다.