[editorial] SRM200 Division 1

  • ipknHama
    ipknHama

    겨울방학 SRM 모임 첫 연습이었습니다.
    ipkn, domeng, libe, dgsquare, altertain, xhae 님이 참가했었고,
    세 개 다풀어서 오오! 했다가 systest에 orz 했네요.
    300 WindowManager여러 개의 네모 상자가 주어질 때, 문제에 주어진대로 해당 상자를 칠하는 문제입니다. 상자의 크기는 가로 세로 100000000까지로, 매우 큰 상자가 입력으로 들어올 수 있지만, 실제로 그려야 하는 영역은 100x100의 크기이기 때문에, 50 (각 상자 수) * 100 * 100 의 시간으로 해결할 수 있는 문제였습니다.

    #include <vector>
    #include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    class WindowManager
    {
    public:
    vector<string>screen(int height, int width, vector<string> windows)
    {
        vector<string> v;
        v.resize(height);
        v[0] = "";
        for(int i = 0; i < width; i ++)
            v[0] += " ";
        for(int i = 1; i <height;i++)
        {
            v[i] = v[0];
        }
        for(int i = 0; i < windows.size(); i ++)
        {
            istringstream is(windows[i]);
            int tlv, tlh, vs, hs;
            string fills;
            is >> tlv >> tlh >> vs >> hs >>fills;
            char fill = fills[0];
            for(int j = max(tlv, 0); j < min(tlv+vs, height);j++)
            for(int k = max(tlh, 0); k < min(tlh+hs, width); k++)
            {
                if (j == tlv || j == tlv + vs-1)
                {
                    if (k == tlh || k == tlh + hs - 1)
                    {
                        v[j][k] = '+';
                    }
                    else
                        v[j][k] = '-';
                }
                else if (k == tlh || k == tlh + hs - 1)
                {
                    v[j][k] = '|';
                }
                else 
                    v[j][k] = fill;
            }
        }
        return v;
    }
    };
    

    500 NC Multiplication
    늘 하던 곱셈 대신에, 각 자리수 별로 곱셈을 한 결과를 자리수 별로 더한 값이 주어질때 원래 값을 추측하는 문제입니다.
    즉 23 * 45 = (2 * 4, 3 * 4 + 2 * 5, 3 * 5) = (8, 22, 15) 가 주어지면, 23과 45를 찾습니다. 이런 A, B는 여러 개 있을 수 있으므로, 그런 수 중 A>B이면서 A, B의 차이가 최소가 되는 A, B를 찾아 A를 리턴합니다. 없는 경우 -1을 리턴합니다.
    문제 조건에서, 원래 수 A, B의 곱이 1014을 넘지 않는단 조건으로 부터, B < 10^7 임을 알 수 있습니다. 또한, NC곱의 값을 10배씩 하면서 더하면 A, B의 곱을 바로 알 수 있습니다. 즉, B값에 대해 루프를 돌면서 가능한 B 값에 대해 NC곱이 같은 결과가 나오는지 확인하여 그중 A가 제일 큰 경우를 찾으면 됩니다.

    #include <vector>
    #include <sstream>
    #include <iostream>
    #include <string>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    class NCMultiplication
    {
    bool finded;
    ll mina_b;
    ll fa;
    void check_vector(ll la, ll lb, string a, string b, vector<int>& test)
    {
    //cout << la << ' ' << lb << endl;
        vector<int> v;
        v.resize(test.size());
        for(int i = 0; i < a.size(); i ++)
        for(int j = 0;j < b.size(); j ++)
        {
            if (i+j >= v.size())
                return;
            v[i+j] += (a[i]-'0') * (b[j]-'0');
        }
    //    for(int i = 0; i < v.size(); i ++)
        //cout << v[i] << ' ';
    //    cout << endl;
        for(int i = 0; i < v.size(); i ++)
        {
            if (v[i] != test[i])
                return;
        }
        if (la >= lb)
            if (!finded || finded && mina_b > la - lb)
            {
                finded = true;
                mina_b = la - lb ;
            fa = la;
            }
    }
    public:
    ll findFactors(vector<int> digits)
    {
        finded = false;
        ll orig = 0;
        for(int i = 0; i < digits.size(); i ++)
        {
            orig *= 10;
            orig += digits[i];
        }
        ll b = (ll)sqrt(orig*1.0)+2;
        while(b)
        {
            if (orig % b == 0)
            {
                cout << b << ' ' << orig;
                ll a = orig / b;
                ostringstream osa, osb;
                osa << a; osb << b;
                string sa = osa.str();
                string sb = osb.str();
                check_vector(a,b,sa,sb,digits);
                if (finded)
                    break;
            }
            b --;
        }
        if (finded)
            return fa;
        return -1;
    }
    };
    

    1000 Graduation졸업하기 위해선 만족시켜야 하는 규칙들이 주어집니다. 규칙들은 다 동일한 형태로, 어떤 과목들 중에서 k개 이상의 과목을 들어야 한다 라는 조건입니다. 즉, 2ABCD 라면, A, B, C, D 중에서 두 과목 이상을 들어야 이 규칙을 만족시킬 수 있습니다. 또 동시에 한 과목은 두 규칙을 만족시키는데 사용될 수 없습니다. 즉, 2ABC, 2BCD라는 두 규칙이 있다면, AB는 2ABC를, CD는 2BCD를 만족시키는데 사용되는 방법밖에 없습니다.
    현재 수강한 과목들이 주어질 때, 어떤 과목들을 추가로 더 수강하면 규칙들을 모두 만족시킬 수 있는지 구하는 문제입니다. 단, 수강해야하는 과목 수는 최소로 해야하고, 최소인 여러가지 경우 중에서 수강하는 과목의 알파벳들이 사전순으로 제일 앞서는 경우를 구해야합니다.
    이 문제는 네트워크 플로우를 이용하여 해결할 수 있습니다. source와 sink를 하나 두고, source에 각 과목들로 가는 가중치 1의 간선과,
    과목에서 자신과 관련있는 규칙들로 가는 가중치 1의 간선, 그리고 규칙 별로 수강해야하는 과목 수와 같은 가중치를 가지는 sink로 가는 간선을 추가하여, maximum flow를 구했을 때, 그 값이 규칙별 수강해야하는 과목 수 합과 같으면 해당 규칙들을 만족할 수 있습니다.
    여기서 기존에 들은 과목을 포함하여 사전적으로 제일 먼저인 수강할 과목 목록을 구해야 하는데, 저는 maximum flow를 계산할 때 수강한 과목 이거나 알파벳으로 우선하는 과목을 먼저 방문하도록 path를 찾도록 해서 해결했습니다. 그 외에 다른 방법들도 있을 수 있습니다.

    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    int on;
    int n;
    int m[200][200];
    int f[200][200];
    class Graduation
    {
    public:
    string order;
    int idx(char c)
    {
        for(int i = 0; i < order.size(); i ++)
            if (c == order[i])
                return i;
        return -1;
    }
    int v[200];
    int p[200];
    int fl;
    int dfs(int s,int e, int l = 0)
    {
        p[l] = s;
        v[s] = 1;
        if (s == e)
        {
            fl = l;
            return 1;
        }
        for(int i = 0 ; i < n; i ++)
            if ((m[s][i]-f[s][i])>0 && !v[i])
            {
                int ret = dfs(i, e,l+1);
                if (ret)
                    return 1;
            }
    //    v[s]=0;
        return 0;
    }
    int maxflow(int s, int e)
    {
        int cost = 0;
        while(1)
        {
            for(int i = 0; i < n; i ++) v[i] = 0;
            if (dfs(s, e))
            {
                int v = 20000;
                for(int i = 0; i < fl; i ++)
                {
                    if (v > m[p[i]][p[i+1]]-f[p[i]][p[i+1]])
                        v = m[p[i]][p[i+1]]-f[p[i]][p[i+1]];
                }
                cout << v ;
                cout << endl;
                cost += v;
                for(int i = 0; i < fl; i ++)
                {
                    f[p[i]][p[i+1]] += v;
                    f[p[i+1]][p[i]] -= v;
                }
            }
            else
                break;
        }
        return cost;
    }
    void clear(int n )
    {
        for(int i = 0; i < n; i ++)
        for(int j = 0;j <n;j++)
        m[i][j] = f[i][j] = 0;
    }
    void addedge(int a, int b, int c)
    {
        m[a][b] = c;
    }
    string moreClasses(string ct, vector<string> rs)
    {
        sort(ct.begin(),ct.end());
        order = ct;
        for(char c = 33; c <= 126; c ++)
        {
            if (c >= '0' && c <= '9')
                continue;
            if (find(ct.begin(), ct.end(), c)==ct.end())
                order += c;
        }
        int totalcost = 0 ;
        vector<int> rc;
        for(int i = 0; i <rs.size(); i ++)
        {
            int v = 0;
            for(int j = 0; j < rs[i].size(); j ++)
            {
                if (rs[i][j] >= '0' && rs[i][j] <= '9')
                {
                    v*=10;
                    v+=rs[i][j] - '0';
                }
                else
                break;
            }
            rc.push_back(v);
            totalcost += v;
        }
        n = order.size();
        on = n;
        n += rs.size();
        int vs = n ++; // s;
        int ve = n ++; // e;
        clear(n);
        for(int i = 0; i < rs.size(); i ++)
        {
            int c = rc[i];
            for(int j = 1;j <rs[i].size(); j ++)
            {
                if (rs[i][j] < '0' || rs[i][j] > '9')
                {
                cout << rs[i][j];
                addedge(idx(rs[i][j]), on+i, 1);
                }
            }
            addedge(on+i, ve, c);
        }
        for(int i = 0; i < order.size(); i ++)
        {
            addedge(vs, i, 1);
        }
        int cost = maxflow(vs, ve);
        if (cost < totalcost)
            return "0";
        string s;
        for(int i = ct.size(); i < order.size(); i ++)
        {
            if (f[vs][i])
            {
                s += order[i];
            }
        }
        return s;
    }
    };
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

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

    저는 1000점 문제를 mincost-maxflow로 풀었어요. 알파벳에 해당하는 간선 빼고, 나머지 모든 간선에 cost를 0으로 합니다. 알파벳에 해당하는 간선은 사전순으로 적당히 큰 값으로 오름차순이 되게 cost를 정하면 됩니다. (저는 '10000+아스키코드값'으로 했어요.)
    maxflow나 mincost-maxflow나 둘다 라이브러리로 만든 걸 이용해서 쓰는데, edmond-karp를 구현한 maxflow로는 사전순으로 먼저 유량을 흘리는 게 불가능할 것 같더라고요.


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