3개의 댓글이 있습니다.
-
-
일루 -
저도 최적화 종류의 문제가 IOI에 나오는 것은 반대입니다. 풀이 과정에 알고리즘 말고 다른 요소들도 개입하기 때문에, 대회의 의도와는 좀 다른 유형의 문제가 아닌가 합니다. 제대로 풀기에는 시간이 너무 부족하기도 합니다. Interactive의 경우에는 나올 수 있다고 생각합니다.
그러나 다른 문제들의 성적과 이런 유형의 문제들의 성적은 거의 정비례하는 모습을 보여주었고, 이 때문에 이슈가 발생한 것도 없으므로, 내년에도 이 체제가 유지될 가능성이 어느 정도 있다고 생각합니다. 어느 정도 준비해두는 것도 좋겠지요.
내년에는 한달 전에 나오는 IOI rules (시기상 KOI 전입니다) 를 참고할 필요가 있겠습니다. 예고된 사항에 준비가 좀 덜 된듯한 느낌이었습니다.
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
일루
이번에 IOI를 나간 학생들과 미래에 이러한 문제를 접할 가능성이 있는 KOI나 IOI를 준비하는 학생들에게 도움이 되기를 바라면서 이 글을 씁니다.
Maze 문제 링크는 여기입니다: http://plg1.cs.uwaterloo.ca/~gvcormac/day2task3/
IOI는 5시간 4문제인데다가, 비교적 쉬운 2문제를 1시간 정도에 해결하고 다른 한 문제를 1시간 30분 정도 시간을 들여 풀거나 못풀거나 한다고 보면, 이 문제에 할애할 수 있는 시간은 겨우 2시간 30분입니다.
이 시간 안에 MM의 대원칙중 하나인 Iterative development - 시도해보고 거기서 교훈을 얻어서 고쳐보거나 다른걸 시도해보고 blah blah... - 를 적용하기 위해서는, 첫 접근이 아주 아주 단순해야 합니다.
1 - 일단 점 하나는 엣지에 있어야 하므로, 이 점들 중 하나를 랜덤하게 정합니다. 그리고 랜덤하게 상하좌우 중 하나를 선택해서 계속 움직이다가 더이상 이동이 불가능하면 그것이 답이 되겠죠. (사실 반대편에서 시작하는게 더 좋은거 같은데 이러면 나온 path가 답이 아닐 확률이 높으므로 이걸 처리하기 많이 귀찮아 보이니 걍 원래대로 합시다)
이렇게 짜면 누구나 예상하겠지만 로컬에서 한번 꼬이면 망하므로... 최적해는 커녕 반의 반도 안될 것이므로, 0점에 한없이 가까운 답이 나옵니다.
그러나 여기서 멈추면 MMer의 자세가 아니죠. 이제부터 iteration이 시작입니다.
2 - 이제 현재 만들어진 path에서 랜덤하게 한 점을 잡아서 그 지점 뒤는 모두 지우고, 거기서부터 새로 상하좌우 랜덤운동을 시작해서 또다시 막다른 길로 갑니다. 이렇게 해서 길이가 길어지거나 같으면 선택하고, 그렇지 않으면 버립니다.
이렇게 하면 좀 더 결과가 좋아지지만, 그래도 0점에 한없이 가깝습니다. 이유를 좀 볼 필요가 있겠죠.
보아하니, 처음부분에서 어느정도 부분까지는 완전 crude하게 대충 빨리 빨리 가는데, 거의 끝부분에서만 최적화가 되어있습니다. 이러면 중간에서 끊고 랜덤하게 움직인 새 솔루션이 기존 솔루션보다 좋아질 확률은 거의 없겠죠.
이런 경우를 해결하려면? 중간 부분을 잘라서 새 path로 갈아끼워야 하겠습니다. 기본적인 아이디어는, 직선으로 연결되어 있는 부분을 꼬불꼬불하게 바꾼다는 것입니다.
이걸 사람이 하게 하려면 밑도 끝도 없고 또한 IOI는 시간도 없으므로 우리는 컴퓨터의 곰같은 힘(=brute force) 를 믿어야 합니다. 다음과 같이...
3 - 현재 path에서 임의의 두 점을 잡습니다. 이 두 점 사이의 path를 없애고, 첫 점에서 두번째 점까지의 길을 새로이 연결합니다. 경향성 같은건 없고 첫 점에서 시작해서 상하좌우로 랜덤하게 움직이다가 두번째 점을 만나서 길이가 늘어나거나 같으면 선택하고, 짧아지거나 만나지 못하면 버립니다.
이 두 점 사이의 길이가 길면 랜덤 경로가 두번째 점을 잘 찾아갈 확률이 기하급수적으로 낮아질 것 같으므로, 두 점 사이의 거리는 최대 20이 되도록 합니다.
아까의 특정 지점부터 path 새로 구하기 루틴과 이 루틴을 결합하자 첫번째 루틴에서는 없던 길을 만들어가고 두번째 루틴에서는 현재 경로를 최적화해 나가면서 시너지효과가 납니다. 답이 최적해 근처로 급격히 증가하기 시작합니다..
초기 시작점과 경로의 움직임에 따라서 결과가 크게 달라지니, 각 경우에 대해서 대략 50~100번 정도 돌려서 그 중의 최적해를 구하자, 실제 대회 점수로 환산했을 때 대략 93~94점 정도의 점수가 나왔습니다. 실제 대회 1등은 89점이었으니, 꽤 괜찮은 점수라고 할 수 있겠죠.
http://codepaste.net/ucq95k 에 코드가 있습니다.
코딩과 테스트 시간을 합쳐서 대략 3시간 30분 정도 소모되었습니다. 보시면 아시겠지만 로직 구성 등 사람이 하는 일은 최소화했고 왠만한건 컴퓨터에게 맡겼습니다. 실제 대회라면, 이 문제부터 건드려서 대략 로직을 업데이트해가면서 로컬 테스트를 돌리는 동안 다른 문제를 해결하면 될 것 같습니다.
올해 대회에 큰 영향력을 가졌던 코맥씨가 내년 대회에도 영향을 미칠 것 같으니 이런 종류의 문제는 내년에도 계속 나올 확률이 높아보입니다. Interactive Interface를 사용하는 문제들도 나오겠지요. KOI는 항상 IOI 경향을 쫓아갔으니 내년 KOI도 어떻게 해서든 올해 IOI 스타일로 바뀌지 않을까 싶습니다.
추가적으로 연습을 해보실 분들은 Topcoder Marathon Match(http://www.topcoder.com/longcontest)를 해 보시는 것이 큰 도움이 됩니다. Interactive한 문제들도 많이 있고 최적화 문제도 많이 있으며 둘을 합친 문제도 많이 있습니다. :)
13년 전