[SRM 456] 2009년 마지막 SRM

Problem Solving/TopCoder logs 2009. 12. 23. 20:59
오늘 아침 11시 2009년의 마지막 SRM 이 열렸다..
비록 챌을 실패해서 좀 아쉽게 됐지만.. 나름 문제이해를 빨리해서 rating 을 48 점이나 올렸다..
내년에는 좀더 도전적인 문제를 많이 풀어서 yellow 로 올라가야겠다..





Level1 - SilverDistance
chess 판에서 unit 은 그림과 같이 5 방향으로 이동할 수 있다.. (sx, sy) -> (gx, gy) 로 이동하는 최단거리 구하기..

문제가 약간 tricky 해서 if 문으로 다 나눠서 생각하려하는데.. 자세히 보니 경우의 수가 두가지밖에 없다..
|sx-gx| 와 |sy-gy| 의 parity 가 같으면 돌아가는 길 없이 바로 갈 수 있다..
그렇지 않은 경우는 반드시 (0, +1) 방향으로 한번 이동해야한다..
언제 이동하는 것은 상관 없으므로 나는 그냥 (gx, gy-1) 까지의 거리를 구하고 1 을 더했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 #define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10
 11 class SilverDistance {
 12 public:
 13
 14 int minSteps(int sx, int sy, int gx, int gy)
 15 {
 16     int dx, dy;
 17     int res;
 18     dx = abs(sx-gx);
 19     dy = abs(sy-gy);
 20     if (dx % 2 == 0 && dy % 2 == 0) {
 21         res = max(dx, dy);
 22     }
 23     else if (dx % 2 == 0 && dy % 2 == 1) {
 24         res = minSteps(sx, sy, gx, gy-1) + 1;
 25     }
 26     else if (dx % 2 == 1 && dy % 2 == 0) {
 27         res = minSteps(sx, sy, gx, gy-1) + 1;
 28     }
 29     else {
 30         res = max(dx, dy);
 31     }
 32     return res;
 33 }
 34
 35 };



Level2 - CutSticks
막대기가 여러개있는데.. 최대 C번까지 cut 을 할 수 있다.. K번째 긴 막대기의 길이를 최대화하기..

일단 문제부터 잘 이해가 안되는 문제.. -_-;;
일단 전형적인 binary search 문제인데 조건이 하나 더 추가되면서 상당히 까다로워진 문제..
editorial 을 보고 풀었다..

binary search 를 이용해 답을 계속 탐색하는데.. 다음 두가지 조건을 만족하면 valid 이다

1) 길이가 최소 mid 인 막대기를 만든다 치면.. 각 막대기를 floor(stick[i] / mid) 개로 만들 수 있다..
따라서 sum{i=1...n} floor(stick[i] / mid) >= K

2) 최대 c 번만 cut 할 수 있다.. 한번 cut 하면 막대기가 하나 더 생기므로..
이미 mid 보다 긴 막대기 수 + c >= K

아... 어렵다.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 class CutSticks {
 13 public:
 14
 15 double maxKth(vector <int> sticks, int C, int K)
 16 {
 17     int n;
 18     int iter, i;
 19     long long a, b;
 20     double l, r, mid;
 21     l = 0;
 22     r = 1000000000.0;
 23     iter = 300;
 24     n = sticks.size();
 25     while (iter--) {
 26         mid = (l+r) * 0.5;
 27         a = b = 0;
 28         for (i = 0; i < n; i++) {
 29             a += (long long)((double)sticks[i] / mid);
 30             if ((double)sticks[i] >= mid)
 31                 b++;
 32         }
 33         if (a >= K && b + C >= K)
 34             l = mid;
 35         else
 36             r = mid;
 37     }
 38     return mid;
 39 }
 40
 41 };



Level3 - FunctionalEquation


to be updated..




'Problem Solving > TopCoder logs' 카테고리의 다른 글

SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20
TopCoder SRM 458 Div 1  (0) 2010.01.17
TopCoder SRM 457 Div 1  (0) 2010.01.06
TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07
TopCoder SRM 453.5 (??) Div 1  (0) 2009.11.26
[SRM 453] 탑코더 아레나 폭발 -> unrated event  (4) 2009.11.18
TopCoder SRM 450 Div 1  (0) 2009.10.19
  • By helloneo

to Top

티스토리툴바