TCO09 Qual 3 (완료)

Problem Solving/TopCoder logs 2009. 3. 5. 21:43
오늘 아침 11시에 있었던 TCO09 퀄 마지막 라운드..
1, 2라운드에서 삽질하다가 결국 3라운드까지 가게됐다..
덕분에 금쪽같은 휴가 쓰고.. 참가하게되었다.. ㅠ_ㅠ
아마도.. 지금까지 참가했던 매치중에 가장 긴장되는 매치였던것 같다..

이미 올라갈 사람은 다 올라갔는지.. 이번에는 약간 한산했다..
무려 1600명 이상 참가했던 Q2에 비해.. Q3은 대략 1200여명 참여했다..

덕분에 모처럼 2문제 풀면서 만족스런 결과를 얻었다..
Q3까지 가는 졸전끝에 간신히 R1 진출~~ (아직 발표는 안났지만)

전체 79등..~ rating도 101점이나 올리면서 4번 연속 하락한걸 한방에 만회했다..~




Level1 - BidirectionalQueue
circular 형태로 된 queue가 있다.. 여기에 shift와 extract라는 operation이 있는데 queue를 왼쪽으로 shift 하면 맨 왼쪽에 수가 오른쪽 끝에 가고 오른쪽으로 shift하면 오른쪽 끝에 수가 왼쪽 맨 앞에 붙는다.. extract는 왼쪽 맨 앞에 수를 하나 pop..~ 1부터 N까지 차례로 들어있는 queue에서 원하는 원소를 주어진 순서대로 뽑으려고 할때 최소 shift수 구하기..

greedy로 풀었다.. 왼쪽으로 shift하던 오른쪽으로 shift하던 그 다음 상태가 항상 같아지므로 그냥 적은 비용이 드는 방향으로 shift하면 된다..~ 이 짓을 주어진 원소를 다 뽑을때까지 반복

처음에 원하는 원소를 아무 순서로나 뽑을수 있는지 알고.. 한참 고민했다.. ㅠ_ㅠ 덕분에 시간 대박 낭비..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class BidirectionalQueue {
  9 public:
 10
 11 int extractElements(int N, vector <int> indices)
 12 {
 13     int num[100], temp[100];
 14     int size;
 15     int i, j, k;
 16     int cnt1, cnt2;
 17     int sum;
 18     size = indices.size();
 19     for (i = 1; i <= N; i++) {
 20         num[i] = i;
 21     }
 22     sum = 0;
 23     for (i = 0; i < size; i++) {
 24         if (N== 1)
 25             break;
 26         for (j = 1; j <= N; j++) {
 27             if (num[j] == indices[i])
 28                 break;
 29         }
 30         cnt1 = j-1;
 31         for (j = N, k = 0; j >= 1; j--, k++) {
 32             if (num[j] == indices[i])
 33                 break;
 34         }
 35         cnt2 = k+1;
 36 printf("cnt1 = %d, cnt2 = %d\n", cnt1, cnt2);
 37         if (cnt1 < cnt2)
 38             sum += cnt1;
 39         else
 40             sum += cnt2;
 41         for (j = 1, k = cnt1+1; j <= N; k++) {
 42             if (k == N+1)
 43                 k = 1;
 44             if (num[k] == indices[i])
 45                 continue;
 46             temp[j++] = num[k];
 47         }
 48         N--;
 49         for (j = 1; j <= N; j++) {
 50             num[j] = temp[j];
 51         }
 52     }
 53 printf("sum = %d\n", sum);
 54     return sum;
 55 }
 56
 57 };



Level2 - PrettyPrintASpiral
주어진 그림과 같이 2차원 좌표계에서 숫자가 반시계방향으로 증가한다.. (row1, col1), (row2, col2) 사이에 수를 차례로 출력하기..

이 문제의 핵심은 (x, y) 좌표가 주어졌을 때, 거기에 해당하는 값을 찾는 방법인데..
나같은 경우 903 - Spiral of Numbers 문제를 미리 풀었기때문에.. 그 코드를 그냥 복.붙 했다.. -_-

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 char temp[1000000];
 10
 11 int get_n(int x, int y)
 12 {
 13     int k, l, m, n;
 14     m = max(abs(x), abs(y));
 15     k = (2*m+1)*(2*m+1);
 16
 17     if (x <= m && y == m) {
 18         l = m - x;
 19         n = k-l;
 20     }
 21     else if (x == -m && y <= m) {
 22         l = m - y;
 23         n = k - (2*m) - l;
 24     }
 25     else if (x <= m && y == -m) {
 26         l = abs(-m - x);
 27         n = k - (4 * m) - l;
 28     }
 29     else {
 30         l = abs(-m - y);
 31         n = k - (6*m) - l;
 32     }
 33     return n;
 34 }
 35
 36
 37 class PrettyPrintASpiral {
 38 public:
 39
 40 vector <string> getWindow(int row1, int col1, int row2, int col2)
 41 {
 42     int i, j, k, l, x, y;
 43     int map[100][100];
 44     int max_digit;
 45     char buf[100];
 46     int len;
 47     vector<string> res;
 48     string str;
 49     max_digit = 0;
 50     for (i = row1, x = 0; i <= row2; i++, x++) {
 51         for (j = col1, y = 0; j <= col2; j++, y++) {
 52             k = get_n(j, i);
 53             sprintf(buf, "%d", k);
 54 printf("(%d, %d) = %d\n", i, j, k);
 55             max_digit = max(max_digit, strlen(buf));
 56             map[x][y] = k;
 57         }
 58     }
 59     for (i = 0; i < x; i++) {
 60         k = 0;
 61         temp[k] = 0;
 62         for (j = 0; j < y; j++) {
 63             sprintf(buf, "%d", map[i][j]);
 64             len = strlen(buf);
 65             if (j != 0) {
 66                 temp[k] = ' ';
 67                 temp[k+1] = 0;
 68                 k++;
 69             }
 70             for (l = 0; l < max_digit-len; l++) {
 71                 temp[k++] = ' ';
 72             }
 73             for (l = 0; l < len; l++) {
 74                 temp[k++] = buf[l];
 75             }
 76             temp[k] = 0;
 77         }
 78         str = temp;
 79         res.push_back(str);
 80     }
 81     return res;
 82 }
 83
 84 };



Level3 - MismatchedStrings
'(' 와 ')'로 이루어진 길이 N의 string 중에서 lexicographically K-th mismatched string 구하기

귀찮은 관계로.. -_- 알고스팟 에디토리얼을 그냥 펌..;;



-- 풀이 --
 
기본 아이디어는 우선 empty string에서 시작해서..
'(' 를 붙여보고 앞으로 나올 수 있는 mismatched가 몇개인지 세봅니다
'('를 붙여서 K-th smallest string을 만들 수 없다고 판단되면 대신 ')' 를 붙입니다..
')'를 붙일 경우 '('를 붙였을 때 만들 수 있는 string의 개수 만큼을 건너뛰게 되므로 K 값에서 빼주면서 진행합니다..
 
이 문제를 풀기 위해 먼저 다음과 같은 table을 구해두면 편합니다
 
match[i][j] = 길이 i 이면서 j개의 '(' 가 아직 닫히지 않은 string의 개수
                   (또는 j개의 '('를 닫을 수 있는 string의 개수??)
 
 
long long match[60][60];
int n;
 
long long get_cnt(string str)
{
    int i, j, len;
    long long cnt;
    len = str.size();
    cnt = 1LL << (n-len);
    j = 0;
    for (i = 0; i < len; i++) {
        if (str[i] == '(')
            j++;
        else
            j--;
        if (j < 0)
            return cnt;
    }
    return cnt - match[n-len][j];
}
 
class MismatchedStrings {
public:
 
string getString(int N, long long K)
{
    int i, j;
    long long cnt;
    string res;
    n = N;
    memset(match, 0, sizeof(match));
    match[0][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 0 ; j <= n; j++) {
            match[i][j] = match[i-1][j+1];
            if (j-1 >= 0)
                match[i][j] += match[i-1][j-1];
        }
    }
    res = "";
    if (K >= (1LL << N) - match[N][0]) {
        return res;
    }
    for (i = 0; i < N; i++) {
        res += '(';
        cnt = get_cnt(res);
        if (cnt <= K && K) {
            K -= cnt;
            res[res.size()-1] = ')';
        }
    }
    return res;
}
 
};
 
이상 tomek의 솔루션 이었습니다..
틀린점이 있으면 알려주세요.. ㅎㅎ;;


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

[SRM 441] 탑코더 아레나.. 중국 뉴비들에게 DDOS공격 받고 사망..  (0) 2009.05.28
TopCoder SRM 440 Div 1 - 드디어 Yellow 등극..  (0) 2009.05.14
말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Round 1  (0) 2009.03.08
TCO09 Qual 2  (0) 2009.03.01
TCO09 Qual 1  (0) 2009.02.25
TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07
TopCoder SRM 428 Div 1  (0) 2008.12.03
  • By helloneo

to Top

티스토리툴바