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$으로 이동하게 된다. 엄밀히 증명하진 않았지만 식의 선..
돈 셋 : IOI 2018 Day 2 ~10분 일단 모든 문제를 읽고, doll을 잡기로 결정했다. 84분 : doll 0점 doll을 계속 고민해봐도, 서브태스크 1, 2를 제외하고는 아무런 생각이 나지 않았다. 서브태스크 2의 구현마저도 엄청 복잡할 것 같았다. 그러다가 M=1인 서브태스크를 풀면 전체적인 감이 오지 않을까 하는 생각에 그걸 계속 고민했다. 스위치를 일렬로 늘어서게 하고 Y 방향을 트리거 쪽으로 오게 하는지 여부로 이진법 표현이 가능할 것 같았다. 그와 비슷한 형태를 계속 고민하다 예제가 나와서 제출했는데 0점을 받았다. 91분 : doll 2점 1시간 이상 고민했는데 소득이 없어서 일단 뭐라도 짜기로 했다. 서브태스크 1을 해결하고 2점을 받았다. 138분 : doll 20점 다시 ..
돈 셋: AGC034 A. Kenken Race C D인 경우로 나누어 풀 수 있다. 전자의 경우에는 A와 D 사이에 연속된 돌이 없는지만 확인해주면 된다. 후자의 경우에는 추가적으로 Snuke와 Fnuke가 순서를 바꿀 수 있는지를 체크해줘야 하는데, B와 D 사이에 연속된 3개의 칸이 모두 비어있을 경우 순서를 바꿀 수 있음을 관찰하면 된다. B. ABC ABC를 BCA로 바꾼다는 걸 약간 다르게 해석해 보면, 'A'와 'BC'가 자리를 바꾼다고 해석할 수 있다. 그러면 문제는 자리 바꾸기 횟수의 최댓값을 구하는 것으로 바뀐다. A의 개수를 누적해주면서 BC가 나올 때마다 그 값을 답에 누적시키고, A도 BC도 아닌 문자가 나오면 A의 개수를 0으로 초기화하는 작업을 반복하면 ..
문제셋: JOI Spring Training Camp/Qualifying Trial 2015/2016 Day 2 Employment 이런 유형의 문제를 예전에 고민해본 경험이 있어서 덕분에 거의 보자마자 풀이가 떠올랐다. 평가치가 높은 사원부터 고용한다고 생각해보면, i번째 사원이 고용될 때 i-1번째 사원과 i+1번째 사원이 이미 고용되어있었는지 아닌지 여부에 따라 그룹의 개수가 어떻게 변화하는지 알 수 있다. i번째 사원마다 그룹의 개수가 어떻게 변화하는지의 값을 C[i]라고 하자. 이제 펜윅 트리와 같은 구간합 자료구조를 통해서 평가치가 가장 높은 사원부터 고용되는 사원들 중 평가치가 가장 낮은 사원까지의 C[i]값을 더하면 그룹의 개수를 알 수 있다. i번째 사원의 평가치가 업데이트될 때 바뀔..