10월 14일 오전 1시에 진행되었던 SRM 371의 Div 1 결과입니다.

SRM 369의 레이팅 무효처리의 충격을 딛고(.........) 다시금 10위권에 진입했습니다. 모 사이트에서 시간대별 퍼포먼스 분석해놓은 것을 보았을 때 이 시간대에 한 것이 전체적으로 가장 성적이 좋았었는데, 현실을 인정하고 올빼미처럼 살아야 하나봅니다.
Easy(250pt) : Div 2 Medium과 같은 문제입니다.
제 소스를 약간 고친 것을 첨부합니다. Div 2 Lecture와 방법도 같습니다.
[code]
vector thronePosition(int width, int length)
{
if ( width >= 3 && length >= 3 )
{
int plus = width;
if (plus > length) plus = length;
plus -= 1;
plus /= 2;
vector res = thronePosition(width - plus*2, length - plus*2);
res[0] += plus;
res[1] += plus;
return res;
}
vector res;
if ( width == 1 )
{
res.push_back(0);
res.push_back(length - 1);
}
else if ( length == 1 )
{
res.push_back(width - 1);
res.push_back(0);
}
else if ( width == 2 || length == 2 )
{
res.push_back(0);
res.push_back(1);
}
return res;
};
[/code]
Middle(500pt) : 우리편 n명과 상대편 n명의 전투력을 받아서, 총 승점(승리 2 비김 1 패배 0)이 가장 높도록 1:1 대응이 되는 대진을 만들어라. 라는 문제입니다.
해법은 실로 여러가지가 있습니다. 그리디 다이나믹 맥스플로우 등등... 그 중에서 제가 한 것은 다이나믹입니다. 우리편 최강자가 상대편 최강자보다 세다면 무조건 그 대응을 시킵고, 우리편 최강자가 더 약하다면 상대편 최강자에게 우리편 제일 약한 애를 붙입니다. 같은 파워를 가졌다면 두 가지를 다 해봐서 그 중에 최대를 구합니다. 이 과정을 작은 문제부터 풀어나가면 됩니다.
이번에도 제 소스를 가져왔습니다.
score[j][k][i] = 우리편은 j번~j+i번, 상대편은 k번~k+i번일 때의 가능한 우리편의 최대 승점 - 따라서 score[0][0][n-1]이 답이 됩니다.
[code]
int score[100][100][100] = {0};
class ChessMatchup
{
public:
int maximumScore(vector us, vector them)
{
sort(us.begin(), us.end());
sort(them.begin(), them.end());
int n = us.size();
for (int i=0; i for (int j=0; j for (int k=0; k {
if ( i==0 )
{
if ( us[j]>them[k] ) score[j][k][0] = 2;
else if ( us[j] else score[j][k][0] = 1;
}
else
{
if ( us[j+i]>them[k+i] ) score[j][k][i] = score[j][k][i-1] + 2;
else if (us[j+i] else
{
int case1 = score[j][k][i-1] + 1;
int case2 = score[j+1][k][i-1];
score[j][k][i] = max(case1, case2);
}
}
}
return score[0][0][n-1];
};
};
[/code]
Hard(900pt) : a 얼핏 보면 가능한 총 갯수가 2^30이므로 brute force로 안 풀릴 거 같지만, a 저는 이렇게 짰습니다.
1) 컴포넌트들로 분리
2) 각 컴포넌트에서의 ordering 수 계산 - dp를 위장한 brute force
3) 컴포넌트가 여러 개 있을 때는 각 컴포넌트에서의 ordering 수를 모두 곱해야 합니다. 여기에다가 각 component에서의 ordering은 서로 독립적으로 이루어질 수 있으므로, 조합론을 이용해서 ordering에 곱해야 하는 수를 구해야 합니다. 이 수는 각 컴포넌트에 대해서 (전체에서 이전까지 처리 안됐던 노드 수)C(이번에 처리하는 노드수) 입니다. 예를 들어 전체 타겟이 10개고 노드가 세 컴포넌트에 4 3 3으로 나누어졌으면 계산 결과에 10C4 * 6C3 * 3C3을 곱해야 합니다.
마지막으로, 답은 이 수를 1000003으로 나눈 나머지이므로, 각 단계마다 이 수로 나눈 나머지만 저장합니다.
[code]
int check[50] = {0};
int nn;
vector A;
vector B;
class RaceOrdering
{
public:
void start_check(int now, int cnt)
{
if ( check[now] ) return;
check[now] = cnt;
for (int i=0; i {
if ( A[i]==now ) start_check(B[i], cnt);
if ( B[i]==now ) start_check(A[i], cnt);
}
}
int countOrders(int n, vector first, vector second)
{
nn = n;
A = first;
B = second;
int cnt = 0;
int graph[40][40] = {0};
int remain_n = n;
long long res = 1;
for (int i=0; i for (int i=0; i if (!check[i])
{
start_check(i, ++cnt);
vector V;
for (int j=0; j if (check[j]==cnt) V.push_back(j);
int sz = V.size();
int new_graph[40][40] = {0};
vector > adj(sz);
for (int j=0; j for (int k=0; k if ( graph[V[j]][V[k]] )
{
new_graph[j][k] = 1;
adj[k].push_back(j);
}
vector S(1< for (int j=0; j<(1< {
if (j==0) { S[j] = 1; continue; }
for (int k=0; k if ( (j>>k)%2 )
{
int ok = 1;
for (int l=0; l if ( (j>>adj[k][l])%2 ) { ok = 0; break; }
if (ok) S[j] += S[j-(1<<k)];
}
S[j] %= 1000003;
}
long long now_ans = S[-1+(1<<sz)];
// calc remain_n C sz
long long combi = 1;
for (int j=0; j<sz; j++)
combi = (combi * (remain_n-j)) / (j+1);
remain_n -= sz;
res = (res * now_ans) % 1000003;
res = (res * combi) % 1000003;
printf("sz=%d now_ans=%lld combi=%lld\n", sz, now_ans, combi);
}
return res;
};
};
[/code]