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] > ..

0. 표지 1. boxes 문제: 최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 ..

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다. 이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다. 출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다. 원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다. 관련 자료들은 여기에서 다운받을 수 있다. 1. search 문제: 정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통..