PS 이야기

금년도 IOI에서 한국대표팀이 금메달 2개, 은메달 2개로 2009년 이후로 좋은 성적을 받았다. IOI2010부터 채점 환경이 갑작스레 바뀌게 되고 자연스럽게 출제할 수 있는 문제의 종류도 다양해졌다. 때문에 우리나라 선수들은 익숙치 못한 환경에 적응을 못하게 되었고 빛을 보기까지 3년정도가 걸린 셈이다.사실 문제 유형이 바뀌어 시험을 못보았다는 것은 핑계거리일 수 있다. 모두가 동일하게 변함을 맞이했고, 충분히 금메달을 받을 수 있는 교육을 받았기 때문이다. 특히, 미국팀이 성적이 엄청 좋았었는데, 그들이 많이 신기했었다. 그래도 코딩 정확성을 기준으로 연습했던 나에게는 큰 타격이었다.내가 2010년, 2011년 두 번 나갔을 때 모두 성적이 떨어지고 있을 때라... 이번 한국대표 선수들이 더 자랑스..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game - KOR (ko).pdf 영문: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game.pdf이 문제는 전형적인 2차원 Segment Tree 문제다.흔히들 알고 있는 Indexed tree로 이 문제를 풀 경우 $R$ 값이 매우 커 배열을 잡을 수 없지만, top-down 방식을 이용하는 segment tree를 이용하면 된다. 이 문제는 online 방식으로 이후 데이터가 어떻게 들어올지 전혀 예측하지 못한 채로 함수를 코딩해야 되기 때문에 re-indexing 혹은 re-numbering 을 할 수 없다. 불가피하게 seg..

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/robots/robots - KOR (ko).pdf이분검색으로 미리 답을 정해놓은 뒤 그리디를 통해 답이 되는지 확인하는 방법을 사용한다. 이런 테크닉은 파라매트릭 서치(Parametric Search)로 알려져 있다.만약 로봇의 종류가 한 가지라면 매우 쉽게 풀릴 것이다. 하지만, 로봇의 종류가 2 종류 (연약한 로봇, 작은 로봇)이라 생각하기 많이 까다로울 수 있다.답을 $m$ 이라 가정했다는 것은 각 로봇은 최대 $m$ 개의 장난감을 운반할 수 있다는 것이다. 먼저 연약한 로봇들이 연약한 순서대로 자신이 가져갈 수 있는 가장 '크기'가 큰 장난감들을 $m$개 운반한다. 만약 가져갈 수 있는 장난감이..