Codeforces #1012 Div.1
3줄 요약1. A, B1, B2, C1을 풀었다.2. 2850 퍼포가 나왔고, 레드를 가며 최대 레이팅 달성에 성공했다.3. 문제를 안 푼지 시간이 좀 되었는데, 꽤나 높은 퍼포먼스가 나와서 좋았다.서론3/23(일)에 Codeforces #1012 시험에 응시했다.전날에 버추얼을 돌았는데, 찐레드 퍼포가 나와서 이번 코포도 기대할만 하다고 생각했다.시험이 시작되었다.A(~0:05)A 문제를 읽었다.대충 n/2에 가장 가까운 소수 p를 잡고 p, p-1, p+1, p-2, p+2, ...을 출력하면 되는 문제였다.바로 맞았다.B1(~0:15)B1 문제를 읽었다.B[i]-A[i]의 누적합을 만들어서 적당히 스택으로 처리해줄 수 있었다.바로 맞았다.B2(~0:45)B2 문제를 읽었다.B1 문제와 비슷하게 하되..
2024 IOI 멘토교육 3주차
IOI 2023 Day 1을 돌았다.0:00 ~ 1:53(35 / 0 / 0 -> 35)1, 2, 3번 문제를 읽고 이해했다. 1, 2, 3번 문제가 모두 어려워 보였기 때문에 1번 문제부터 천천히 고민해보기 시작했다.1번 문제의 1, 2, 3번 섭테는 간단하게 해결할 수 있었고, 4번 섭테는 뭔가 더 아이디어가 필요할 것 같았다.X의 오른쪽, Y의 왼쪽으로 얼마나 갈 것인지를 $O(N^2)$으로 모든 경우를 다 해 보고, 각 경우를 $O(logN)$에 처리하면 될 것 같았다.각 경우에 대해서 선택해야 하는 값들을 작은 것부터 선택하는 그리디가 성립하기 때문에, 가장 작은 것 x개를 골랐을 때, 합이 K 이하가 되는 x의 최댓값을 구하면 된다. 이는 좌표 압축 + 세그먼트 트리로 구현할 수 있다.처음에는..
