SRM 617 DIV1 Middle - PieOrDolphin （復習×）
問題
５０人のプレイヤーが存在する。
毎日コンテストを行い、その勝者２名にイルカ１つとパイ１つをプレゼントする。
どちらにイルカ、どちらにパイをプレゼントしてもよい。
コンテストが終わったとき、各プレイヤーが受け取ったイルカとパイの数の絶対値をできるだけ小さくしたい。
毎日行われるコンテストの勝者２名がわかっているとき、上記を満たすようなプレゼントの仕方を求める。
解き方
問題をグラフに落とすことで単純化できる。
今回はノードを各プレイヤーとする。
エッジは各コンテストの勝者２名を有向グラフで結び、入りをイルカ、出をパイとみなすことでグラフに落とし込むことができる。
このとき、各ノードの入次数と出次数の差を最小化する問題とみなすことができる。
次に、エッジの向きをどのように最適化していけばよいか考える。
あるノードからのエッジについて向きをを入れ替えた際、
つながっているノードの絶対値が増える場合がある。
ここでもう少し考えると、さらにそのノードからエッジが伸びている場合、
中間のノードは±０なので絶対値が変わらないことがわかる。
よって同じノードに戻ってこないようなパスを考えて、それをひっくり返せばよい。
ただし、同じパスの更新のループにならないようにしなければらない。
そこで、終了のノードをどこに持ってくればよいかを考える。
ひとつめの条件は、同じノードに戻ってこないようなパス。
もう一つは、入次数の方が多い場合はより最適化できるので、そこで終わればよいことがわかる。そのノードで終わることで、次にそのノードから同じパスは再現されないので同じ更新は繰り返されない。
よって、同じノードに戻ってこないようなパス、もしくは入次数の方が多いノードで終わるパスを考えて、それを全てひっくり返せばよいことがわかる。
最後に、各ノードは絶対値をいくつまで収束させたらよいかを決めるために、絶対値の最小値はいくつであるか考える。
０が最適な値であるのは自明。
また、奇数のときは最小で１になってしまう。
では、２の場合はどうかを考える。
そのノードから上記のパスの更新を行ったとき、途中のノードの絶対値は大きくならないことがわかる。よって、２の場合は１または０に更新することができる。
よって、各ノードの絶対値は１以下になるように収束させる。
最後に、以上で証明した手順をコードに落とせばよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PieOrDolphin {
public:
vector<int> Distribute(vector<int> choice1, vector<int> choice2) {
int m=choice1.size(),n=50;
vector<int> ret(m,1);
vector<int>in(50,0),out(50,0);
FORE(i,0,m){
out[choice1[i]]++;
in[choice2[i]]++;
}
while(1){
int s=-1;
FORE(i,0,n)if(abs(in[i]-out[i])>=2)s=i;
if(s==-1)break;
if(in[s]>out[s]){
FORE(i,0,m)ret[i]= ((ret[i]==1) ? 2 : 1);
FORE(i,0,n)swap(in[i],out[i]);
}
queue<int> q;
vector<int> pnode(50,-1),pedge(50,-1);
q.push(s);
int t=-1;
while(!q.empty()){
int x=q.front();
q.pop();
if(in[x]>out[x]){
t=x;
break;
}
FORE(i,0,m){
int u,v;
if(ret[i]==1){
u=choice1[i];
v=choice2[i];
}
else{
u=choice2[i];
v=choice1[i];
}
if(u==x&&v!=s){
if(pnode[v]==-1){
pnode[v]=x;
pedge[v]=i;
q.push(v);
}
}
}
}
int x=t;
while(pnode[x]!=-1){
int e=pedge[x];
ret[e]= ((ret[e]==1) ? 2 : 1);
int u=pnode[x];
in[u]++;
out[u]--;
in[x]--;
out[x]++;
x=u;
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PieOrDolphin {
public:
vector<int> Distribute(vector<int> choice1, vector<int> choice2) {
int m=choice1.size(),n=50;
vector<int> ret(m,1);
vector<int>in(50,0),out(50,0);
FORE(i,0,m){
out[choice1[i]]++;
in[choice2[i]]++;
}
while(1){
int s=-1;
FORE(i,0,n)if(abs(in[i]-out[i])>=2)s=i;
if(s==-1)break;
if(in[s]>out[s]){
FORE(i,0,m)ret[i]= ((ret[i]==1) ? 2 : 1);
FORE(i,0,n)swap(in[i],out[i]);
}
queue<int> q;
vector<int> pnode(50,-1),pedge(50,-1);
q.push(s);
int t=-1;
while(!q.empty()){
int x=q.front();
q.pop();
if(in[x]>out[x]){
t=x;
break;
}
FORE(i,0,m){
int u,v;
if(ret[i]==1){
u=choice1[i];
v=choice2[i];
}
else{
u=choice2[i];
v=choice1[i];
}
if(u==x&&v!=s){
if(pnode[v]==-1){
pnode[v]=x;
pedge[v]=i;
q.push(v);
}
}
}
}
int x=t;
while(pnode[x]!=-1){
int e=pedge[x];
ret[e]= ((ret[e]==1) ? 2 : 1);
int u=pnode[x];
in[u]++;
out[u]--;
in[x]--;
out[x]++;
x=u;
}
}
return ret;
}
};
