klimmek55

예선 후기는 stonejjun 블로그에서 볼 수 있다. 우선 대회 당일에 우여곡절이 정말 많았다. 대회 장소에 문제가 생겨서 세팅하기에도 바빴는데 프린터도 고장나서 그냥 노트북으로 순서대로 같이 읽기 시작했다. A는 지문이 너무 길기도 하고 딱 봐도 처음 풀 문제는 아닌 것 같아서 B로 넘어갔다. 모든 색깔이 다 포함되는걸 무지개라고 하고, 두 겹인걸 찾으면 된다는 것까지는 이해했는데, 끝날 때까지 \(P\)도 임의로 정하고 \(P'\)도 임의로 정하는걸로 이해하고 있었다. 근데 stonejjun이 풀 수 있다고 해서 풀고 있었다. 이 쯤에 아마 프린터가 고쳐져서 문제를 뽑다가 다시 고장났다. 그래도 어찌저찌 앞 부분 문제는 볼 수 있었다. C는 그냥 시뮬레이션이었고 B도 코딩이 잠깐 막혀있어서 일단 내..

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'\)인..

Educational Codeforces Round 103 (Rated for Div. 2) A. K-divisible sum \(n\ge k\)일 때는 \(1\) 또는 \(2\)만으로 \(k\)로 나누어 떨어지는 합을 만들 수 있다. \(n

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) A. Strange Birthday Party 처음엔 감도 안 잡혀서 포기할까 생각하다가 조금 더 고민해보니 \(c\)를 기준으로 이분탐색할 수 있다고 생각했는데 그렇게 거의 다 짜고난 뒤에 안 된다는걸 깨달았다. 그래서 더 고민해보니 \(k\)를 기준으로 정렬한 뒤 앞에서부터 몇번째까지는 현금으로 주고 나머지에게 선물을 주는 식으로 계산을 할 수 있었다. 그리고 그 방식이 가능한 시점은 이분탐색으로 찾을 수 있다. 이렇게 구현했는데, 구현도 매끄럽게 안 되고 심지어 냈는데 한 번 틀리기까지 해서 이미 멘탈이 나갔다. B. Strange Definition 보자마자 소인수분해하고 각 소인수의 개수의 홀짝이 모두 같은 쌍이 인접한 거라는건 알았는데 일..

AtCoder Beginner Contest 187 E. Through Path 우선 \(1\)번 쿼리와 \(2\)번 쿼리는 \(a\)와 \(b\)만 바뀐거니 \(1\)번 쿼리를 기준으로 생각할 수 있다. 일단 아무 노드나 루트 노드로 잡아서 트리를 만든다. 만약 \(a\)가 \(b\)의 자식노드라면, \(a\)의 서브트리 내의 모든 노드에 \(x\)를 더하면 된다. 만약 \(a\)가 \(b\)의 부모노드라면, \(a\)의 서브트리를 제외한 모든 노드에 \(x\)를 더하면 된다. 그리고 이 작업은 lazy propagation을 하듯이 각 노드에 자신의 서브트리에 더해야될 값을 저장해둔 뒤 모든 쿼리가 끝난 후 계산을 해주면 된다. F. Close Group 일단 \(N\)이 엄청 작다. 처음엔 \(9!..

작년 KOI에서 은상을 타서 올해는 APIO를 나갈 수 있었다. 대회 일주일 정도 전부터 예전 APIO 문제들을 좀 보긴 했는데... 진짜 풀기는 커녕 부분점수도 못 받을 것 같은 문제들이 많았다. 어떤 해는 세 문제 중에 하나도 엄두가 안 나고, 어떤 해는 그래도 한 문제 정도는 풀만하기도 한걸 보면 난이도가 좀 오락가락 하나보다. 그리고 대회 때 비주얼스튜디오를 써야한다고 했는데 나는 비주얼스튜디오밖에 쓸 줄 몰라서 오히려 좋았다. 1. 이상한 기계 처음엔 보자마자 대체 뭔 소리인지 이해가 안 돼서 일단 다른 문제들부터 다 읽었다. 근데 다른 문제들이 더 멀어보여서 다시 이 문제로 돌아왔다. 일단, 주어진 구간들이 겹칠 수 있다. 그러므로 라인 스위핑을 써서 합쳐야되긴 할 것 같다. 그런데 그건 부가..

AtCoder Beginner Contest 120 A - Favorite Sound 문제 설명대로, \(\min (\lfloor \frac{b}{a} \rfloor,c)\)를 출력하면 된다.12345678910#include int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); printf("%d", std::min(b / a, c)); return 0;}Colored by Color Scriptercs B - K-th Common Divisor \(\max (a,b)\)부터 공약수를 세서 \(K\)번째 공약수를 출력하면 된다.1234567891011121314151617181920#include int main() { int a, b, k; scanf(..