겨울방학 SRM 모임 연습으로, JongMan, domeng, altertain, ryuwonha, xhae 다섯 명이 참가했습니다.
노가다 구현 500 과 후덜덜한 기하 1000, 그리고 노가다나 적절한 센스로 풀리는 250 으로 구성된 셋이었고요. 결과는 http://spreadsheets.google.com/pub?key=prOLhYJ-PdsL_svuPcyB3Pw&gid=0 에서 볼 수 있습니다. (태윤님 근데 저 M 좀 대문자로 바꿔주세요.. -_-)
250 - ElevatorLimit
Key Insight
physicalLimit * n <= 5000
해법
모든 문제에서 가장 먼저 확인해야 할 것은, 가장 무식한 방법으로도 문제를 풀 수 있는가입니다. 시간 안에만 들어간다면, 가장 무식하고 가장 작성하기 편한 해법이 가장 좋은 해법이죠. ^ 그래서, 처음에 0 명이 있었을 경우부터 physicalLimit 명이 있었을 경우까지의 모든 시나리오를 모두 시뮬레이션하면서 오류가 있는 경우를 제외하면 쉽게 답을 구할 수 있습니다.
오류가 있는 경우란: exit[i] 명이 나갔는데 엘리베이터에 음수명이 있을 경우와, enter[i] 명이 탔는데 physicalLimit 명을 초과하는 경우겠지요.
그 외 O(n) 해법도 있습니다. 처음에 0 명이 있다고 가정하고 쭉 시뮬레이션을 한 뒤 (오류 무시하고) 한 시점에 엘리베이터에 있었던 최소 인원수 A 와 최대 인원수 B 를 각각 기록합니다. 그러면, A <= 0 이겠는데, 이 때 처음 엘리베이터에서는 -A 명에서 physicalLimit - B 명까지 존재할 수 있었겠죠. 물론, 이 때는 각종 예외들을 처리해 줘야 하므로 검증이 좀 더 어렵다는 문제가 있죠. (실제로 r모 레드님은 이걸로 챌린지.)
소스코드 나갑니다.
~~~ cpp
struct ElevatorLimit
{
vector getRange(vector enter, vector exit, int physicalLimit)
{
int mini = physicalLimit + 1;
int maxi = -1;
for(int begin = 0; begin <= physicalLimit; ++begin)
{
int current = begin;
bool valid = true;
for(int i = 0; i < enter.size(); ++i)
{
if(current < exit[i]) { valid = false; break; }
current -= exit[i];
current += enter[i];
if(current > physicalLimit) { valid = false; break; }
}
if(valid)
{
mini = min(mini, begin);
maxi = begin;
}
}
if(maxi == -1) return vector();
vector ret(2);
ret[0] = mini;
ret[1] = maxi;
return ret;
}
};
500 - RPGRobot
아, 문제 조낸 기네여.. 사실 알고 보면 문제는 단순합니다.
Key Insight
width * height * length(moves) 해봐야 얼마 안되는구나.
해법
넵 역시 닥치고 시뮬레이션입니다. 가장 간단한 방법은 각 위치에 대해서 이 위치에서 주어진 movement 를 할 수 있나 같은 함수를 만들어서 순서대로 호출하는 겁니다. 그 안에선 간단한 시뮬레이션을 하면서 현재 위치의 상하좌우에 벽이 있는지 여부가 기록과 맞는지를 비교하면 되죠.
큐를 만들어서 모든 초기상태를 집어넣고, 큐가 빌 때까지 탐색한다 (altertain, ryuwonha) .. 이런 것도 때깔나지만 좀 오버킬이라고 할 수 있습니다.
그 외 파싱도 좀 귀찮습니다. 이런 데서는 깔끔하게 짜는 능력이 다른 무엇보다 중요하죠. 자기가 작성한 코드가 한 번에 동작할 수 있도록 연습하는 게 좋겠네연. 'ㅅ'
제 코드 나갑니다. (출력 순서를 y좌표-x좌표로 해서 틀린 비운의..)
~~~ cpp
struct RPGRobot
{
int width, height;
vector m;
void assertWall(int y, int x, bool isWall)
{
if(y < 0 || x < 0 || y >= m.size() || x >= m[0].size()) return;
bool itsWall = (m[y][x] != ' ');
if(itsWall != isWall) throw 1;
}
bool isValid(int y, int x, const vector >& mv)
{
try
{
for(int i = 0; i < mv.size(); ++i)
{
assertWall(y*2+1-1, x*2+1 , count(all(mv[i].first), 'N') == 0);
assertWall(y*2+1+1, x*2+1 , count(all(mv[i].first), 'S') == 0);
assertWall(y*2+1 , x*2+1+1, count(all(mv[i].first), 'E') == 0);
assertWall(y*2+1 , x*2+1-1, count(all(mv[i].first), 'W') == 0);
char dir = mv[i].second[0];
if(dir == 'N') --y;
if(dir == 'S') ++y;
if(dir == 'E') ++x;
if(dir == 'W') --x;
}
}
catch(int x)
{
return false;
}
return true;
}
vector where(vector map, string movements)
{
m = map;
height = m.size() / 2;
width = m[0].size() / 2;
vector > mv;
istringstream inp(movements);
string tok;
while(inp >> tok)
{
tok += ",-";
replace(tok.begin(), tok.end(), ',', ' ');
istringstream inp2(tok);
string first, second;
inp2 >> first >> second;
mv.push_back(make_pair(first, second));
}
vector ret;
for(int j = 0; j < width; ++j)
for(int i = 0; i < height; ++i)
if(isValid(i, j, mv))
{
char buf[64];
sprintf(buf, "%d,%d", 2*j+1, 2*i+1);
ret.pb(buf);
}
return ret;
}
};
1000 - DogWoods
아 문제 완전 안드로 -_-;;; 딴 거 볼 것 없이 1번 예제에 딸려오는 그림을 보시면 문제가 이해가 갈 겁니다.
Key Insight
볼 거 없이 시뮬레이션이구나
해법
넵 역시 닥치고 시뮬레이션 + 기하입니다. 이 셋 세터가 누군지.. 하악 어쨌든 적절한 가정과 코딩을 통해서 해야 하는 코딩의 양을 많이 줄일 수 있습니다. 일단, 원점을 중심으로 하는 원과 다른 원의 교차점을 구하는 식이 주어진다는 것은 좀 다행이죠. 이걸 이용해서 시뮬레이션을 하려면 다음과 같은 단계가 필요할 겁니다.
* R = 현재 위치와 원점과의 거리
* 원점을 중심으로 하고 반지름이 R 인 원과 교차하는 모든 나무들을 찾는다
* 없으면 -1 리턴
* 시계 방향으로 달렸을 때 처음 만나는 점을 찾는다
* 이 나무를 타고 반시계 방향으로 내려갈 것인데
* 이 나무가 원점을 중심으로 하고 반지름이 10 인 원과 교차한다면, 반시계 방향으로 달리다 숲의 중심에 도달
* 안 교차 한다면, 원점과 가장 가까운 점까지 달려내려간 후 맨 위로 돌아감
하악.. 뭐 말이 쉽지 좀 안드로메다죠. 적절한 코딩을 통해서 이 모든 것을 극복해야 합니다. 이런 경우 효율적으로 코딩을 하려면 점이나 원 등의 기본적인 primitive 들을 클래스화하는 것이 좋습니다. 예를 들어, 내가 나무 A 에 부딪혀서 원점과 가장 가까운 점까지 달려내려가려는데, 이 점의 위치를 구한다고 합시다. 덧셈, 뺄셈, 곱셈과 길이 구하기 등이 적절히 구현된 벡터 클래스를 가지고 있다면
double a = A.center().norm(); // 원점에서 A의 중심까지의 거리
double b = A - A.radius(); // 원점에서 우리가 찾는 점까지의 거리
return A.center() * (b / a);
로 (비교적) 간단하게 이 일을 할 수가 있겠죠. 그 외에 구현이 번거로운 점은 시계 방향으로 달렸을 때 처음 만나는 점 구하기 정도인데요. 모든 후보를 구한 뒤, atan2() 함수를 이용해 현재 점부터 그 점까지 가기 위한 각도를 구해서 최소를 구하면 비교적 편하게 할 수 있었던 것 같네요.
이것은 "구현하는" 문제라, 가장 짧게 코드를 짜는 연습을 해 보는 데 좋을 것 같습니다. :-) 깔끔한 코드 짜게 되면 올려 주세요~
제 코드 나갑니다.
~~~ cpp
const double EPS = 1e-7;
const double PI = 2.0 * acos(0.0);
struct Point
{
double y, x;
Point(double y = 0, double x = 0) : y(y), x(x) {}
Point operator - (const Point& rhs) const { return Point(y - rhs.y, x - rhs.x); }
Point operator * (double rhs) const { return Point(y * rhs, x * rhs); }
double norm() const { return hypot(y, x); }
double degree() const {
double t = atan2(y, x);
if(t < 0) t += 2 * PI;
return t;
}
};
struct Circle
{
double y, x, rad;
Circle(double y = 0, double x = 0, double rad = 0) : y(y), x(x), rad(rad) {}
Point center() const { return Point(y, x); }
};
inline double sqr(double x) { return x*x; }
struct DogWoods
{
vector C;
vector circleIntersection(double r1, const Circle& c)
{
double x0 = c.x, y0 = c.y, r0 = c.rad;
vector ret;
double D = c.center().norm();
if(D > r1 + r0 - EPS) return ret; // reject no/one intersection
if(D + r0 + EPS < r1) return ret; // no intersection
double x, y, d, p;
d = sqr(x0) + sqr(y0);
p = sqrt(( sqr(r0+r1) - d) * (d - sqr(r1-r0)));
x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) + y0 * p / (2*d);
y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) - x0 * p / (2*d);
ret.push_back(Point(y, x));
x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) - y0 * p / (2*d);
y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) + x0 * p / (2*d);
ret.push_back(Point(y, x));
return ret;
}
double degreeBetween(const Point& a, const Point& b)
{
double thetaA = a.degree();
double thetaB = b.degree();
double diff = thetaA - thetaB;
if(diff < 0) return diff + 2 * PI;
return diff;
}
double howFar(vector x, vector y, vector diameter, int startx, int starty)
{
for(int i = 0; i < x.size(); ++i) C.push_back(Circle(y[i], x[i], diameter[i] / 2.0));
Point here(starty, startx);
if(here.norm() <= 10) return 0;
double run = 0;
while(true)
{
double R = here.norm();
// get all colliding points
vector > collide;
for(int i = 0; i < C.size(); ++i)
{
vector p = circleIntersection(R, C[i]);
for(int j = 0; j < p.size(); ++j) collide.push_back(make_pair(p[j], i));
}
if(collide.empty()) return -1; // ooops
// get the nearest colliding point
int best = 0;
double bestMove = degreeBetween(here, collide[0].first);
for(int i = 1; i < collide.size(); ++i)
{
double candMove = degreeBetween(here, collide[i].first);
if(candMove < bestMove)
{
bestMove = candMove;
best = i;
}
}
run += bestMove * R;
here = collide[best].first;
int circle = collide[best].second;
vector p = circleIntersection(10, C[circle]);
if(!p.empty())
{
// yay, finally
Point arrival = p[0];
if((here-p[0]).norm() > (here-p[1]).norm())
arrival = p[1];
double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center());
run += theta * C[circle].rad;
break;
}
else
{
double D = C[circle].center().norm();
Point arrival = C[circle].center() * ((D - C[circle].rad) / D);
double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center());
run += theta * C[circle].rad;
here = arrival;
}
}
return run;
}
};
~~~
JongMan
겨울방학 SRM 모임 연습으로, JongMan, domeng, altertain, ryuwonha, xhae 다섯 명이 참가했습니다.
노가다 구현 500 과 후덜덜한 기하 1000, 그리고 노가다나 적절한 센스로 풀리는 250 으로 구성된 셋이었고요. 결과는 http://spreadsheets.google.com/pub?key=prOLhYJ-PdsL_svuPcyB3Pw&gid=0 에서 볼 수 있습니다. (태윤님 근데 저 M 좀 대문자로 바꿔주세요.. -_-)
250 - ElevatorLimit
Key Insight
physicalLimit * n <= 5000
해법
모든 문제에서 가장 먼저 확인해야 할 것은, 가장 무식한 방법으로도 문제를 풀 수 있는가입니다. 시간 안에만 들어간다면, 가장 무식하고 가장 작성하기 편한 해법이 가장 좋은 해법이죠. ^ 그래서, 처음에 0 명이 있었을 경우부터 physicalLimit 명이 있었을 경우까지의 모든 시나리오를 모두 시뮬레이션하면서 오류가 있는 경우를 제외하면 쉽게 답을 구할 수 있습니다.
오류가 있는 경우란: exit[i] 명이 나갔는데 엘리베이터에 음수명이 있을 경우와, enter[i] 명이 탔는데 physicalLimit 명을 초과하는 경우겠지요.
그 외 O(n) 해법도 있습니다. 처음에 0 명이 있다고 가정하고 쭉 시뮬레이션을 한 뒤 (오류 무시하고) 한 시점에 엘리베이터에 있었던 최소 인원수 A 와 최대 인원수 B 를 각각 기록합니다. 그러면, A <= 0 이겠는데, 이 때 처음 엘리베이터에서는 -A 명에서 physicalLimit - B 명까지 존재할 수 있었겠죠. 물론, 이 때는 각종 예외들을 처리해 줘야 하므로 검증이 좀 더 어렵다는 문제가 있죠. (실제로 r모 레드님은 이걸로 챌린지.)
소스코드 나갑니다.
~~~ cpp
struct ElevatorLimit
{
vector getRange(vector enter, vector exit, int physicalLimit)
{
int mini = physicalLimit + 1;
int maxi = -1;
for(int begin = 0; begin <= physicalLimit; ++begin)
{
int current = begin;
bool valid = true;
for(int i = 0; i < enter.size(); ++i)
{
if(current < exit[i]) { valid = false; break; }
current -= exit[i];
current += enter[i];
if(current > physicalLimit) { valid = false; break; }
}
if(valid)
{
mini = min(mini, begin);
maxi = begin;
}
}
if(maxi == -1) return vector();
vector ret(2);
ret[0] = mini;
ret[1] = maxi;
return ret;
}
};
1000 - DogWoods
아 문제 완전 안드로 -_-;;; 딴 거 볼 것 없이 1번 예제에 딸려오는 그림을 보시면 문제가 이해가 갈 겁니다.
Key Insight
볼 거 없이 시뮬레이션이구나
해법
넵 역시 닥치고 시뮬레이션 + 기하입니다. 이 셋 세터가 누군지.. 하악 어쨌든 적절한 가정과 코딩을 통해서 해야 하는 코딩의 양을 많이 줄일 수 있습니다. 일단, 원점을 중심으로 하는 원과 다른 원의 교차점을 구하는 식이 주어진다는 것은 좀 다행이죠. 이걸 이용해서 시뮬레이션을 하려면 다음과 같은 단계가 필요할 겁니다.
* R = 현재 위치와 원점과의 거리
* 원점을 중심으로 하고 반지름이 R 인 원과 교차하는 모든 나무들을 찾는다
* 없으면 -1 리턴
* 시계 방향으로 달렸을 때 처음 만나는 점을 찾는다
* 이 나무를 타고 반시계 방향으로 내려갈 것인데
* 이 나무가 원점을 중심으로 하고 반지름이 10 인 원과 교차한다면, 반시계 방향으로 달리다 숲의 중심에 도달
* 안 교차 한다면, 원점과 가장 가까운 점까지 달려내려간 후 맨 위로 돌아감
하악.. 뭐 말이 쉽지 좀 안드로메다죠. 적절한 코딩을 통해서 이 모든 것을 극복해야 합니다. 이런 경우 효율적으로 코딩을 하려면 점이나 원 등의 기본적인 primitive 들을 클래스화하는 것이 좋습니다. 예를 들어, 내가 나무 A 에 부딪혀서 원점과 가장 가까운 점까지 달려내려가려는데, 이 점의 위치를 구한다고 합시다. 덧셈, 뺄셈, 곱셈과 길이 구하기 등이 적절히 구현된 벡터 클래스를 가지고 있다면
double a = A.center().norm(); // 원점에서 A의 중심까지의 거리
double b = A - A.radius(); // 원점에서 우리가 찾는 점까지의 거리
return A.center() * (b / a);
로 (비교적) 간단하게 이 일을 할 수가 있겠죠. 그 외에 구현이 번거로운 점은 시계 방향으로 달렸을 때 처음 만나는 점 구하기 정도인데요. 모든 후보를 구한 뒤, atan2() 함수를 이용해 현재 점부터 그 점까지 가기 위한 각도를 구해서 최소를 구하면 비교적 편하게 할 수 있었던 것 같네요.
이것은 "구현하는" 문제라, 가장 짧게 코드를 짜는 연습을 해 보는 데 좋을 것 같습니다. :-) 깔끔한 코드 짜게 되면 올려 주세요~
제 코드 나갑니다.
~~~ cpp
const double EPS = 1e-7;
const double PI = 2.0 * acos(0.0);
struct Point
{
double y, x;
Point(double y = 0, double x = 0) : y(y), x(x) {}
Point operator - (const Point& rhs) const { return Point(y - rhs.y, x - rhs.x); }
Point operator * (double rhs) const { return Point(y * rhs, x * rhs); }
double norm() const { return hypot(y, x); }
double degree() const {
double t = atan2(y, x);
if(t < 0) t += 2 * PI;
return t;
}
};
struct Circle
{
double y, x, rad;
Circle(double y = 0, double x = 0, double rad = 0) : y(y), x(x), rad(rad) {}
Point center() const { return Point(y, x); }
};
inline double sqr(double x) { return x*x; }
struct DogWoods
{
vector C;
vector circleIntersection(double r1, const Circle& c)
{
double x0 = c.x, y0 = c.y, r0 = c.rad;
vector ret;
double D = c.center().norm();
if(D > r1 + r0 - EPS) return ret; // reject no/one intersection
if(D + r0 + EPS < r1) return ret; // no intersection
double x, y, d, p;
d = sqr(x0) + sqr(y0);
p = sqrt(( sqr(r0+r1) - d) * (d - sqr(r1-r0)));
x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) + y0 * p / (2*d);
y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) - x0 * p / (2*d);
ret.push_back(Point(y, x));
x = x0 / 2 - x0 * (sqr(r0) - sqr(r1)) / (2*d) - y0 * p / (2*d);
y = y0 / 2 - y0 * (sqr(r0) - sqr(r1)) / (2*d) + x0 * p / (2*d);
ret.push_back(Point(y, x));
return ret;
}
double degreeBetween(const Point& a, const Point& b)
{
double thetaA = a.degree();
double thetaB = b.degree();
double diff = thetaA - thetaB;
if(diff < 0) return diff + 2 * PI;
return diff;
}
double howFar(vector x, vector y, vector diameter, int startx, int starty)
{
for(int i = 0; i < x.size(); ++i) C.push_back(Circle(y[i], x[i], diameter[i] / 2.0));
Point here(starty, startx);
if(here.norm() <= 10) return 0;
double run = 0;
while(true)
{
double R = here.norm();
// get all colliding points
vector > collide;
for(int i = 0; i < C.size(); ++i)
{
vector p = circleIntersection(R, C[i]);
for(int j = 0; j < p.size(); ++j) collide.push_back(make_pair(p[j], i));
}
if(collide.empty()) return -1; // ooops
// get the nearest colliding point
int best = 0;
double bestMove = degreeBetween(here, collide[0].first);
for(int i = 1; i < collide.size(); ++i)
{
double candMove = degreeBetween(here, collide[i].first);
if(candMove < bestMove)
{
bestMove = candMove;
best = i;
}
}
run += bestMove * R;
here = collide[best].first;
int circle = collide[best].second;
vector p = circleIntersection(10, C[circle]);
if(!p.empty())
{
// yay, finally
Point arrival = p[0];
if((here-p[0]).norm() > (here-p[1]).norm())
arrival = p[1];
double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center());
run += theta * C[circle].rad;
break;
}
else
{
double D = C[circle].center().norm();
Point arrival = C[circle].center() * ((D - C[circle].rad) / D);
double theta = degreeBetween(arrival - C[circle].center(), here - C[circle].center());
run += theta * C[circle].rad;
here = arrival;
}
}
return run;
}
};
~~~
17년 전