티스토리 뷰

공부/Problem Solving

Topcoder SRM 519 DIV2

Mastojun 2011.09.20 22:34
250 WhichDay
 - 아무리 div2이지만 이렇게 쉬운 문제가 나온건 처음이였던듯한 문제.
 - 테스트 하지 않고 바로 제출할껄 하는 아쉬움이...
 - 결과 246.65
class WhichDay 
{ 
public: 
    string getDay(vector <string> notOnThisDay) 
    { 
        string day[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday",  "Friday", "Saturday"};
         
        bool isFound; 
        for(int i = 0; i < 7; i++) 
        { 
            isFound = false; 
            for(int j = 0; j < notOnThisDay.size(); j++) 
            { 
                if(notOnThisDay[j] == day[i]) isFound = true; 
            } 
            if(isFound == false) 
            { 
                return day[i]; 
            } 
        } 
        return ""; 
    } 
};

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 뜸.
 - 결국 아마 난 시간이 있었어도 쉽게 못 풀었을꺼야 아마.. ㅠㅠ








 
TAG
,
댓글
댓글쓰기 폼