어제랑 비슷하게 3인 팀 5시간 셋을 3시간 (2분) 동안 돌았다. 대회 당시 11솔이 최대였고, 나는 10솔로 4등을 했다. (페널티 1143) 한 문제를 못 풀었는데 남은 문제도 크게 어렵진 않아서, 올솔을 못한 게 조금 아쉽다. A (6분) 가능한 게임 진행 방법이 $2^{21}$가지에 못 미친다는 것을 알 수 있다. 모든 경우에 대해서 가능한지 시도해 보면 된다. 이외에는 크게 언급할 점이 없다. C (24분) B에서 맞왜틀을 좀 당하다가 바로 C로 갔다. 풀이는 단순히 앞에서부터 가질 수 있는 커피 수를 계속 관리하면 쉽다. D (28분) $(r, 1)$이 유효한 답이다. F (1시간 9분) 일단 각 팀명의 길이를 구해야 한다. 1번 팀의 팀명을 $x$로 두면 이후 팀들의 팀명을 $ax+b$꼴로..
선발고사 대비용으로 3시간짜리 셋을 돌았다. OI가 아닌 ICPC 셋을 선택한 이유는, 적당한 3시간 OI 셋을 찾을 수가 없었다. 3인 셋을 혼자 도는 거니까 대략 스코어보드 깠을 때 5등 안에 들자는 마음으로 셋을 쳤다. 대회 당시 9솔이 최대였고, 나는 11솔을 했다. J 빼고는 크게 어려운 문제가 없는 셋이었다. 각 문제에 대해 푼 순서대로 대략적인 풀이를 적어 본다. A (0:02) 문제 해석하는 게 푸는 것보다 더 오래 걸리는 문제다. 예제가 예상과 달라서 10초 정도를 허비하는 바람에 1분째에 맞출 수 있는 문제에서 시간을 날렸다. 답은 $(x \pm r, y \pm r)$의 네 꼭짓점으로 이루어진 정사각형이다. 이 외에도 다양한 답이 있겠지만, 굳이..? B (0:19) 쉬워 보여서 A 다..
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의 전형적인..