TopCoder SRM 426

고수들이 하나둘씩 SRM을 시작하게 된 것인지 우리나라에 옐로우 레이팅을 가지신 분들이 늘어나고 있다. 오늘 SRM에는 우리나라에서 DIV1에 25명이 참가했다.

이번 문제들은 디스크립션을 이해하기가 참 난해했던 것 같다. 영어는 해석을 다 했으나 무슨말이지 잘 이해가 안되서 문제를 완전히 이해하는데 20분정도가 걸렸다. 문제를 이해하고 나니 쉬운 문제였는데 안타깝게도 점수는 이미 바닥을 향해 가고 있었다.

250문제는 간단한 시뮬레이션과 소팅을 결합해서 해결할 수 있는 문제였고 500은 터너리서치로 풀 수 있는 문제였다. 1000은 그래프이론을 적용해야 할 것 같은데 역시 잘 모르겠다.

신 petr가 상당히 부진한 모습을 보이며 62등을 했다

250 - Shuffling Machine

카드를 셔플링 하는 기계가 있는데 이 기계는 항상 같은 방법으로 카드를 섞는다. 벡터 shuffle이 이 기계가 카드를 섞는 방법을 나타낸다. 이 기계는 매 셔플마다 i번째 카드를 shuffle[i]로 옮긴다. 예를들어 {1, 0, 4, 3, 2}라는 벡터를 보면 이 기계는 0번째 카드를 1번째 위치로 옮기고, 1번 위치에 있는 카드를 0번으로, 2번 위치를 4번 위치로... 옮긴다. 기계는 1에서 maxShuffle 사이에서 랜던하게 수를 선택하여 그 횟수만큼 셔플을 한다.

플레이어는 셔플이 끝난 후 벡터 cardsReceived 에서 지정하는 위치에 있는 카드를 받게 된다. cardsReceived가 {0, 2, 6} 라면, 플레이어는 0번째, 2번째, 6번째에 위치한 카드를 받게된다. 이 플레이어는 기계가 항상 같은 방법으로 셔플을 하는 것을 이용하여 치팅을 하려 한다. 플레이어는 셔플이 시작되기 전에 자기가 받고 싶은 K장의 카드의 위치를 선택할 수 있다. 셔플이 완료된 후 플레이어가 받고 싶어 했던 K장의 카드 중 플레이어가 받을 수 있는 카드를 최대로 하려고 할 때 예상되는 카드의 장수를 리턴하라.

디스크립션을 이해하기가 쉽지가 않다.

M장의 카드가 있으면 각각의 카드의 초기위치는 (0, 1, 2, ... , M-1) 이다.
이 카드를 shuffle 법칙대로 기계가 섞었을 때 초기의 카드가 어느 위치로 이동했는지는 구해볼 수 있다.
기계가 1회 shuffle을 하는 경우, 카드가 이동할 위치를 계산하고 cardsReceived에 해당하는 초기위치를 카운트 한다.
기계가 2회 shuffle을 하는 경우, 마찬가지로 카드가 이동할 위치를 계산하고 받을 카드를 카운트 한다.
이 과정을 maxShuffle까지 반복한 다음 카운트된 결과를 maxShuffle로 나누어 각 초기위치마다 카드를 받게될 예상횟수를 알 수 있다.

플레이어는 K장의 카드를 받기를 원하므로 카드를 받게될 예상횟수가 가장 높은 K개의 위치에 자신이 원하는 카드를 집어 넣는것이 이득이다.

문제에서 요구하는 답은 예상되는 카드의 갯수 이므로 예상횟수가 가장 높은 K개의 위치에 대해 그 예상횟수를 모두 더한 값이된다.
double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K) { int i,j,k; int n = shuffle.size(); vector<int> cards(n), recv(n); // 초기 카드의 위치 for (i = 0; i < n; i++) cards[i] = i; // maxShuffle번 까지 카드를 섞는다. for (i = 0; i < maxShuffles; i++) { // 카드를 섞고난 후 카드 위치 vector<int> newcards = cards; // 카드를 shuffle for (j = 0; j < n; j++) { newcards[shuffle[j]] = cards[j]; } // 플레이어가 받을 카드를 카운트 cards = newcards; for (j = 0; j < cardsReceived.size(); j++) { recv[cards[cardsReceived[j]]]++; } } // 내림차순으로 소팅 int sum = 0; sort(recv.rbegin(), recv.rend()); // 기대치가 가장 높은 K장의 카드의 기대치를 모두 더한다. for (i = 0; i < K; i++) sum += recv[i]; // maxShuffles로 나누어 리턴 return (double)sum / maxShuffles; }

500 - Catch The Mice

"Catch The Mice" 라는 게임기가 있다. 이 게임기 안에는 장난감 쥐들이 돌아다니고 있다. 플레이어는 우리(cage)를 이동시켜 어느 순간 버튼을 눌러 cage를 떨어뜨려 cage안에 있는 쥐들을 잡을 수 있다.

쥐들은 2차원 평면상을 이동하고 이 평면은 무한히 크다고 가정해도 좋다. cage는 L*L크기의 정사각형이고 cage의 각 모서리는 축에 평행하다. 게임기의 주인은 플레이어가 cage안에 모든 쥐를 다 잡으면 스포츠카를 준다고 했지만 사실은 절대로 그런일이 발생하기를 원하지 않는다.

쥐들의 초기좌표(xp,yp)와 속도(xv,yv)가 주어졌을 때 절대로 모든쥐를 절대로 한번에 못잡게 하는 최대의 cage의 크기 L을 구하라. L의 경계에 걸린 쥐는 잡지 못한것으로 처리된다.

시간 t에서 쥐의 좌표는 (xp + xv * t, yp + yv * t) 이다.

두 쥐가 있을 때 t가 변함에 따라 두 쥐를 한번에 못잡게 하는 L은 아래 그래프같은 모양이 된다.

문제는 두 쥐사가 아니라 모든 쥐를 한번에 못잡게 해야 하므로 모든 쥐의 쌍에대해 그래프를 그려야 한다.
그 그래프는 아래와 같은 모양이 된다.

위의 그래프에서 t가 변함에 따라 모든쥐를 한번에 못잡게 하는 최대의 L도 변하게 된다. 그 중 L이 최소가 될때가 이 문제가 요구하는 정답이 된다.

문제는 저 최소점을 어떻게 구하느냐인데 L의 그래프를 살펴보면 최소점을 기준으로 왼쪽은 감소 오른쪽은 증가한다는 것을 알 수 있다. 이런 특징이 우연히 나온 것인지 아니면 모든 경우에 그런것인지를 생각해보면, 쥐들의 벡터가 어떤식으로 주어지든지 간에 모든경우에 이런 특징이 성립할것이라는 것을 예상할 수 있다.(증명은 못하겠다.;;)

그렇다면 터너리서치(Ternary Search)를 이용하여 답을 구할 수 있다.
2008/11/24 - [Study/Computer Science] - Ternary Search
// 시간 t에서 모든 쥐를 한번에 잡지 못하게 하는 거리 L을 구한다. pair<double, pair<int, int> > func(vector <int>& xp, vector <int>& yp, vector <int>& xv, vector <int>& yv, double t) { int i, j, n = xp.size(); double x1, y1, x2, y2; double maxdist = 0; int a,b; for (i = 0; i < n; i++) { x1 = xp[i] + xv[i]*t; y1 = yp[i] + yv[i]*t; for (j = i+1; j < n; j++) { x2 = xp[j] + xv[j]*t; y2 = yp[j] + yv[j]*t; double dist = MAX(abs(x1-x2), abs(y1-y2)); if (dist > maxdist) { maxdist = dist; a = i; b = j; } } } return make_pair(maxdist, make_pair(a, b)); } double largestCage(vector <int> xp, vector <int> yp, vector <int> xv, vector <int> yv) { int i,j,k; double left = 0; double right = 10000; double tl, tr, mindist; // 터너리서치 for (i = 0; i < 10000; i++) { tl = (left*2 + right) / 3; tr = (left + right*2) / 3; pair<double, pair<int, int> > a, b, c, d; a = func(xp, yp, xv, yv, left); b = func(xp, yp, xv, yv, tl); c = func(xp, yp, xv, yv, tr); d = func(xp, yp, xv, yv, right); mindist = b.first; if (a.first == b.first) left = tl; else if (c.first == d.first) right = tr; else { if (b.first > c.first) left = tl; else right = tr; } } return mindist; }

1000 - Long Straight Road

페트르 신도 틀렸는데..;;