問題
http://community.topcoder.com/stat?c=problem_statement&pm=10687&rd=13907
解き方
全探索可能。
DFSを用いて各チームの勝ち負けについてすべて調べ、
行列の対角側についてはすでに調べているのですでに決められた値を代入して
更新していく。
コード
int a[5][5];
set<vector<int> > s;
class TheBasketballDivOne {
public:
void rec(int n,int x,int y){
if(n==x){
int b[n];
memset(b,0,sizeof(b));
FORE(i,0,n)FORE(j,0,n)b[i]+=a[i][j];
vector<int> vx;
FORE(i,0,n)vx.push_back(b[i]);
sort(vx.rbegin(),vx.rend());
s.insert(vx);
return;
}
int xx=x+(y==n-1 ? 1 : 0);
int yy=(y+1)%n;
if(x>y){
a[x][y]=2-a[y][x];
rec(n,xx,yy);
}
else if(y>x){
FORE(i,0,3){
a[x][y]=i;
rec(n,xx,yy);
}
}
else rec(n,xx,yy);
}
int find(int n, int m) {
int ret=0;
s.clear();
rec(n,0,0);
for(set<vector<int> >::iterator it=s.begin();it!=s.end();it++){
if((*it)[0]==m)ret++;
}
return ret;
}
};
set<vector<int> > s;
class TheBasketballDivOne {
public:
void rec(int n,int x,int y){
if(n==x){
int b[n];
memset(b,0,sizeof(b));
FORE(i,0,n)FORE(j,0,n)b[i]+=a[i][j];
vector<int> vx;
FORE(i,0,n)vx.push_back(b[i]);
sort(vx.rbegin(),vx.rend());
s.insert(vx);
return;
}
int xx=x+(y==n-1 ? 1 : 0);
int yy=(y+1)%n;
if(x>y){
a[x][y]=2-a[y][x];
rec(n,xx,yy);
}
else if(y>x){
FORE(i,0,3){
a[x][y]=i;
rec(n,xx,yy);
}
}
else rec(n,xx,yy);
}
int find(int n, int m) {
int ret=0;
s.clear();
rec(n,0,0);
for(set<vector<int> >::iterator it=s.begin();it!=s.end();it++){
if((*it)[0]==m)ret++;
}
return ret;
}
};