티스토리 뷰


전세계 대상으로 열렸던 구글 코드잼이 한국인 만을 대상으로 대회를 열었습니다. 아마도 구글에 다니시는 모 분의 힘이 크지 않았나 싶은 생각이 듭니다. (-_-;;) 대회 홈페이지에 적혀 있는 "많은 참가자들의 호응에 힘입어" 라는 말을 듣기엔 그리 많이 참가하는것 같지 않았거든요. 지역 대회를 개최하는 3번째 국가라던데 code jam 참가자수 국가 순위는 대략 10등 밖이라서..

이번 korea 2012 는 한국어로 진행한다는 점 덕분인지 1문제를 푼 사람이 500명 이 넘었습니다. 오오!  Google Code Jam에 참여하는 한국인이 대략 200명 정도 였는데,  이 기세를 code jam 2012까지 몰아 갔으면 좋으련만 영어에 대한 반감때문에 200~300 정도가 참가하지 않을까 하는 추측을 해봅니다.

대회가 당초 오후 2시 부터 8시까지 6시간 진행되려던 것을 구글 해커톤과 일정이 겹친 덕분에 12시간 연장! 애초 자사 행사와 겹쳐서 일정이 잡혔던게 좀 의아한. 그래서 전 한껏 게으르게 문제를 풀 수 있었습니다. 핫핫.

처음 문제판을 열어보니 예상보다 높은 커트라인 점수 (40점!)와 예상보다 쉽게 풀리지 않았던 A번 문제 때문에 당황을 했습니다. -_-; 무려 두번이나 틀려서 힘들게 풀었어요. 한 주에 속한 일이 많아봤자 100일 밖에 안되므로 이를 이용해 마지막 주에 남겨진 일수를 이용해서 패턴찾기 비슷하게 풀었습니다. 아... 어려웠어요 -_-;

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
#include <map>
#include <set>
#include <list>
#include <cstring>
using namespace std;
 
long long getResult(long long month, long long day, long long dayweek)
{
    long long weekOfMonth = day/dayweek;
    long long spare = day%dayweek;
    if(spare){weekOfMonth++;}
    
    long long result = weekOfMonth*month;
 
    int spareDay[101] = {0};
    long long period = 0;
    long long addedDay = 0;
    for(long long i = 1; i <= dayweek; i++){
        spareDay[i] = (spareDay[i-1]+day)%dayweek;
        period = i;
        if(spareDay[i] == 0) break;
        if(spareDay[i] < spareDay[i-1]){ addedDay++;}
    }
 
    result += (month/period)*addedDay;
    for(long long i = 1; i <= month%period; i++){
        if(spareDay[i] < spareDay[i-1]){
            result++;
        }
    }
 
    return result;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    long long t, m, d, w;
    
    scanf("%lld", &t);
    for(long long caseNumber = 1; caseNumber <= t; caseNumber++)
    {
        scanf("%lld %lld %lld", &m, &d, &w);
        
        printf("Case #%lld: %lld\n", caseNumber, getResult(m, d, w));
    }
 
    return 0;
}
 

두번째 문제를 보니 배점이 가장 높고 문제를 푼사람도 20명이 채 되지 않길래 그냥 깔끔히 패ㅋ스ㅋ

세번째 문제를 보니 문제는 좀 길지만 모든 친구가 도달할 수 있는 지점의 최댓값의 최솟값을 구하는 문제였습니다. 
그.래.서. 그냥 그렇게 짯어요 -_-;;

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
#include <map>
#include <set>
#include <list>
#include <cstring>
#include <queue>
 
using namespace std;
 
struct Line{
    int dist;
    int length;
};
 
struct People{
    int start, time;
};
 
int t, p, n, m;
int resultSet[10001][101];
int cityMap[10001][10001];
People people[101];
Line lines[1001];
 
void Init()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= p; j++)
        {
            resultSet[i][j] = -1;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cityMap[i][j] = 0;
        }
    }
}
 
int getResult()
{
    // 초기화
    scanf("%d %d %d", &n, &p, &m);
    Init();
 
    // 입력
    for(int i = 1; i <= p; i++)
    {
        scanf("%d %d", &people[i].start, &people[i].time);
    }
 
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &lines[i].dist, &lines[i].length);
        int from, to;
        scanf("%d", &from);
        for(int j = 1; j < lines[i].length; j++)
        {
            scanf("%d", &to);
            cityMap[from][to] = cityMap[to][from] = i;
            from = to;
        }
    }
 
    // 각 사람이 도달할 수 있는 지점 표시하기!
    for(int i = 1; i <= p; i++)
    {
        queue<int> pos, time;
 
        pos.push(people[i].start); time.push(0);
        resultSet[people[i].start][i] = 0;
 
        while(!pos.empty())
        {
            int nowPos = pos.front();pos.pop();
            int nowTime = time.front();time.pop();
            
            for(int other = 1; other <= n; other++)
            {
                int path = cityMap[nowPos][other];
                if(path)
                {
                    if(resultSet[other][i] == -1
                        || resultSet[other][i] > nowTime + lines[path].dist*people[i].time)
                    {
                        pos.push(other);
                        time.push(nowTime + lines[path].dist*people[i].time);
                        resultSet[other][i] = nowTime + lines[path].dist*people[i].time;
                    }
                }
            }
        }
    }
 
    // 모든 사람이 도달할 수 있는 곳의 도착 시간의 최댓값의 최솟값 구하기.
    int result = -1;
    for(int i = 1; i <= n; i++)
    {
        int maximum = 0;
        for(int j = 1; j <= p; j++)
        {
            maximum = max(maximum, resultSet[i][j]);
            if(resultSet[i][j] == -1)
            {
                maximum = -1;
                break;
            }
        }
        if(maximum != -1){
            if(result == -1) result = maximum;
            else             result = min(result, maximum);
        }
    }
 
    return result;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d", &t);
    for(int c = 1; c <= t; c++)
    {
        fprintf(stderr, "now %d\n", c);
        printf("Case #%d: %d\n", c, getResult());
    }
    return 0;
}
 
 

Small케이스에서는 제법 빠른 시간에 나옵니다. large일 경우도 시간 복잡도가 매우 크지 않으므로 대충 한 테스트 케이스당 10초 내에는 나올꺼라 생각해서 large input을 받고 돌려봤죠.

그런데 1분이 지나도 답이 나오지 않습니다. -_-;; What the ....

그래서 돌아가던 것을 끄고 input 파일을 열어 보았죠. 그런데 놀랍게도 테스트 케이스가 단 2개밖에 없었습니다. 그렇게 오래 걸릴일이 없는거죠! 하지만 large input에 대한 답을 제출할 수 있는 시간은 8분이 한계이며 기회는 단 한번 밖에 없기 때문에 소스코드 수정은 할 수 없죠. 별 수 없이 자포자기 한 심정으로 돌려 놓았습니다.

시간은 흐르고 제출시간이 1분도 채 남지 않았을때 프로그램이 답을 내주었어요! 부랴부랴 일단 제출! 그러고 나서 질답을 읽어보니.

제공되는 모든 문제는 2GHz(Single core) 컴퓨터에서 256MB 메모리만을 사용하면서 2분안에 나올 수 있도록 출제되고 있습니다.

랍니다. -_-;; 2.80GHz의 컴퓨터에서 400MB 가까이 사용하여 5분이나 걸려 답을 낸 프로그램을 만든 저로써는 그저 부끄러울뿐. 다익스트라를 이용하면 3초도 안되서 답이 나오더군요 데헷.

문제를 풀던중에 대회 난이도 덕분인지 오류가 있었는지 40점이였던 커트라인이 35로 줄어들었습니다. 그리고 대회안내를 읽어보니 처음엔 상위 30등까지 기념 티셔츠를 준다고 했는데 상위 50명까지 준다고 합니다. 지금까지 대회에서 저의 최고 기록이 한국인중 3x등이였으니 가능성이 있... 지만 참가자수가 더 늘어서 아마 안되겠죠 ㅠㅠ.

코드잼 역사 페이지에 있는 티셔츠 도안을 보니... 이쁘진 않네요 :(

댓글
댓글쓰기 폼