TCO09 를 앞두고 거진 한달만에 돌아본 연습.. 발렸다 orz 그래프 문제 250, 중복 처리가 까다로운 500, 그리고 그래프 + 이분매칭의 1000 의 구성. 1k 는 나는 아주 어렵게 풀었는데 다른 사람들은 매우 쉽게 짠 듯.. ㅜㅜ 그리고 이분 매칭용 라이브러리를 만들어 둘 필요가 있다고 느껴짐.. :3
오늘은 너무 피곤해서 코딩 못하겠지만.. --;
두 번째 돈 소스 코드. 1420 점 정도? 그래도 스냅보다 느리다. 500, 1000 모두 나보다 골고루 빠르심. ㅜㅜ
250: CellRemoval: /graph/tree
이진 트리를 표현하는 parent[] 배열이 주어진다. deletedCell 을 루트로 하는 서브트리를 지우면, 트리에 남는 잎 (leaf) 의 수는?
초간단
lang:cpp
struct CellRemoval
{
int cellsLeft(vector <int> parent, int deletedCell)
{
int n = parent.sz;
int ret = 0;
for(int i = 0; i < n; ++i)
{
int j = i;
while(j != deletedCell && parent[j] != -1) j = parent[j];
if(j != deletedCell)
{
bool ok = true;
REP(k,n) if(parent[k] == i) ok = false;
if(ok) ++ret;
}
}
return ret;
}
};
500: DNASequence /dp
DNA Sequence 를 앞에서부터 세 자리씩 자르면 코돈이 되며, 각 코돈을 아미노산에 매칭해서 단백질을 만들 수 있다. DNA 에서 중간의 염기가 임의로 생략될 수 있다고 할 때, 만들어질 수 있는 nonempty 단백질의 수는?
코돈과 아미노산의 매칭이 1:1 이 아니라서 어려웠다. AAACCC 에서, AAA => amino1, ACC => amino1 이라면 중복으로 세기 쉽기 때문이다. 모든 단백질을 재귀호출로 만들어 본다고 가정한 뒤, 이 때 각 단백질에 매칭되는 코돈의 시작 위치가 lexicographically smallest 인 것만 센다고 가정해서 중복을 제거했다.
에디토리얼에 나온 답은, 각 위치에서 시작하고, 그 뒤에서는 시작할 수 없는 단백질의 수를 정의해서 이렇게 푼 듯. 요는, lexicographically largest 를 푼 셈이다. Snap 이랑 소스코드가 똑같아서 기분이 좋았지만, 나는 쓸데없는 최적화를 해서 더 느렸단 문제가..
오랜만에 했더니 머리가 안돌아간다. 처음엔 300점에 풀었음.
lang:cpp
const int M = 1000000007;
const string AGCT("AGCT");
struct DNADeletion
{
vector<vector<string> > codons;
int n, cache[2501], next[2501][4];
string seq;
int go(int here)
{
if(here+2 >= n) return 1;
int& ret = cache[here]; if(ret != -1) return ret;
ret = 1;
REP(next,codons.sz)
{
int end = nearestAfter(here, codons[next]);
if(end <= n) (ret += go(end)) %= M;
}
return ret;
}
int nearestAfter(int canBegin, const vector<string>& codons)
{
int ret = n+1;
REP(i,codons.sz)
{
int here = canBegin;
REP(j,3)
{
if(here < n && seq[here] != codons[i][j])
here = next[here][AGCT.find(codons[i][j])];
++here;
}
ret = min(here, ret);
}
return ret;
}
int differentProteins(vector <string> DNASequence, vector <string> codonTable)
{
seq = accumulate(all(DNASequence), string());
n = seq.sz;
REP(i,4) next[n-1][i] = n;
for(int i = n-2; i >= 0; --i)
REP(j,4)
{
if(seq[i+1] == AGCT[j])
next[i][j] = i+1;
else
next[i][j] = next[i+1][j];
}
map<string,int> amino;
REP(i,codonTable.sz)
{
istringstream inp(codonTable[i]);
string a, b;
inp >> a >> b;
if(amino.count(b) == 0)
{
amino[b] = codons.sz;
codons.resize(codons.sz+1);
}
codons[amino[b]].pb(a);
}
CLEAR(cache,-1);
int ret = 0;
REP(i,codons.sz)
{
int after = nearestAfter(0, codons[i]);
if(after <= n)
(ret += go(after)) %= M;
}
return ret;
}
};
1000 - CompanyRestructuring; /dp/matching/flow/good/again
모든 사람들 간에, 한 사람이 다른 사람을 상사로 관리한 적이 있었는지의 여부가 그래프로 주어진다. 이 그래프엔 사이클이 있을 수 있는데, 같은 사이클 위에 있는 사람들은
- 한 사람이 다른 사람의 상사가 될 수도
- 같은 사람의 직속 부하가 될 수도 없다.
조직 개편을 하려고 하는데, 어떤 사람이 다른 사람의 직속 상사가 되려면 이전에 상사였던 적이 있어야 한다. 이 때, 이 조건을 지키기 위해 그래프를 몇 개로 분할해야 하는가? .. 뭐 이런 문제.
일단 SCC 가 연관된다는 것은 당연한 것 같고.. 맨 처음엔 사이클 간선을 없애고 생각했다 (OneWayStreet 에서처럼). SCC 내부의 간선을 모두 없애면 DAG 가 된다. 이 때, 맨 앞에서부터 순서대로 배정해 나간다. 각 조직도의 트리를 맨 위에서부터 만들어 나가는 것은 항상 가능하다. 이 때, 한 사람은 한 SCC 안에 포함된 부하는 한 명밖에 가질 수 없어서, bipartite matching 이 필요하게 된다. -_-;
아쒸, 나는 존내 어렵게 풀었는데, 스냅은 왜 이렇게 쉽담.
lang:cpp
class NetworkFlow
{
public:
// 내부 함수 및 변수
// =================
// MAXV 는 최대 정점의 수
enum { MAXV = 110 };
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;
}
void setEdge(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 CompanyRestructuring
{
int n;
vector<vector<bool> > managed, sup, cycleRemoved;
vector<int> scc;
void dfs(int here, int no)
{
scc[here] = no;
REP(there,n) if(sup[here][there] && sup[there][here] && scc[there] == -1)
dfs(there, no);
}
bool canManage(int a, int b)
{
return managed[a][b] && !sup[b][a];
}
int fewestDivisions(vector <string> hasManaged)
{
n = hasManaged.sz;
managed.resize(n, vector<bool>(n, false));
REP(i,n) REP(j,n) if(hasManaged[i][j] == 'Y')
managed[i][j] = true;
sup = managed;
REP(k,n) REP(i,n) REP(j,n) if(sup[i][k] && sup[k][j]) sup[i][j] = true;
cycleRemoved = managed;
REP(i,n) REP(j,n) if(sup[i][j] && sup[j][i]) cycleRemoved[i][j] = false;
scc.resize(n, -1);
int comps = 0;
REP(i,n) if(scc[i] == -1) dfs(i, comps++);
vector<NetworkFlow*> nf(comps);
REP(i,comps) nf[i] = new NetworkFlow(2 + 2 * n);
vector<int> indegree(n);
REP(i,n) REP(j,n) if(cycleRemoved[i][j]) indegree[j]++;
vector<bool> taken(n, false);
int took = 0, ret = 0;
while(took < n)
{
vector<int> add;
REP(i,n) if(indegree[i] == 0) { add.pb(i); indegree[i] = -1; }
REP(i,add.sz)
{
int here = add[i];
REP(there,n) if(taken[there] && canManage(there, here))
nf[scc[here]]->setEdge(2 + there, 2 + n + here, 1);
nf[scc[here]]->setEdge(2 + n + here, 1, 1);
if(nf[scc[here]]->go(0, 1) == 0)
++ret;
}
REP(i,add.sz) REP(j,n) if(cycleRemoved[add[i]][j]) --indegree[j];
REP(i,add.sz) taken[add[i]] = true;
REP(i,add.sz)
{
int here = add[i];
REP(there,n) if(!taken[there] && canManage(here, there))
{
nf[scc[there]]->setEdge(0, 2+here, 1);
nf[scc[there]]->setEdge(2 + here, 2 + n + there, 1);
}
}
took += add.sz;
}
return ret;
}
};
그래도 두 번째 풀었을 땐 컴파일하자마자 정상 동작해서 좋았다.
