79brue의 PS 블로그

BOJ 15844. Land of the Rainbow Gold 이런 식으로 연결 성분 개수를 특이한 그래프(여기서는 격자 그래프)에서 구하라고 하면 높은 확률로 오일러 지표를 쓰는 것이다. 흔히 아는 그 v-e+f 공식인데, 연결성분이 여러 개일 경우 공식이 조금 달라진다. 하여튼 v-e+f 형태로 나오는 것은 맞으니 외울 필요는 없고 그냥 여러 개 그려 보며 규칙을 찾으면 된다. 그래서 문제는 주어진 영역에서 v, e, f의 개수를 구하는 것이다. 일단 그래프는 각 격자칸을 점, 인접한 격자칸을 선으로 이은 형태가 되어야 할 것이다. 이렇게 하면 v, e, f를 어떻게 세어야 할 지 각이 잡힌다. 셋 모두 그 개수를 직접 세기보다는 빠지는 개수를 세서 여집합으로 처리하는 것이 편리할 것이다. 즉, 정..

BOJ 25422. Seesaw 오름차순으로 정렬된 길이 $N$의 수열이 있고, 그 수열의 양쪽 끝 수 중 하나를 제거하는 작업을 $N-1$번 반복한다. 이 과정 동안 수열의 수들의 평균의 최댓값과 최솟값의 차를 최소화 해야 한다. 다항 시간 풀이를 만들려고 생각해 보면, 일단 상태가 $[l, r]$ 꼴로 표현될 것임을 쉽게 예측할 수 있다. 그러나 여기서 문제는 각 상태에 대해 두 가지 값을 관리해야 한다는 점이다. 지금까지 본 구간의 최대 평균과 최소 평균을 관리해야 한다. 그런데 문제는 이 두 값이 독립적이 아니라는 것이다. 즉, 상태 $[l, r]$까지 오는 방법 중 가능한 최대 평균의 최솟값 $M$과 가능한 최소 평균의 최댓값 $m$을 동시에 얻을 수 있을지 확실하지 않다는 것이다. 그렇다면 상..

JOI Spring Camp 2015년의 문제 세 개를 골라서 풀었다. 대략적인 풀이와 떠올리는 과정 정도만 간단히 적어보려고 한다. BOJ 17716. Copy and Paste 2 문제를 딱 보면 거꾸로 풀기라는 생각이 들었고, 바로 짜서 풀었다. 사실 거꾸로 푸는 문제를 한 번도 풀어본 적이 없다면 그 아이디어를 스스로 떠올리기는 상당히 힘들다고 생각한다. 하지만 이러한 유형을 많이 풀어 보면 그 특유의 느낌이 오는 것 같다. 문제 형태가 매우 간단하고, 시간 복잡도도 log 같은거 붙지 않고 깔끔하게 나와야 할 때 쓴다는 느낌? 유사한 아이디어를 쓰는 문제 몇 개가 있다. 이런 문제 유형 특성상 아이디어 자체가 매우 큰 스포일러라는 점을 조심하자. 더보기 유사한 아이디어를 쓰는 문제로 KOI 중등..

BOJ 21792. Meetings 2 먼저 답 후보가 여러 개인 경우가 언제 일어나는지 살펴 봅시다. $2i$명의 비버가 만난다고 할 때, 답 후보가 $j$개인 참석자 선정이 존재한다면 트리에 아래 조건을 만족하는 경로가 존재합니다. 경로의 길이는 $j-1$이고, 경로의 양쪽 서브트리(경로의 양 끝점 포함)에 정점이 각각 $i$개 이상 존재한다. 같은 맥락으로 만약 참석자 수가 홀수라면 답은 항상 1개입니다. Subtask 2 (20점) $O(N^2)$ 풀이가 가능하므로, 가능한 모든 경로에 대해 양쪽 서브트리에 있는 정점 개수를 적당한 전처리를 통해 $O(1)$에 찾아주면 됩니다. 자세한 설명은 생략합니다. Subtask 3 (100점) 가능한 모든 경로를 시도해 봐야 하는데, $N$이 큰 경우 사용..

BOJ 4008. 특공대 $$S_i = \sum_{1 \le j \le i} A_j $$ $$DP[i] = \max_{0 \le j < i} \left( a(S_i - S_j)^2 + b(S_i - S_j) + c + DP[j] \right)$$ 이제 위 점화식을 빠르게 계산해 봅시다. $$ \begin{align} DP[i] &= \max_{0 \le j < i} \left( aS_i^2 - 2aS_i S_j + aS_j^2 + bS_i - bS_j + c + DP[j] \right) \\ &= aS_i^2 + bS_i + c + \max_{0 \le j < i} \left( -2aS_i S_j + aS_j^2 - bS_j + DP[j] \right) \end{align}$$ 위 식은 CHT의 전형적인..

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 ..