https://jaehoyi-blog.vercel.app/
ICPC 2021 후기
예선 후기는 stonejjun 블로그에서 볼 수 있다. 우선 대회 당일에 우여곡절이 정말 많았다. 대회 장소에 문제가 생겨서 세팅하기에도 바빴는데 프린터도 고장나서 그냥 노트북으로 순서대로 같이 읽기 시작했다. A는 지문이 너무 길기도 하고 딱 봐도 처음 풀 문제는 아닌 것 같아서 B로 넘어갔다. 모든 색깔이 다 포함되는걸 무지개라고 하고, 두 겹인걸 찾으면 된다는 것까지는 이해했는데, 끝날 때까지 \(P\)도 임의로 정하고 \(P'\)도 임의로 정하는걸로 이해하고 있었다. 근데 stonejjun이 풀 수 있다고 해서 풀고 있었다. 이 쯤에 아마 프린터가 고쳐져서 문제를 뽑다가 다시 고장났다. 그래도 어찌저찌 앞 부분 문제는 볼 수 있었다. C는 그냥 시뮬레이션이었고 B도 코딩이 잠깐 막혀있어서 일단 내..
AtCoder Beginner Contest 210 후기
AtCoder Beginner Contest 210 C. Colorful Candies 길이가 \(K\)인 구간을 투 포인터로 관리하면서 양 끝에서 새로운 수가 추가되는지, 사라지는지를 확인하면 된다. D. National Railway 두 지점을 고르는 것은 두 가지 경우가 있다. 1) 왼쪽 위와 오른쪽 아래 (\(i\le i',\ j\le j'\)) 2) 오른쪽 위와 왼쪽 아래 (\(i\le i' \ j\ge j'\)) 1)의 경우는 \(A_{i,j}+A_{i',j'}+(i'-i)+(j'-j)\)이다. 연관된 것끼리 묶으면, \((A_{i,j}-i-j)+(A_{i',j'}+i'+j')\)이 되므로, 오른쪽 아래 점이 \((i',j')\)가 되는 경우의 최솟값은 \(i\le i',\ j\le j'\)인..
역전의 제왕 (Hard) 아마 가장 간단한 방법은 PBDS(Policy-Based Data Structure)라는 라이브러리에 있는 Order Statistics Tree라는 걸 쓰는 것 같다. 이 자료구조는 정렬된 순서를 유지하면서 원소 삽입, 삭제, \(k\)번째 원소, lower bound와 그 위치를 다 \(O(\log{n})\)만에 할 수 있는 기능이 있다. 그러면 스코어보드를 구현만 하면 변하기 전 순위와 변한 후 순위를 모두 쉽게 알 수 있다. 이 것과 별개로 내가 푼 방법은 조금 다른 식이다. 우선 마지막 순위를 구하는 것은 우선순위 큐로 할 수 있다. 그런데 문제 하나를 스코어보드에 반영한 뒤에 얼마나 순위가 올랐는지는 쉽게 알 수 없다. 이 것을 구하기 위해 우선순위 큐에서 나온 참가자..
Codeforces Round #695 (Div. 2) 후기
Codeforces Round #695 (Div. 2) A. Wizard of Orz 약간 함정스러운 문제였다. 무조건 \(989\cdots \)로 시작하는게 가장 크다. B. Hills And Valleys \(a_i\)를 바꿨을 때, 개수가 변하는 요인은 \([a_{i-2},a_{i-1},a_i]\)과 \([a_{i-1},a_{i},a_{i+1}]\)과 \([a_{i},a_{i+1},a_{i+2}]\)로 세 가지 뿐이니 \(a_i\)를 적당히 바꾼 뒤에 개수를 비교해주면 된다. 이 때 적당히가 어느정도인지가 관건인데, \(a_{i-1}\)또는 \(a_{i+1}\) 중 하나가 답이 될 수 있다. 나는 대회 때는 적당히 저 둘을 포함한 \(10\)가지 정도 다 검사했다. C. Three Bags 첫 문단..
Codeforces Round #694 (Div. 1) 후기
Codeforces Round #694 (Div. 1) A. Strange Birthday Party 처음엔 감도 안 잡혀서 포기할까 생각하다가 조금 더 고민해보니 \(c\)를 기준으로 이분탐색할 수 있다고 생각했는데 그렇게 거의 다 짜고난 뒤에 안 된다는걸 깨달았다. 그래서 더 고민해보니 \(k\)를 기준으로 정렬한 뒤 앞에서부터 몇번째까지는 현금으로 주고 나머지에게 선물을 주는 식으로 계산을 할 수 있었다. 그리고 그 방식이 가능한 시점은 이분탐색으로 찾을 수 있다. 이렇게 구현했는데, 구현도 매끄럽게 안 되고 심지어 냈는데 한 번 틀리기까지 해서 이미 멘탈이 나갔다. B. Strange Definition 보자마자 소인수분해하고 각 소인수의 개수의 홀짝이 모두 같은 쌍이 인접한 거라는건 알았는데 일..