PS 이야기

Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다. $S_i = \sum_{k=1}^{i} x_k$ 를 정의하자. 단, $S_0 = 0$ DP 배열을 아래와 같이 정의한다. $D_i$ = 1번부터 $i$번 병사까지 특공대를 나눌 때 전투력 합의 최대값. 단, $D_0 = 0$ 이 때, 점화식은 아래와 같이 된다. $D_i = \max(D[j] + A(S_i-S_j)^2 ..

0. 문제 패키지 1. paint 길이가 $n$인 문자열이 있고 각 문자는 'X'혹은 '_'이다. 연속한 'X'끼리 묶어 블록이라 부르고, 총 $k$개의 블록이 있다. 문자열의 전체가 주어지지 않고 일부만 주어진다. 그리고 블록의 개수 $k$와 왼쪽부터 순서대로 블록들의 크기가 길이 $k$인 정수배열로 주어진다. 이 때 가능한 문자열이 여러 개가 있을 수 있는데, 가능한 모든 문자열에 대해서 항상 'X'가 놓이는 위치, 그리고 항상 '_'가 놓이는 위치를 구하는 문제다. 모든 위치에 대해서 '_'를 놓을 수 있는지, 'X'를 놓을 수 있는지를 나눠서 계산하면 된다. 아래와 같은 세 개의 DP 배열을 계산해놓으면 편하다.D[i][j] = 1번 블록부터 i번 블록을 1번째 문자부터 j번째 문자까지의 부분 문..

0. 문제 패키지 1. molecules $n$개의 자연수로 이루어진 집합 $S$가 있다. 한 집합 안에 같은 수가 여러 개 있을 수 있다. 이 때, 속한 원소의 합이 $l$이상 $u$이하가 되는 부분집합을 찾는 문제다. 이 문제에서 중요한 조건은 $u-l \geq \max(S) - \min(S)$이다. 부분집합의 크기 $k$를 정했을 때, 부분집합 원소 합의 최소값을 $s_k$, 부분집합 원소 합의 최대값을 $e_k$라고 하자. $[s_k, e_k]$와 $[l, u]$가 겹치는 것과 속한 원소의 합이 $l$이상 $u$이하가 되는 크기가 $k$인 부분집합이 존재하는 것은 필요충분조건이다. 왜냐하면 $u-l \geq \max(S) - \min(S)$이기 때문이다. 이에 대한 증명은 어렵지 않다. 위와 같은..