BOJ 10848. 팔렘방의 다리 정말 좋은 문제. 직접 풀지 못해서 풀이를 봤는데 놀라웠다. 풀이는 이곳에 적지 않는다. 풀이를 보고 나서 든 생각... 더보기 요즘 식 정리 문제에서 많이 말린다는 생각이 든다. IOI 2022 Circuit, Goodbye BOj 2022 F도 식 정리 문제였는데 못 풀었고, 식 정리만 하면 쉬운 유형들이었다. 이 문제도 마찬가지인 것 같은데, 문제를 풀면서 복잡한 식 정리를 피해가려는 문제풀이 스타일이 지속적으로 발목을 잡는 것 같다. BOJ 10066. 팰린드롬 팰린드롬 조건이 없었다면 LCP 배열을 구하고 나서 DnC로 풀 수 있다. 그런데 팰린드롬 조건이 있다 보니 이것만으로는 안 끝나고, 구간 내에서 가장 긴 팰린드롬을 구하는 쿼리까지 처리해야 한다. 대략적..
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의 전형적인..
Problem Solving Diary #7
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_..
Problem Solving Diary #6
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$번 범위를 이미 선택했으므로 다음 연결 성분의 범위들은 ..