kmjp's blog

競技プログラミング参加記です

AtCoder ARC #010 : D - 情報伝播

ARC

さて４問目。
本番は後述の強連結成分分解がわからず、部分点10しか取れなかった。
というわけで復習。
http://arc010.contest.atcoder.jp/tasks/arc010_4


各人、最寄のスパイより距離が近い仲間にメッセージを伝達できる。
仲間全員にメッセージを伝えるのに必要な発信元の人数を答える。

本問題は２つのパートに分けられる。

  1. 伝達可能な仲間を列挙する幾何の問題
  2. 有向グラフから最少点被覆となる始点の数え上げ

前者は、愚直に行うとN人の仲間それぞれがM人のスパイとの最短距離を探すのがO(NM)、仲間同士の距離を計算して伝達可能性を判定するのがO(N^2)となる。
部分点ならN<=30なので問題なく処理できる。

実は、N<=1000でも愚直で間に合うようだ。愚直でも1.3sで終わってしまった。
これは問題製作者にとってはミスだったらしい。本当はMがもう１ケタ位大きくしたいんだろうな。

最短距離の検索は愚直だとO(NM)だけど、模範解答ではKD木を使う方法で処理を省略していた。
M>=1000ではスパイの位置がランダムであるため、空間分割で検索対象の点をMの1割以下にしたところ、1秒程度となった。


次に後半、最少点被覆。
N<=10なら、2^10パターンの始点候補を挙げ、DFSで全部の点を網羅できるか確認すればよい。
実際自分もそれで10点稼いだ。

本番中は「入る辺が無い点の数かな、でもそれだとループが対応できないな…」と思っていたけど、これは考えたら強連結成分分解そのものだね。
せっかくなので、強連結成分分解のライブラリを作っておいた。

この問題では、強連結成分分解を行った後、同一強連結成分以外の点から入る辺が無い場合、始点候補とすることで始点を数えることができる。

int N,M;
ll FX[5001],FY[5001];
ll SX[100001],SY[100001];

class G {
public:
	static const int MV = 5000;
	vector<int> E[MV], RE[MV], NUM;
	vector<vector<int> > SC;
	int NV,vis[MV],GR[MV];
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear(); }}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c++);}
		SC.resize(c);
	}
};

vector<int> smap[25][25];

void solve() {
	int f,r,i,j,k,l,res;
	G g;
	
	N=GETi();
	FOR(i,N) { FX[i]=GETi()+1200000000LL; FY[i]=GETi()+1200000000LL;}
	
	M=GETi();
	FOR(i,M) {
		SX[i]=GETi()+1200000000LL; SY[i]=GETi()+1200000000LL;
		smap[SX[i]/100000000][SY[i]/100000000].push_back(i);
	}
	
	g.init(N);
	FOR(j,N) {
		ull mind=(1ULL<<63)-1;
		if(M<2000 || N<=30) {
			FOR(i,M) mind = min(mind,(ull)((FX[j]-SX[i])*(FX[j]-SX[i]))+(ull)((FY[j]-SY[i])*(FY[j]-SY[i])));
		}
		else {
			/* rand */
			int tx = FX[j]/100000000;
			int ty = FY[j]/100000000;
			FOR(k,5) FOR(l,5) FOR(i,smap[tx+(k-2)][ty+(l-2)].size()) {
				int s=smap[tx+(k-2)][ty+(l-2)][i];
				mind = min(mind,(ull)((FX[j]-SX[s])*(FX[j]-SX[s]))+(ull)((FY[j]-SY[s])*(FY[j]-SY[s])));
			}
		}
		
		FOR(k,N) {
			ull dist=(ull)((FX[j]-FX[k])*(FX[j]-FX[k]))+(ull)((FY[j]-FY[k])*(FY[j]-FY[k]));
			if(j!=k && dist<mind) g.add_edge(j,k);
		}
	}
	
	g.scc();
	res=0;
	int vis[5001];
	ZERO(vis);
	FOR(i,N){
		if(vis[i]) continue;
		FOR(j, g.SC[g.GR[i]].size()) vis[g.SC[g.GR[i]][j]]=1;
		int top=1;
		FOR(j, g.SC[g.GR[i]].size()) {
			int id=g.SC[g.GR[i]][j];
			FOR(k,g.RE[id].size()) {
				if(g.GR[g.RE[id][k]] != g.GR[i]) {
					top=0; break;
				}
			}
			if(top==0) break;
		}
		res+=top;
	}
	
	_P("%d\n",res);
}

まとめ

空間分割、強連結成分分解と、こうやればいいんだろうなというのは本番わかったけど、そもそも強連結成分のアルゴリズムの書き方を知らなかったので時間切れした。
今回ライブラリを作ったし、今度からはこれを使おう。
Mが小さくて空間分割の効果がわからなかったのが残念。
KD木使ったことないし練習しておいた方がいいかな…。