https://www.acmicpc.net/problem/17697 17697번: Railway Trip JOI Railways is a company operating one railway. In the railway of JOI Railways, there are N stations on a straight line numbered from 1 to N. For each i (1 ≤ i ≤ N − 1), the station i and the station i + 1 are connected by a railway track. JOI Railw www.acmicpc.net $N$개의 역이 일렬로 있으며, $i$번 역의 등급은 $A_i$이다. 모든 $A_i$에 대해 $1 \le A_i \le K$가 성..
곧 있을 2023 함수컵을 대비해 2019 함수컵을 풀어 보았다. 굿바이 한별(79brue, flappybird, lisifu) 팀 연습 세션으로 5시간 동안 돌아 1068/1200점, 대회 중 2등의 성적을 기록했다. 나는 저 중 1-1, 1-2, 1-3, 2-1, 4-1을 맡았다. 1-x 문제들은 매우 쉬운 문제들이었기 때문에 사실상 2-1 푼 게 유일한 기여라고 할 수 있겠다. 4-1도 원래 무조건 풀었어야 했을 문제인데, 못 푼 게 아쉽다. 나머지 문제들 중에서는 어려운 게 많았는데 팀원들이 대부분 너무 잘 풀어줘서 고마웠다. A. HicCup (0:13) $X$에 대한 이분 탐색을 한다. 간단한 스택 문제이다. 스택을 통해 현재 상태를 오토마타 느낌으로 저장한다. 현재 상태는 H, HC, HC!..
어제랑 비슷하게 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 중등..