ARC083 F : Collecting Balls(1200)
作成日：2017.09.18
最終更新日：2017.09.18
問題概要
$2N$個のボールが$(x_i , y_i)$の位置に、$2N$台のロボットが$(a,0)$または$(0,b)$ $(1 \leq a,b \leq N)$の位置にある。
$(a,0),(0,b)$の位置にあるロボットは起動すると、それぞれ$x=a , y=b$上にあるボールのうち$y,x$座標の値が最小のものを回収して止まる。
回収できるボールがない場合は何もせずに停止する。
各ロボットは一度しか起動できず、2つ以上のロボットを同時に動作させることはできない。
ボールをすべて回収できるロボットの起動順序の個数を$10^9 + 7$で割った余りを求めよ。
制約
$2 \leq N \leq 10^5$
$1 \leq x_i , y_i \leq N$
$i \neq j$ならば$(x_i , y_i) \neq (x_j , y_j)$
考え方
ロボットの配置が2部グラフを示唆しているので、それを構築することを考える。
具体的にはロボットを頂点とし、各ボールにおいてそれを回収できる2体のロボットの間に辺を張る。
これにより求めるものは、頂点とそれにつながる辺のうちの1つを取り除いていく(選ばなかった辺は残す)操作を繰り返しグラフを空にする時の取り除き方の個数となる。
まず2部グラフが連結でない時を考える。
異なる連結成分間には操作の順序に対する制約が存在しない。
よって連結成分ごとに操作順序を決めた後、どの連結成分の操作を行うかを並べれば良い。
これは簡単に求めることができる。
以下1つの連結成分について考える。
そもそも連結成分に含まれる辺と頂点の個数が異なる時は操作を終えられないので答えは$0$になる。
そうでない時、頂点と辺は同じ個数あるので閉路がちょうど一つ存在している。
操作を終えるには、次数が1の頂点はそれにつながる辺を取り除く必要がある。
とりあえず操作順序は考えないことにしてその操作を繰り返すと、操作の行い方は1通りであり閉路が残る。
その後閉路中のある頂点に対する操作は2通りであり、その頂点に対して操作を行うと後は各頂点に対する操作は1通りに定まる。
以上より各連結成分において、各頂点への辺の割り当て方は2通りしかない。
よってこれは両方試すことができる。
最後に各頂点への辺の割り当て方を決めた時の操作順序の個数を考える。
元の問題に戻ると、ロボットに割り当てられたボールよりロボット側にあるボールは先に取られている必要があることが分かる。
これによって定まる順序に従い有向辺を張ったボールを頂点とするグラフ$G$を構築する。
辺の向きに従って頂点を辿ると、問題の条件からその頂点に対応するボールの座標のいずれかは増加することが分かる。
したがって$G$はDAGをなしている。
DAGをトポロジカルソートする方法の個数は求めることができる。
計算量はほぼ$O(N)$(Union-Findを使うため)であるから、この問題を解くことができた。
ソースコード
マクロ等はこちら
Union_Find
void uni(int a , int b)
頂点$a$を含む集合と頂点$b$を含む集合を併合する
int boss(int a)
頂点$a$を含む集合の代表である頂点を返す
const int MC = 100010;
const LL mod = 1e9 + 7;
int N;
int x[MC*2] , y[MC*2];
vector<int> V[MC*2]; //頂点iと辺で結ばれている頂点の集合
vector<int> C[MC*2]; //頂点iを代表とする集合
vector<int> G[MC*2];
vector<int> rG[MC*2]; //Gの逆グラフ
int e[MC*2]; //頂点iを代表とする連結成分に含まれる辺の数
int al[MC*2]; //頂点iに割り当てられた辺で結ばれている頂点
int co[MC*2];
int sz[MC*2];
LL h[MC*2];
LL fct[MC*2]; //i!
LL inv[MC*2]; //(i!)^(-1)
LL ans;
Union_Find uf;
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MC*2){
fct[i] = fct[i-1] * i % mod;
}
LL x = fct[MC*2-1];
inv[MC*2-1] = 1;
for(int i = mod - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (inv[MC*2-1] *= x) %= mod;
(x *= x) %= mod;
}
repm(i,MC*2-1,0){
inv[i-1] = inv[i] * i % mod;
}
}
LL fanc(int z){
queue<int> Q;
LL k = fct[(int)C[z].size()];
for(auto u : C[z]) G[u].clear();
for(auto u : C[z]){
rG[u].clear();
for(auto w : V[u]){
if(w == al[u]) break;
G[w].PB(u);
rG[u].PB(w);
}
sz[u] = 0;
h[u] = 1;
co[u] = G[u].size();
if(co[u] == 0) Q.push(u);
}
while(!Q.empty()){
int u = Q.front(); Q.pop();
sz[u] = 1;
for(auto w : rG[u]){
(h[u] *= h[w]) %= mod;
(h[u] *= inv[sz[w]]) %= mod;
sz[u] += sz[w];
}
(h[u] *= fct[sz[u]-1]) %= mod;
if(G[u].size() == 0){
(k *= h[u]) %= mod;
(k *= inv[sz[u]]) %= mod;
}
for(auto w : G[u]){
--co[w];
if(co[w] == 0) Q.push(w);
}
}
return k;
}
LL calc(int z){
queue<int> Q;
int t = 0;
for(auto u : C[z]) if(V[u].size() == 1) Q.push(u);
while(!Q.empty()){
int p = Q.front(); Q.pop();
for(auto u : V[p]){
if(al[u] == 0){
al[p] = u;
++co[u];
++t;
if(V[u].size() == co[u] + 1) Q.push(u);
}
}
}
int r,s;
for(auto u : C[z]){
if(al[u] == 0){
r = s = u;
break;
}
}
while(C[z].size() > t + 1){
for(auto u : V[r]){
if(al[u] == 0){
al[r] = u;
r = u;
++t;
break;
}
}
}
al[r] = s;
LL rv = fanc(z);
queue<P2> Q2;
r = s;
while(Q2.empty() || r != s){
Q2.push(MP(al[r],r));
r = al[r];
}
while(!Q2.empty()){
al[Q2.front().first] = Q2.front().second;
Q2.pop();
}
return (rv + fanc(z)) % mod;
}
int main(){
build();
cin >> N;
repp(i,0,2*N){
cin >> x[i] >> y[i];
V[x[i]].PB(MC+y[i]);
V[MC+y[i]].PB(x[i]);
uf.uni(x[i],MC+y[i]);
}
repp(i,1,N+1){
C[uf.boss(i)].PB(i);
e[uf.boss(i)] += V[i].size();
C[uf.boss(MC+i)].PB(MC+i);
e[uf.boss(MC+i)] += V[MC+i].size();
sort(V[i].begin(),V[i].end());
sort(V[MC+i].begin(),V[MC+i].end());
}
ans = fct[2*N];
repp(i,1,N+1){
if(uf.boss(i) == i){
if(C[i].size() * 2 != e[i]){
cout << 0 << endl;
return 0;
}
(ans *= calc(i)) %= mod;
(ans *= inv[(int)C[i].size()]) %= mod;
}
if(uf.boss(MC+i) == MC+i){
if(C[MC+i].size() * 2 != e[MC+i]){
cout << 0 << endl;
return 0;
}
(ans *= calc(MC+i)) %= mod;
(ans *= inv[(int)C[MC+i].size()]) %= mod;
}
}
cout << ans << endl;
return 0;
}解法まとめ
ロボットを頂点、ボールを辺とするグラフを構築し連結成分ごとに考える。(122-135行)
連結成分に含まれる頂点と辺の個数が異なれば答えは$0$である。(139-142,147-150行)
そうでない場合、頂点に辺を割り当てる2通りの方法をともに試す。(73-104,106-115行)
割り当て方それぞれに対し、辺の取り方に関する制約をDAG(グラフ$G$)にし、トポロジカルソートのやり方を求める。(35-70行)
最後に連結成分をまとめて答えを求める。(136,143,144,151,152行)