BOJ 14636. Money for Nothing 문제는 $\max_{1 \le i \le m} \max_{1 \le j \le n} (q_j - p_i) (e_j - d_i)$를 구하는 것입니다. 식의 형태가 직사각형의 넓이를 구하는 것과 닮았기 때문에, $(p_i, d_i)$, $(q_j, e_j)$ 상에 플로팅한 기하 문제로 바꿔 봅시다. 모든 점 쌍을 시도해 보기에는 시간이 너무 오래 걸립니다. 여기서 관찰해야 할 사실 하나는 [절대로 답에 포함될 수 없는 점]이 존재한다는 것입니다. 예를 들어, $(p_i, d_i)$가 $(p_j, d_j)$보다 오른쪽 위에 있다면 $(p_i, d_i)$는 절대 답에 포함될 수 없습니다. 또한 어떤 $(q_i, e_i)$에 대해서도 이득을 볼 수 없는 $(p_..
BOJ 22031. Yet Another Interval Graph Problem 먼저 구간들을 끝점 순서대로 정렬합시다. 즉 $i < j$이면 $e_i \le e_j$입니다. $DP[i]$를 $i$번 구간이 선택된 가장 번호가 큰 구간일 때의 답으로 정의합시다. 이때 $j < i$인 $j$에 대해 $DP[j]$에서 $DP[i]$의 상태 전이를 빠르게 구할 수 있으면 문제를 $O(N^2)$ 남짓한 시간 복잡도에 풀 수 있습니다. $DP[j]$에서 $DP[i]$로 전이하는 방법을 찾아봅시다. 이는 곧 $[j+1, i]$ 인덱스를 가진 범위 중 $K$개 이하를 잘 선택해 최대 가중치를 가진 연결 성분을 구하는 것과 같은데, $DP[j]$의 정의상 $j$번 범위를 이미 선택했으므로 다음 연결 성분의 범위들은 ..
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 ..
https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net Step 1 ($O(M \log^3 N)$) 이 단계는 머지 소트 트리를 알고 있다면 누구나 풀 수 있습니다. 머지 소트 트리는 일반적인 세그먼트 트리와 비슷한데, $[l, r]$ 구간을 담당하는 노드에는 $[l, r]$ 구간에 있는 수들을 정렬해서 배열 형태로 저장해 둔 세그먼트 트리를 말합니다. 머지 소트 트리의 구축은 모든 노드에 대해 정렬을 독립적으로 하면 $O(N \log^2 N)$에 가능합니..
이번 IOI에 한국 국가대표로 선발이 되어서, 본 대회를 치르게 되었습니다. 코로나19가 계속되는 바람에 올해도 싱가포르 현지에서 대회를 치르지 못하고 우리나라에서 온라인으로 치르게 된 점이 아쉽습니다. 작년에 이어 2년째 IOI에 참가하게 되었는데, 작년과는 느낌이 확연히 다른 대회였습니다. 작년과 다르게 올해는 주변 누구도 성적에 대한 기대를 가지지 않아서 편한 마음으로 시험을 볼 수 있었습니다. 아마 이러한 점도 성적에 영향을 주지 않았나 싶습니다. Day 0 (Practice Session) 연습 세션 문제는 작년과 거의 똑같았습니다. 차이점이 있다면, 무슨 이상한 전처리를 해야 맞는 문제 하나가 간단한 bfs 문제로 바뀌었습니다. 작년에 끝까지 풀지 못했던 문제(Jelly Flavours)를 이..
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..