mo1lusca의 블로그

https://www.acmicpc.net/problem/4008CHT의 바이블 점화식은 $DP[i] = max(\;a(S[i]-S[j])^{2}+b(S[i]-S[j] ) +c+DP[j]\;)$ 이다.$j$와 관련 없는 항은 $max$밖으로 빼줄 수 있다.$(S[i]-S[j])^{2}$를 전개한 뒤 &max& 밖으로 항을 빼주자.그럼 $DP[i] = max(\;-2aS[i]S[j] + aS[j]^{2} - bS[j] + DP[j]\;) + aS[i]^{2} + bS[i] + c$이 되고,$max$ 밖의 항들은 상수항이므로 나중에 더해줘도 된다.$max$ 안의 식은 $S[i]$에 대한 일차식으로 나타낼 수 있다.따라서 $DP[i] = max(\;-2aS[j]x + (aS[j]^{2}-bS[j]+DP[j])..

https://www.acmicpc.net/problem/13263$DP[i]$ : $i$번째 나무를 높이가 1이 되게 하는 최소비용 이다.그럼 점화식이 $DP[i] = min( A[i] * B[j] + DP[j] )\;(0\le j 이때 $A[i] * B[j]$는 $i$보다 작은 $j$에 대해, $i$번째 나무를 $j$번째 비용으로 모두 자른다는 뜻이고,$DP[j]$는 $j$번째 비용을 사용하기 위해 $j$번째 나무를 자르는걸 의미한다. 하지만 n이 100,000이라 $O(n^{2})$은 안되기 때문에....CHT를 써줘야 한다!문제 조건에 의해 $a_{i}$는 단조증가하고, $b_{i}$는 단조감소하기 때문에, CHT를 쓸 수 있다. #include using namespace std;using ll..

https://codeforces.com/contest/2171코포를 두세번정도 쳐봤었지만..진짜 실력을 키우려면 업솔빙을 해야 한다는 것을 알게 되었다.. A. Shizuku Hoshikawa and Farm Legs브론즈쯤 되는듯한 간단한 사칙연산 문제였다.n이 홀수인 경우는 불가능하니 0이다. n이 짝수인 경우만 고려하자.소의 마릿수를 정하면 닭의 마릿수는 자동으로 정해진다. (소 1마리 == 닭 2마리)n을 4로 나눈 값 + 1(소를 선택하지 않는 경우)가 정답이 되겠다.더보기include using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; if (n % 2) { cout B. Yuu Koito..

https://www.acmicpc.net/problem/13510트리상의 임의의 두 노드 u, v를 잇는 경로 중 비용이 가장 큰 간선의 비용을 출력하면 된다. HLD (Heavy Light Decomposition) 를 사용하면 된다!이 글에서는 이론적인 내용보단 구현적인 내용을 다룬다.부분 코드 설명#include using namespace std;const int MAX = 100'005;int sz[MAX];int dep[MAX];int par[MAX];int top[MAX];int in[MAX], out[MAX]; vector g[MAX];vector, int>> edge;int seg[MAX * 4 + 16];선언부이다.. 와우...뭐가 많아보이지만 사실 간단하다!- sz[i]는 노드 i를..

https://www.acmicpc.net/problem/18227루트(수도)와 임의의 노드 사이의 경로에 있는 노드들에,루트부터 +1, +2, +3...이 더해진다.이렇게 경로라고 생각하면? 뭔가 HLD + Lazy prop을 써야할 것 같지만ETT만으로도 풀 수 있다! 핵심 아이디어는 노드 당 물이 부어진 횟수와,물을 한번 부을때마다 얼마나 부어질지를 따로 생각하는 것이다.이러한 트리가 있다고 해보자.6번 노드에 물을 부으려면 1 - 4 - 6 순서로 1, 2, 3 만큼의 물을 부어야 한다.항상 루트를 첫번째로, 목표 노드를 마지막으로 물을 붓게 되고..이 경로에 포함되는 노드에 부어지는 물의 양은 루트로부터의 거리, 즉 depth임을 알 수 있다. 노드 별로 항상 같은 양만큼 물이 부어지니, 노드 ..

https://www.acmicpc.net/problem/14268얼핏 보면 간단히 합세그만 구현해도 되는게 아닌가? 싶지만문제에서 주는 조직도는 결국 트리 형태이고, 쿼리 또한 서브트리를 대상으로 한다.하지만 세그트리는 선형 구조(배열)에서 사용할 수 있기 때문에 무지성 합세그구현은 못한다..이럴땐 트리를 선형으로 펴주는 ETT를 사용하면 된다!ETT(Euler Tour Technique) 란?ETT란, 임의의 노드의 서브트리를 선형구조의 구간으로 표현할수 있게 하는 알고리즘(테크닉)이다.세그트리와 함께 사용하면 서브트리의 합을 구할 수 있는 것이다! (1번 노드가 루트 노드라고 생각하자.)ETT는 기본적으로 DFS가 노드를 방문하는 순서에 따라 번호를 매긴다.DFS를 수행하는 과정에서 직접 노드를 방..

https://www.acmicpc.net/problem/1517본격적인 설명 전, 하나의 간단한 개념을 짚고 넘어가면 좋다.역전쌍(inversion)이란, 어떤 배열 내에서 자신보다 작은 인덱스를 가지지만 (자신보다 앞에 있지만)자신보다 큰 값을 가지는 원소 쌍을 말한다. 다시 본론으로 돌아오자.수열을 주고, 해당 수열로 버블소트를 수행할 때 Swap이 몇번 일어나는지 구하면 된다.물론 진짜 버블소트를 돌리면 시간초과가 난다. 버블소트 수행 중 Swap이 일어난다는 뜻은 무엇인가?Swap을 당하는 두 원소가 역전쌍임을 의미한다.(버블소트 자체가 역전쌍을 올바른 순서로 뒤집는 것이기 때문)그렇다면 우리는 배열에 대해 직접 버블소트를 수행하는게 아니라,배열 내의 모든 역전쌍의 갯수를 구하면 된다. Coun..

https://www.acmicpc.net/problem/12738간단한 O(n log n) LIS 문제이다.이분탐색을 구현하지 않아도 c++의 lower_bound 함수로 딸깍이 된다.#include #include #include using namespace std;int main() { int n; cin >> n; vector v; vector lis; for (int i = 0; i > x; v.push_back(x); } lis.push_back(v[0]); for (int i = 0; i 설명하기에는 필력에 한계가 있어서이 알고리즘을 이해하는데 도움이 되었던 블로그 글을 첨부하겠다https://eatchangmyeong.github.io/2022/01/20/why-is-lis-algori..

https://www.acmicpc.net/problem/1504다익스트라를 사용하는 최단거리 문제지만,특정 두 노드를 경유해야한다는게 관건이다.경유하면서 거리를 최단으로 줄이는 방법을 생각해보면 도움이 된다.#include #include #include #include using namespace std;const int INF = 1e8; //int N, E;vector> graph[801];vector dist;void daik(int start) { dist.assign(N + 1, INF); dist[start] = 0; priority_queue , vector>, greater> pq; pq.push({ 0, start }); while (!pq.empty()) { auto [cur_di..

https://www.acmicpc.net/problem/117792025.07.11 - [백준] - [백준] 1916 최소 비용 구하기 - C++이 문제와 비슷한 문제지만? 최단거리만 출력하는게 아니라최단거리를 지나며 경유하는 노드와 그 갯수도 출력해주어야 한다.부분 코드 설명void daik(int start) { dist.assign(N + 1, INF); priority_queue, vector >, greater > pq; dist[start] = 0; route[start] = -1; // pq.push({ 0, start }); while (!pq.empty()) { auto [cur_dist, cur] = pq.top(); pq.pop(); if (dist[cur] cur_dist ..