79brue의 PS 블로그

BOJ 7644. Highway Construction 트리 DP를 돌려 주며, 각 점이 경로의 LCA일 때의 답을 구해 주면 됩니다. 먼저 각 점에서 아래로 가장 먼 점까지의 거리를 전처리해 주고, 이것을 이용해 트리 DP를 할 수 있습니다. 어떤 점 $v$의 자식 $c$를 봅시다. $v$를 LCA라고 하면, 자식 최대 두 개를 골라 해당 자식을 경로에 포함시킬 수 있습니다. 경로에 포함되지 않는 자식의 경우 해당 서브트리에서 가장 먼 정점까지의 거리만이 중요하고, 경로에 포함되는 자식의 경우 트리 DP를 통해 올려준 값이 중요합니다. 해당 값들로 LCA가 $v$일 때의 답을 구한 후, 이번에는 자식을 하나만 골랐을 때의 답을 부모로 전달해 줍니다. 더보기 #include using namespace ..

BOJ 20641. Sleeping Cows 문제에서 요구하는 조건은 크게 두 가지입니다. 모든 소가 하나의 헛간에 들어갈 수 있도록 선택할 것 선택하지 않은 소들은 모두 선택하지 않은 헛간보다 크기가 클 것 2번 조건을 다른 말로 표현하면, "선택하지 않은 가장 작은 소"가 "선택하지 않은 가장 큰 헛간"보다 크면 됩니다. 따라서 선택하지 않은 가장 작은 소를 고정하고, 2차원 DP를 돌리면 $O(N^3)$ 풀이가 나옵니다. DP에 대해 간단히 설명하면 우선 헛간과 소를 모두 한 배열에 넣고 크기 순으로 정렬한 뒤, 왼쪽부터 차례로 보면서 그 인덱스를 i, (지금까지 선택한 소의 수 - 지금까지 선택한 헛간의 수)를 j로 정의하면 됩니다. 이제 $N$을 하나 떼어 봅시다. 선택하지 않은 가장 작은 소의..

지인 분들에게 추천받은 문제들을 풀어 보았습니다. BOJ 12963. 달리기 번호가 큰 간선부터 보면서, 해당 간선 용량만큼의 사람을 추가로 보낼 수 있는지 판별합시다. 이때 남은 간선들을 통해 시작점에서 끝점까지 모든 간선의 용량이 $3^i$ 이상인 경로를 만들어야 합니다. 이러한 경로가 존재하지 않으면 사람을 보낼 수 없습니다. $3^0 + 3^1 + \cdots + 3^i < 3^{i+1}$이기 때문에, 용량이 큰 간선을 직접 사용하지 않는 이상 용량이 더 작은 간선들에 의해 막히는 일이 없습니다. 따라서 용량 큰 간선을 최대한 취하는 것이 최적 전략이고, Union Find 자료구조를 이용해 시작점에서 끝점까지 경로가 존재하는지 판단해 주면 됩니다. 나이브하게 짤 경우 $O(NM)$, Union ..

IOI 2015 Day 1. Teams 서브태스크 1, 2 (34점) $O(NQ)$로 풀 수 있는 경우 어떻게 쉽게 풀 수 있을까요? 그리디한 접근을 생각해 봅시다. 정원 수가 작은 프로젝트부터 보면, 현재 넣을 수 있는 사람들 중 $B_i$가 가장 작은 사람을 넣는 게 이득입니다. (나중에 가능성이 있는 사람을 남겨 둬야 하므로) 따라서 사람들을 $A_i$ 순서로 정렬하고 프로젝트를 정원 수에 따라 정렬한 뒤에, 힙을 사용하여 $B_i$가 작은 사람부터 뽑아내면 됩니다. 시간 복잡도는 $O(NQ \log N)$입니다. 더보기 #include #include "teams.h" using namespace std; typedef long long ll; int n; pair arr[500002]; void..

IOI 2020 Day 1. Comparing Plants 대회 때 멘탈이 제대로 갈려나간 문제입니다. 다음 대회를 망치지 않기 위해서는 이런 문제를 풀어야 한다고 생각해서 잡고 풀었습니다. 서브태스크 1 (5점) $k=2$로, 바로 옆의 식물과의 대소관계를 확실히 알 수 있습니다. 어떤 식물 $x$가 식물 $y$보다 확실히 크려면 (문제 조건에 의해 $x h_{x+1} > \cdots > h_{y-1} > h_y$ $h_x > h_{x-1} > \cdots > h_1 > h_n > \cdots > h_{y+1} > h_y$ 첫 번째 조건은 $s_x = s_{x+1} = \cdots = s_{y-1} = 0$에 대응되고, 두 번째 조건은 $s_1 = \cdots = s_{x-1} = s_y = \cdot..