페글이랑 비주얼드를 너무 열심히 해서 눈깔이 어지러운 상태에서 돌았다.. =_= 600 에서 실수해서 틀림. 제정신이 아니다. 초간단 250, 구현 550, 네트워크 플로 950 순서.
250 Underprime
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
struct Underprimes
{
int howMany( int A, int B )
{
VI p;
for(int i = 2; i <= 320; i++)
{
bool ok = true;
REP(j,p.sz) if(i % p[j] == 0) ok = false;
if(ok) p.pb(i);
}
int ret = 0;
FOR(i,A,B+1)
{
int factors = 0, val = i;
REP(j,p.sz) while(val % p[j] == 0) { val /= p[j]; ++factors; }
if(val > 1) ++factors;
if(count(all(p), factors)) ++ret;
}
return ret;
}
};
550 BedroomFloor
2개짜리 잘라내고 남는것을 1개짜리에 쓰는 부분 계산을 잘못해서 틀림. ;ㅁ;
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<long long> VI;
VI& operator += (VI& a, const VI& b)
{
REP(i,a.sz) a[i] += b[i];
return a;
}
struct BedroomFloor
{
int rup(int x) { return ((x+4)/5) * 5; }
int rdn(int x) { return (x/5)*5; }
VI solve(int y1, int x1, int y2, int x2)
{
if(y2 <= y1 || x2 <= x1) return VI(6);
VI ret(6);
for(int y = rdn(y1); y < y2; y += 5)
for(int x = rdn(x1); x < x2; x += 5)
{
int xoverlap = min(x+5, x2) - max(x, x1);
int yoverlap = min(y+5, y2) - max(y, y1);
if(xoverlap <= 0 || yoverlap <= 0) continue;
if((y/5)%2 == (x/5)%2)
{
// horz cell
ret[xoverlap] += yoverlap;
}
else
{
// vert cell
ret[yoverlap] += xoverlap;
}
}
return ret;
}
long long numberOfSticks( int x1, int y1, int x2, int y2 )
{
VI needed(6);
if(x2 - x1 <= 5 || y2 - y1 <= 5)
needed = solve(y1, x1, y2, x2);
else
{
long long xx1, yy1, xx2, yy2;
xx1 = rup(x1); yy1 = rup(y1);
xx2 = rdn(x2); yy2 = rdn(y2);
long long t = ((yy2-yy1)/5) * ((xx2-xx1)/5);
needed[5] += t*5;
needed += solve(y1, x1, yy1, x2);
needed += solve(yy2, x1, y2, x2);
needed += solve(yy1, x1, yy2, xx1);
needed += solve(yy1, xx2, yy2, x2);
}
long long ret = needed[5];
ret += needed[4];
needed[1] = max(0LL, needed[1] - needed[4]);
ret += needed[3];
needed[2] -= needed[3];
if(needed[2] < 0)
needed[1] += needed[2] * 2;
else
{
long long buy = (needed[2] + 1) / 2;
needed[1] -= buy * 5 - needed[2] * 2;
ret += buy;
}
ret += (max(0LL, needed[1]) + 4) / 5;
return ret;
}
};
950 NowhereLand
각 agency 를 각각 따로 풀 수 있다. 그러고 나면 black 으로 컬러링 된 노드와 white 로 컬러링 된 노드가 있고, 이들 간의 연결을 끊는 문제가 되는데 => min cut.
lang:cpp
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
class NetworkFlow
{
public:
// 내부 함수 및 변수
// =================
// MAXV 는 최대 정점의 수
enum { MAXV = 210 };
int flow[MAXV][MAXV], cap[MAXV][MAXV], totalFlow, V;
// (a, b) 간선으로 c 만큼의 유량을 보낸다
void push(int a, int b, int c) { flow[a][b] += c; flow[b][a] = - flow[a][b]; }
// (a, b) 간선의 residual capacity 를 반환한다
int res(int a, int b) { return cap[a][b] - flow[a][b]; }
// 인터페이스
// ==========
// V 는 정점의 최대 수
NetworkFlow(int V): V(V)
{
assert(V <= MAXV);
memset(flow, 0, sizeof(flow));
memset(cap, 0, sizeof(cap));
totalFlow = 0;
}
// (a, b) 간선의 capacity 에 c 를 더한다
void addEdge(int a, int b, int c)
{
cap[a][b] += c;
}
// source 로부터 sink 까지 한 번 augmenting path 를 찾아 보내고, 이 path 의 유량을 반환한다
int pushFlow(int source, int sink)
{
vector<int> pred(V, -1); queue<int> q;
q.push(source); pred[source] = source;
while(!q.empty() && pred[sink] == -1)
{
int u = q.front(); q.pop();
for(int v = 0; v < V; ++v) if(res(u,v) > 0 && pred[v] == -1) { pred[v] = u; q.push(v); }
}
if(pred[sink] == -1) return 0;
int h, amt = 2147483647;
h = sink; while(pred[h] != h) { amt = min(amt, res(pred[h], h)); h = pred[h]; }
h = sink; while(pred[h] != h) { push(pred[h], h, amt); h = pred[h]; }
totalFlow += amt;
return amt;
}
// source 로부터 sink 까지의 최대 유량을 반환한다
int go(int source = 0, int sink = 1)
{
int ret = 0, f;
while(f = pushFlow(source, sink))
ret += f;
return ret;
}
};
struct NowhereLand
{
int placeGuards( vector <string> cities, int k, vector <string> guards, vector <string> agencies )
{
int ret = 0, n = cities.sz;
VVI has(n, VI(k)), canHave(n, VI(k));
REP(i,n)
{
istringstream inp1(guards[i]);
istringstream inp2(agencies[i]);
int t;
while(inp1 >> t) has[i][t] = 1;
while(inp2 >> t) canHave[i][t] = 1;
}
REP(agency,k)
{
NetworkFlow* nf = new NetworkFlow(2 + cities.sz);
REP(i,n)
{
if(has[i][agency]) nf->addEdge(0, 2+i, 10000);
if(!canHave[i][agency]) nf->addEdge(2+i, 1, 10000);
REP(j,n) if(i != j && cities[i][j] == '1')
nf->addEdge(2+i, 2+j, 1);
}
ret += nf->go();
delete nf;
}
return ret;
}
};
