https://codeforces.com/contest/1284 A. New Year and Naming 한국인이라서 문제 안 읽고 예제만 본 다음에 풀었다. ㅋㅋㅋ $A_{(y-1) \mod n} + B_{(y-1) \mod m}$을 출력하면 된다. B. New Year and Ascent Sequence Ascent가 없는 수열들을 개수를 세면 더 쉽다. 수열 자체에 Ascent가 있는 수열은 걸러내고, Ascent가 없다면 그 수열은 최댓값과 최솟값만 중요하다는 것을 알 수 있다. $\min s_i \geq \max s_j$인 (i, j) 쌍의 수를 세면 되는데, 이는 부분합 배열을 사용하면 해결할 수 있다. C. New Year and Permutation [l, l+c]를 수의 범위로 가지는 f..
JOI 2016 오렌지 출하 $D_i =$ (1~i번째 오렌지까지 어떻게 상자에 넣을지 배정했을 때 최솟값)이라고 정의하면, $O(NM)$ DP로 해결할 수 있다. 스탬프 수집 일단 JOI를 모을 수 있는 경우의 수를 구하는 방법을 생각해 보자. $J_i =$ (1~i번째 가게 중 J 스탬프를 주는 가게 수)로 정의하고, $I_i =$ (i~N번째 가게 중 I 스탬프를 주는 가게 수)로 정의하자. 그러면 경우의 수는 $S_i =$ 'O'를 만족하는 i들에 대해 $J_i*I_i$를 모두 더한 것이 된다. 가게를 추가할 때 스탬프 J를 주는 가게를 추가한다면, 입구에 설치하는 게 이득이고, 스탬프 I를 주는 가게를 추가한다면 출구에 설치하는 게 이득이다. 스탬프 O를 주는 가게를 추가한다면 $J_i*I_i$..
AGC006 A - Prefix and Suffix $O(N^2)$으로 일일이 비교해주고 |S| + |T| - (가장 길게 겹치는 길이)가 답이 된다. B - Median Pyramid Easy 어느 시점에 같은 수가 연속으로 있게 되면 그 두 수는 피라미드 끝까지 그 위치에 그대로 남아있게 됨을 관찰할 수 있다. 이걸 이용해서 (..., x-1, x, x+1 x-2, ...) 혹은 (..., x+1, x, x-1, x+2) 등의 형태를 만들어주면 피라미드의 윗줄에 x가 두 번 연속으로 존재하게 된다. C - Rabbit Exercise $x_i$에 위치한 토끼가 점프를 하면 이 토끼는 $2x_{i-1} - x_i$ 혹은 $2x_{i+1} - x_i$으로 이동하게 된다. 엄밀히 증명하진 않았지만 식의 선..