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

#include
#include
#include
#include
using namespace std;
class WindowManager
{
public:
vectorscreen(int height, int width, vector windows)
{
vector v;
v.resize(height);
v[0] = "";
for(int i = 0; i < width; i ++)
v[0] += " ";
for(int i = 1; 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가 제일 큰 경우를 찾으면 됩니다.
~~~ cpp

#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를 찾도록 해서 해결했습니다. 그 외에 다른 방법들도 있을 수 있습니다.
~~~ cpp

#include
#include
#include
#include
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 m[i][j] = f[i][j] = 0;
}
void addedge(int a, int b, int c)
{
m[a][b] = c;
}
string moreClasses(string ct, vector 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 rc;
for(int i = 0; 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 {
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;
}
};

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/54695">원문보기</a>]</div>