600 - ThreeTeleports
- 500점이 아닌 600점이길래 어려울꺼라 생각했는데, 중간에 경유할수 있는 텔레포트가 3개로 제한되어 있고 가장 빠른길은 텔레포트를 몇개를 거치는지, 어떤 순서로 거치는지, 어디가 시작점이고 어디가 끝점인지 여부가 중요하므로 이를 선택하는 전략을 정하는게 주요한 문제였는데, 모든 경우의 수를 다 계산해도 3*2+3*2*2*2+3*2*2*2*1*2 밖에 안되므로 모든경우를 다 만들어 돌려봄.
- 처음 코딩할때 시작점과 끝점을 어떻게 정하느냐에 따라 경우의수가 나뉘어 진다는것을 생각못해 좀 더 걸림.
- 가장 긴게 32bit int 범위를 넘어간다는것을 예상하지 한번더 고생함.
- 하지만 예제 입출력이 다양하게 잘 되어 있어서 이런 실수들을 다 커버해주심..
- 결과 : 337.28
struct Point
{
int x1, y1, x2, y2;
};
class ThreeTeleports
{
public:
long long result;
int xMe, yMe, xHome, yHome;
Point tele[3];
int used[3];
bool backword[3];
bool allUsed()
{
for(int i = 0; i < 3; i++)
{
if(used[i] == 0) return false;
}
return true;
}
int nextUsedNumber()
{
int maxvalue = 0;
for(int i = 0; i < 3; i++)
{
maxvalue = max(maxvalue, used[i]);
}
return maxvalue+1;
}
long long getDistance(long long x1, long long y1, long long x2, long long y2)
{
return abs(x1-x2)+abs(y1-y2);
}
void setMinimumPath()
{
int prevX = xMe;
int prevY = yMe;
long long nowPath = 0;
for(int i = 1; i <= 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(used[j] == i)
{
nowPath += 10;
if(backword[j] == false)
{
nowPath += getDistance(prevX, prevY, tele[j].x1, tele[j].y1);
prevX = tele[j].x2;
prevY = tele[j].y2;
}
else
{
nowPath += getDistance(prevX, prevY, tele[j].x2, tele[j].y2);
prevX = tele[j].x1;
prevY = tele[j].y1;
}
}
}
}
nowPath += getDistance(prevX, prevY, xHome, yHome);
result = min(result, nowPath);
}
void getMinimumPath()
{
if(allUsed())return;
for(int i = 0; i < 3; i++)
{
if(used[i] == 0)
{
used[i] = nextUsedNumber();
backword[i] = false;
setMinimumPath();
getMinimumPath();
backword[i] = true;
setMinimumPath();
getMinimumPath();
used[i] = 0;
}
}
}
int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector <string> teleports)
{
this->xMe = xMe;
this->yMe = yMe;
this->xHome = xHome;
this->yHome = yHome;
for(int i = 0; i < teleports.size(); i++)
{
used[i] = 0;
sscanf(teleports[i].c_str(), "%d %d %d %d", &tele[i].x1
, &tele[i].y1
, &tele[i].x2
, &tele[i].y2);
}
result = getDistance(xMe, yMe, xHome, yHome);
getMinimumPath();
return (int)result;
}
};
900 - BinaryCards
- 대회를 30분이나 늦게 시작했더니 900문제를 열었을땐 시간이 8분밖에 남지 않아 깨끗이 포기.
- 으아니 근데 이게 Div1 250 이라니!!
- 같은 방 어떤 분이 풀었으나 챌린지 할때 공격을 못함.
- 그분은 Sys fail 뜸.
- 결국 아마 난 시간이 있었어도 쉽게 못 풀었을꺼야 아마.. ㅠㅠ
http://www.topcoder.com 에서 진행하는 알고리즘 대회인 Single Round Match에 요 근래부터 참여를 하고 있다. 오래전에 이러한 곳이 있다는 것을 알고 있었지만 UVa등 여타 문제 풀이 사이트와는 다른 접근 방법 때문에 미루고 미루다가 이제야 부터 시작하게 되었다.
다른 사이트는 여러 문제들중 풀고 싶을 때 문제를 골라서 풀어 제출하고 로봇 테스트를 통과하지 못하면 어떤 입력에 대해서 틀린 값이 나올지 추축을 하고 코드를 다시 한번 검증을 하고 수정을 한 다음에 다시 제출해야 한다. 이게 맞을때까지 반복. 만약 도저히 알지 못하겠으면 포기를 하던가 구글링을 하여 정답 소스를 찾던가 사이트 마다 마련된 게시판에서 검색을 하여 해결 방법을 찾아보는 식으로 진행을 했다.
탑코더는 자바로 만들어진 Arena라는 런처를 통해 마치 게임하듯이 접속을 진행을 한다. 진행 방법도 게임과 흡사하다. 20명당 한방에 들어가게 되며 문제는 총 3개의 문제로 구성이 되어 있다. 난이도마다 점수가 주어지며 빨리 풀수록 점수는 높게 되는데 여기 까지는 여타 다른 사이트랑 다를게 없어 보이지만 차이는 이 다음부터. 코딩하고 제출한것은 시스템에서 어떠한 검사도 해주지 않는다. 제출한 시간이 빠를 수록 바로 점수가 부여된다. 이러면 엉터리 코드를 제출한 사람이 높은 점수를 받을거 같지만 이 다음이 있다. 휴식 시간이 지나고 챌린지 라는게 있는데, 이게 탑코더의 백미. 다른 사람의 소스를 열어 보고 오류 결과를 낼 만한 입력을 만들어 입력을 하여 그것이 적절한 지적이였으면 오류 소스를 짜낸 사람은 그 문제에 대한 점수가 0점 처리 되고 지적한 사람은 50점을 받게 된다. 챌린지 시간에 다른 코더의 눈에 띄지 않고 무사히 견뎌냈다고 해도 다음번에 있는 시스템 테스트에서 걸려버리면 0점 처리.
챌린지라는 도구를 하나 넣음 으로써 알고리즘 문제 풀이를 보다 게임화 시켰다. 한 문제도 풀지 못한 코더가 챌린지를 통해서 룸에서 높은 순위까지 올라가는 것도 가능하다.
멋진점이 진행 방식 말고도 몇가지 더 있는데, 전세계 곳곳에 흩어져 있는 훌륭한 코더들이 풀어 재출한 소스 코드를 언제든 직접 볼 수 있다는 점과 참여자들이 자발적으로 만들어가는 Editorial, 그리고 챌린지에서 혹은 시스템 테스트에서 실패를 했을 경우 어떠한 입력에서 실패를 했는지도 알 수 있다는 것이다. 모든 테스트를 통과한 코더의 기록을 통해서 다른 테스트 입력이 뭔지도 알아낼 수 있으니 시스템 테스트에서 실패한 문제는 다른 코더의 소스를 통해서, 입력되었던 테스트 입력들을 통해서 올바른 소스로 고쳐 나갈 수 있다.
