구글 코드잼 코리아 예선 B번은 다들 어떻게 푸셨나요?

  • hyunhwan
    hyunhwan

    나름 문제가 재밌었던 대회였는데, 이야기가 없어서 먼저 이야기를 꺼내봅니다.

    그 중에서 가장 재밌었던 문제는 B번 계산식 복원 문제였던것 같습니다.

    제 경우에는 '사전순으로 가장 작은 수식'을 출력하는 부분을 처리하는데 많은 애를 먹었는데, 다음과 같은 아이디어와 동적계획법을 조합하여 구현을 해봤습니다.

    우선 계산식을 처리하는 경우에는
    일반적으로 자리올림/내림 연산의 경우가 발생하기 떄문에 낮은자리에서 높은자리 순으로 구현을 하는게 일반적인데요(보통 입력된 수식을 뒤집어서 계산하는 편이 편합니다)

    서두에 언급한 조건 때문에 앞서 설명한 방법으로 구현할 경우에는, 거의 모든 경우를 헤아리게 되어 계산량을 줄이기 힘듭니다.

    그래서 수식을 뒤집지 않고, 높은 자리부터 계산을 하되, 다음 자리를 계산할 때 자리 올림/내림 연산을 강제하도록 구현했습니다.

    예를 들어서 설명하면 다음과 같습니다.

     5AB
    +C5D
    -----
     724
    

    A, B, C, 그리고 D는 ? 가 들어가 있는 위치입니다.

    높은 자리부터 계산할 경우 우선 C에 들어갈 수 있는 숫자는 1, 2가 됩니다. 따라서 1이 들어갈 경우 5+1 이 되어서 해당 자리의 값인 7을 만족하지 못합니다.
    따라서 다음의 자리에서는 반드시 자리 올림 연산이 강제되야 하기 때문에 A에 들어가게 될 숫자는 6혹은 7이 됩니다. 앞의 과정과 마찬가지로 6이 될 경우 다음 자리에서는 강제적으로 자리올림 연산이 발생해야죠.

    이러한 아이디어를 조합해서 상태공간을 [pos][a][b][c][carry] 로 잡아서 사전순으로 작은 수식이 올 수 있도록 구현을 하였는데, 여기서 pos는 연산하는 자리의 위치, a, b, c는 바로 앞단계에 선택된 숫자입니다.
    그리고 carry는 강제적으로 자리올림을 발생해야 하는가, 아닌가를 뜻합니다.

    근데 대회가 끝나고 생각해보니, c의 경우에는 a와 b 그리고 carry를 조합하면 c에 들어갈 숫자는 정해지기 때문에 굳이 c를 상태공간에 잡을 필요는 없더군요.

    제가 대회 도중에 작성했던 소스코드를 첨부합니다. 다들 어떻게 짜셨는지 댓글로 달아주시면 좋을거 같습니다.

    #include <cstdio>
    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    #include <map>
    #include <set>
    #include <string>
    #include <utility>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    typedef pair<int,int> ii;
    typedef long long ll;
    
    string best;
    
    string rm( const string &s ) {
        string ret = s;
        while( (int)ret.size() > 1 && ret[0] == '0' ) {
            ret = ret.substr(1);
        }
        return ret;
    }
    
    int getlo( int i, const string &s  ){
        if( isdigit( s[i] ) ) return (int)(s[i]-'0');
        if( s[i] == '#' ) return 0;
    
        if( (int)s.size() == 1 ) return 0;
        if( i == 0 ) return 1;
        if( s[i-1] == '#' && i != (int)s.size() - 1 ) return 1;
        return 0;
    }
    
    int gethi( int i, const string &s ) {
        if( isdigit( s[i] ) ) return (int)(s[i]-'0');
        if( s[i] == '#' ) return 0;
        return 9;
    }
    
    int sign;
    string lf;
    string rt;
    string ans;
    
    typedef pair< pair<string,string>, string > node;
    node cache[2][10][10][10][251];
    
    const node nil = make_pair( make_pair( "", "" ), "" );
    const node fail = make_pair( make_pair( "", "" ), "FAIL" );
    
    node solve( int where, int carry, int pl, int pr, int pa ) {
        if( where == ans.size() ) {
            //for(int i=0;i<where;++i) fprintf( stderr, " ");
            //fprintf(stderr,"=> %s\n", ( carry ? "O" : "X" ) );
            if( carry == 0 ) return nil;
            return fail;
        }
    
        int l1 = getlo( where, lf ), l2 = gethi( where, lf );
        int r1 = getlo( where, rt ), r2 = gethi( where, rt );
        int a1 = getlo( where, ans ), a2 = gethi( where, ans );
    
        node &ret = cache[carry][pl][pr][pa][where];
        if( ret != nil ) return ret;
        ret = fail;
    
        for( int l = l1 ; l <= l2 ; ++l ) for( int r = r1 ; r <= r2 ; ++r ) for( int a = a1 ; a <= a2 ; ++a ) for( int c = 0 ; c <= 1 ; ++c ) {
    
            int v = l + sign * ( r + c );
            //cerr << v << " " << l << " " << r << " " << a << " " << c << endl;
            if( carry == 1 ) {
                if( sign == 1 ) {
                    if( v < 10 ) continue;
                }
                else {
                    if( v >= 0 ) continue;
                    v += 10;
                }
            }        
            else {
                if( sign == 1 ) {
                    if( v >= 10 ) continue;
                }
                else if ( v < 0 ) continue;
            }
            if( v % 10 == a ) {
                node ans = solve( where+1, c, l, r, a ); 
                if( ans != fail ) {
                    ans.first.first = string(1,char(l+'0')) + ans.first.first;
                    ans.first.second = string(1,char(r+'0')) + ans.first.second;
                    ans.second = string(1,char(a+'0')) + ans.second;
                    if( ret == fail || ret > ans ) ret = ans;
                }
            }
        }
        return ret;
    
    }
    
    int main() {
        int ncase;
        scanf("%d", &ncase); 
    
        for( int caseno = 1 ; caseno <= ncase ; ++caseno ) {
            string op, foo;
            cin >> lf >> op >> rt;
            cin >> foo >> ans;
    
            best = "";
            int max_len = max( (int)ans.size(), (int)lf.size() );
            max_len = max( max_len, (int)rt.size() );
    
            while( (int)lf.size() < max_len ) lf = '#' + lf;
            while( (int)rt.size() < max_len ) rt = '#' + rt;
            while( (int)ans.size() < max_len ) ans = '#' + ans;
    
            for( int i = 0 ; i < 2 ; ++i ) 
                for( int l = 0 ; l < 10 ; ++l ) 
                    for(int r = 0 ; r < 10 ; ++r ) 
                        for( int a = 0 ; a < 10 ; ++ a ) 
                            for( int p = 0 ; p < max_len ; ++p )
                                cache[i][l][r][a][p] = nil;
            printf("Case #%d: ", caseno);
            if( op == "+" ) sign = 1; else sign = -1;
            node ret = solve( 0, 0, 0, 0, 0);
            cout << rm(ret.first.first) << " " << op << " " << rm(ret.first.second) << " = " << rm(ret.second) << endl;
    
        }
    }
    

    12년 전
4개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    저도 대회가 끝난 후에는 비슷한 아이디어로 풀어보았는데, 제 컴퓨터에서는 large 데이터를 푸는데 30초 정도?는 걸렸던 것 같네요... 그리고 저는 pair로 node를 정의하는 부분을 구조체로 했는데, 의미를 명확하게 하기도 좋고, 오히려 코드도 더 짧아진 것 같습니다. .first.first 대신 .A를 쓰고 .first.second 대신 .B를 쓰니까요 ~_~


    12년 전 link
  • Being
    Being

    저는 레퍼런스 솔루션과 비슷한 방식으로 앞에서부터 그냥 하나씩 결정해 보면서 "이 수식을 만족하는 해가 존재할 수 있니?" 하고 물어보도록 했고, 그 쿼리 처리를 적당한 전처리를 통해 O(N)에 할 수 있도록 했습니다. 러닝 타임은 1초 미만입니다.


    12년 전 link
  • 꿀호떡
    꿀호떡

    저도 "이 수식을 만족할 수 있나"를 구하는 sub-problem을 정의하고, 앞에서부터 ?를 작은 숫자부터 하나씩 대치하여 풀었습니다.


    12년 전 link
  • wookayin
    wookayin

    뭐 기본적인 idea는 다들 비슷할 것 같고.. DP의 subproblem dimension을 저는 [150][2][2][2][2] 로 했네요..-_-;;


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