PS 이야기

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