[editorial] TCO09 Qual3

  • helloneo
    helloneo

    안녕하세요.. 처음으로 에디토리얼을 써봅니다..
     
    Q1, Q2에서 삽질한 덕분에 Q3을 참여하였는데요..
    Q3은 난이도도 무난했고 경쟁도 좀 덜 치열했던 것 같네요.. ㅎㅎ

    123.jpg456.jpg
     
     
    250 - Bidirectional Queue (링크)
     
    bidirectional queue는 세가지 operation이 있는데
    1) queue 맨 왼쪽의 원소를 extract
    2) 왼쪽으로 한칸 shift (맨 왼쪽에 있는 원소는 오른쪽 끝으로 이동)
    3) 오른쪽으로 한칸 shift (맨 오른쪽에 있는 원소는 왼쪽 끝으로..)
     
    vector indice[] 의 원소를 차례대로 뽑고 싶을때 최소 몇번 shift해야 하는지 구하기..
     
     
    -- 풀이 --
     
    이 문제는 greedy로 쉽게 해결할 수 있습니다.
    왼쪽으로 shift하든지 오른쪽으로 shift하든지 그 이후의 상태가 같아지므로..
    무조건 적은 비용이 드는 방향으로 shift하면 됩니다.
    그 다음은 그냥 simulation 합니다 ;;
     
     
     
    500 - PrettyPrintASpiral (링크)
     
    sp.jpg 
     
    그림과 같은 2차원 grid에서 row1, col1, row2, col2 가 주어질 때,
    그 사이에 들어있는 수를 차례로 출력하기..
     
     
    -- 풀이 --
     
    이 문제의 핵심은 input x, y에 대해서 (x, y)에 있는 값을 어떻게 찾아오느냐 입니다..
    우선 (0, 0)을 중심으로 하며 (x, y)를 포함하는 최소의 정사각형 찾습니다..
    당근 정사각형의 한쪽 끝 x, y좌표는 max(abs(x), abs(y)) 가 됩니다..
    그리고 이 정사각형 선상에 있는 수중에 가장 큰 수를 구합니다.. (2*max(abs(x), abs(y))+1)^2 가 됩니다
    그리고 찾으려고 하는 좌표가 정사각형의 오른쪽선상에 있는지 왼쪽선상에 있는지 위에에 있는지 아래 있는지를
    판단해서 적절한 연산을 하면 해당 좌표의 값을 구할 수 있습니다..

    int get_n(int x, int y)
    {
        int k, l, m, n;
        m = max(abs(x), abs(y));
        k = (2*m+1)*(2*m+1);
        if (x <= m && y == m) {
            l = m - x;
            n = k-l;
        }
        else if (x == -m && y <= m) {
            l = m - y;
            n = k - (2*m) - l;
        }
        else if (x <= m && y == -m) {
            l = abs(-m - x);
            n = k - (4 * m) - l;
        }
        else {
            l = abs(-m - y);
            n = k - (6*m) - l;
        }
        return n;
    }
    

     
    1000 - MatchedStrings (링크)

    ( 또는 ) 로 이루어진 string 중에서 ( 와 ) 가 짝이 맞는 경우를 well-parenthesized 이라고 합니다
    예를들어 다음은 다 well-parenthesized 입니다
     
    empty string
    ()()()
    (()())()()
    ((()))
     
    well-parenthesized 가 아닌 string 을 mismatched라고 하는데..
    '(' 와 ')' 로 이루어진 길이 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의 솔루션 이었습니다..
    틀린점이 있으면 알려주세요.. ㅎㅎ;;
    code highliting 어떻게 하는건가요..?
    크롬에서 쓰다가 이상해졌어요..;

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    10년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    제가 날름 적용해 봤습니다. ^^; 에디토리얼 고맙습니다~! ㅋㅋ


    10년 전 link
  • 세인트
    세인트

    T.T 패배의 세인트


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.