4/21
BOJ 27452 - (재밌고 웃기고 센스있고 깔끔한 제목)
Platinum 5
#recursion
$|S_i|$가 $10^{18}$보다 커지는 $i$의 최솟값을 찾아서 주어지는 $n, k$를 그 범위 안으로 끌어내리고 그 때부턴 직접 재귀로 찾아주면 된다.
Platinum 3
#greedy #disjoint_set
도로를 역순으로 하나씩 배치하면서 $0$과 $N-1$을 잇게 되면 그 가중치만큼의 사람을 이동시켜주면 된다.
$i$번 도로가 배치되어있다고 가정하면, $i-1$번 이하의 모든 도로 사람들을 수용할 수 있다. $3^i > 3^{i-1} + \cdots + 3^0$이기 때문이다.
Platinum 4
연산을 한 번도 수행하지 않는 경우에는 두 수열이 동일해야 POSSIBLE이다.
연산을 한 번 이상 수행해야 한다면, 수열 내에 연속한 원소 3개가 오름차순 또는 내림차순으로 되어있어야 가능하다.
Platinum 2
#tree_dp #dfs #greedy
하나의 연결 요소 $G$에 대해서만 생각해보자. $G$에 속하는 정점 $i$에 대해, $dist[i]=(i$에서 가장 먼 정점까지의 거리$)$로 정의하면, 이 연결 요소와 다른 연결 요소를 잇는다고 가정할 때 $dist[i]$가 가장 작은 점들끼리 이어줘야 한다는 것을 알 수 있다.
각각의 연결 요소에서 가장 작은 $dist[i]$들을 $R_j$라고 하면, 이제 문제는 $\max($각 연결 요소에서의 지름$, \max(R) + \max_2(R) + L, \max_2(R) + \max_3(R) + 2L)$를 구하는 것으로 생각할 수 있다.
연결 요소들끼리 최적으로 이었을 시, 항상 두 개 이하의 추가 간선만으로 서로 이동할 수 있기 때문이다.
4/22
Platinum 3
#trie
예전에 구현해둔 정수 삽입, 삭제, 검색이 가능한 트라이 구현체를 가져와서 풀었다.
Platinum 5
#small_to_large
$1\le i \le N$에서 $S[i]$를 현재 $i$값을 가지는 수들의 집합으로 정의하자. 초기엔 $S[i] = {i}$이다.
$u, v$가 주어질 때마다, $S[u]$를 $S[v]$쪽에 합쳐주면 된다. (with small to large)
Diamond 4
#segtree #priority_queue
한 번의 테스트케이스에서 심어지는 식물의 개수는 $O(M)$이다. 그러므로 당연히 뽑힐 수 있는 식물의 개수 또한 $O(M)$이다.
따라서 식물을 뽑는 쿼리가 주어지면 직접 하나씩 뽑아도 된다.
3번 쿼리는 각 정원의 식물 수를 관리하는 합세그로 구할 수 있고,
2번 쿼리에서 update가 필요한 구간을 잘 판별해서 꼭 뽑혀야만 하는 구간에 대해서만 더 깊이 들어가도록 구간의 max값을 관리하는 세그를 하나 더 가지고있으면 된다.
1. 하나의 정원에 여러 식물이 들어갈 수 있고, 각각의 값이 유지되어야 함
2. 높이가 높은 순서대로 뽑힘
두 성질을 보면, 최대 힙 $N$개를 사용해서 각 정원 별로 식물들을 관리할 수 있음을 알 수 있다.
시간에 따른 높이 처리는 $t$번째 날의 높이 $h$에 대해, 이 높이는 $0$번째 날에 $h-tK$였음을 이용해 모두 $0$번째 날 기준의 높이로 처리하면 된다.
4/23
Diamond 5
#sqrt_decomposition #binary_search
$N$개의 수를 크기가 $\sqrt{N}$인 구간들로 나누어서 생각해보자.
1번 쿼리에서, $[i,j]$에 완전히 포함되는 구간들에 대해서는 upper_bound를 사용하여 각 구간 당 $\log{\sqrt{N}}$에 원하는 값을 구할 수 있다. 구간이 최대 $\sqrt{N}$개이므로 시간복잡도는 $O(\sqrt{N}\log{\sqrt{N}})$이다. 양 끝에 완전히 포함되지 않는 구간에 대해서는 직접 하나씩 확인해준다고 가정해도 시간복잡도는 $O(\sqrt{N})$이다. 따라서, 한 번의 1번 쿼리에 대한 시간 복잡도는 $O(\sqrt{N}\log{\sqrt{N}})$이다.
2번 쿼리가 들어오면, 해당 인덱스가 포함된 구간으로 가서 erase 후 새로운 값을 넣고 정렬시키면 된다. 시간복잡도는 $O(\sqrt{N}\log{\sqrt{N}})$이다.
따라서 전체 시간복잡도 $O(M\sqrt{N}\log{\sqrt{N}})$으로 통과할 수 있다.
BOJ 24953 - Reconstruction Project
Diamond 3
#mst #graph_traversal
$X_0 = 0$으로 두면, 이 때는 기본 MST의 비용이 답이 된다.
MST에 사용되지 않은 어떤 간선 $e = (u_e, v_e, c_e)$에 대해, 현재 MST상에서 $u$와 $v$를 잇는 경로에서 가장 가중치가 작은 간선을 $m = (u_m, v_m, c_m)$이라 하면, $X = \lfloor \frac{c_m + c_e + 1}{2} \rfloor$가 되었을 때, 간선 $m$이 빠지고 $e$가 추가되는 것이 그 때의 MST가 된다.
모든 간선에 대해 $X$를 미리 구해놓으면 해결할 수 있다. 본인은 dfs로 구했고, $O(MN)$의 시간이 걸렸다.
$Q$번의 쿼리에서는 $O(Q+M)\log{N})$정도 걸린 것 같다.
Diamond 5
#sqrt_decomposition #binary_search
sqrt 분할 시 나오는 구간들의 개수를 $S$라고 하면, 이 $S$를 $\frac{N}{\sqrt{N}}$으로 잡았더니 시간 초과가 나서, $S = 1000$으로 두고 제출하니 아슬아슬하게 통과했다. 구간의 개수를 줄이는 것이 더 도움되는 것 같다.
4/24
Platinum 5
#bitmask_dp
$dp[k]$를 처리한 일 집합 $k$의 최대 확률로 정의하고 Top-Down으로 테이블을 채워나가면 된다.
4/25
Platinum 4
#prefix_sum #priority_queue
문제를 dp식으로 접근해보자.
제한을 고려하지 않는다면, 아래와 같은 식을 쉽게 떠올릴 수 있다.
$dp[i] = \min_{i-L \le j < i ; \mid S[i] - S[j] \mid \le 1} {dp[j] + 1}$
$S[i]$는 $1~i$번째 문자에서 'K의 개수' - 'Y의 개수'이다.
위 dp식은 $O(N^2)$로 시간 초과를 받으므로 최적화를 해줘야 한다.
어떤 인덱스 $i$에서 고려해줘야 하는 인덱스들은 $\max(i-L,0)$부터 $i-1$까지 인덱스 중, $S[i]$와의 차이가 1 이하인 인덱스들이다.
따라서, $S$의 각각의 값마다 우선순위 큐를 이용해 그 곳에 인덱스 $i$ 이전의 $dp$값들을 저장해둔다면 $O(N\log{N})$으로 줄일 수 있다.
4/28
Platinum 5
#dp #case_work
각 블럭에 취할 수 있는 행동은 왼쪽으로 넘어뜨리기, 오른쪽으로 넘어뜨리기, 아무것도 하지 않기 총 3가지이다.
또, 각 블럭의 행동에 제약을 걸 수 있는 블럭은 항상 그 블럭과 가장 가까운 블럭뿐이다.
$\Rightarrow$ (블럭의 개수) * 3 형태의 dp table을 구상하여 풀면 된다.
Platinum 4
$P \le 347$이하의 모든 경우에 대해 답을 직접 출력해보고, 규칙성을 찾아 $O(1)$에 해결했다.
4/30
Platinum 5
#mst #graph_traversal
쿼리 $x$ $y$에서, 두 정점 $x$와 $y$를 MST 상에서 분리시켜 그 가중치 합을 최소로 만들어야 한다. (간선을 하나 적절히 끊어서)
트리에서 임의의 두 정점을 잇는 단순 경로는 항상 유일하므로, $x$와 $y$를 잇는 단순 경로 상에서 가중치가 가장 큰 간선 하나를 끊어주면 최적해를 얻을 수 있다.
Platinum 5
#dijkstra
$dist[n][k]$를 $1$번 정점에서 $n$번 정점까지 왔고, $k$개의 포장된 도로를 통과했을 때의 최소 시간으로 정의하고 다익스트라를 돌리면 된다.
Platinum 4
#mst
23034번 문제와 동일한데, 제한이 조금 더 크다.
본인은 segtree로 해결했는데, 더 쉬운 풀이가 있는 듯하다.
간선 $(u,v,w)$에 대해, $u$와 $v$를 잇는 단순 경로상의 최대 가중치를 $x$라고 하면, $x = w$라는 것은 $w$또한 MST의 일부가 될 수 있다는 얘기이다. 즉, 크루스칼 알고리즘으로 MST를 형성하는 과정에서 $w-1$ 이하의 가중치를 모두 처리했을 때, 두 정점이 같은 컴포넌트에 속해있지 않다면 이 간선은 MST에 속할 수 있는 것이다.
'문제 풀이' 카테고리의 다른 글
| BOJ 25549 - 트리의 MEX [C++] (0) | 2024.05.01 |
|---|---|
| BOJ 15683 - 감시 [C++] (1) | 2024.05.01 |
| 4월의 문제 풀이 - (2) (0) | 2024.04.22 |
| 4월의 문제 풀이 - (1) (2) | 2024.04.13 |
| BOJ 1176 - 섞기 [C++] (0) | 2023.12.14 |