[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;
}
};
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

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

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


    16년 전 link

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