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..
이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다. #1. Just Long Neckties (0:00 ~ 0:06) 만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다. Time Complexity: $O(N..
이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다. #1. Trous de Loop (BOJ 18368) 조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다. Time Complexity: $O(N)$ #2. Highway Modernization (BOJ 183..