PS 이야기

0. 표지 1. horses 문제: 말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i < j$인 모든 $j$에 대해 $Y[i] \geq X[i+1] \times \dots \times X[j] \times Y[j]$ 를 만족해야한다. 여기서 주목해야할 점은 $Y[i] \leq 10^9$라는 것이다. $X[i] > 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ ..

0. 표지 1. boxes 문제: 최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 좌표와 양수 좌표를 나누어 생각할 수 있다. 결국 선형인 경우에 대해 욕심쟁이 기법으로 답을 전부 구해놓은 뒤, 모든 지점에 대해 끊어 선형으로 바꾼 뒤 답을 계산하면 된다. 선형일 때 주의해야할 점은 K개의 지점에 선물을 나누어주고 다시 0번 지점으로 돌아가는 경로는 원형에서 이루어지는게 ..

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다. 이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다. 출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다. 원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다. 관련 자료들은 여기에서 다운받을 수 있다. 1. search 문제: 정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다. #include "graderlib.h" int find(int sub, int N, int X) { int s = 0, e = N-1, t; whil..