えらく遠回りな解法を取ってしまった。
https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_e
問題
N頂点の木を成すグラフが与えられる。
なお、各頂点の次数は5以下である。
このうちどこか1個の頂点は特別である。
以下のクエリを14回まで実行可能な時、特別な頂点を求めよ。
- 2つの頂点を指定すると、特別な頂点はどちらに近いか、もしくは等距離かを教えてくれる。
解法
他の人は重心を使う解法が多いようだが、ここは別解法で。
クエリを1回行うと、クエリの結果によって解の候補がクエリの2頂点への距離に応じ、3つのグループのどれか1つに絞られる。
よって、3つのグループの最大要素数が最少となるようなクエリの頂点を選べば、大よそクエリ1回で1/3に候補が絞れることが期待できる。
そのためには、クエリを行う2頂点を総当たりし、3つのグループの各頂点数を高速に求める必要がある。
以下では、LCAを使い2頂点の中点を求めている。また、EulerTour+累積和(BITでもよい)でSubTree内の有効頂点数の数え上げを行った。
int N,Q; vector<int> E[2020]; int P[21][200005],D[200005]; int L[2020],R[2020],eid; int O[2020]; int S[2020]; int ddist[2020][2020]; void dfs2(int cur,int pre,int d,int id) { ddist[id][cur]=d; FORR(e,E[cur]) if(e!=pre) dfs2(e,cur,d+1,id); } int ask(int u,int v) { int ret; cout<<"? "<<u<<" "<<v<<endl; cin>>ret; return ret; } void dfs(int cur) { L[cur]=eid++; ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it); R[cur]=eid; } int getpar(int cur,int up) { int i; FOR(i,20) if(up&(1<<i)) cur=P[i][cur]; return cur; } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N-1) { cin>>x>>y; E[x].push_back(y); E[y].push_back(x); } P[0][1]=1; dfs(1); for(i=1;i<=N;i++) dfs2(i,i,0,i), O[x]=1; FOR(i,19) for(x=1;x<=N;x++) P[i+1][x]=P[i][P[i][x]]; while(1) { Q--; assert(Q>=0); vector<int> C; ZERO(S); for(i=1;i<=N;i++) if(O[i]) { C.push_back(i); S[L[i]+1]++; } for(i=1;i<=N;i++) S[i]+=S[i-1]; if(C.size()==1) { cout<<"! "<<C[0]<<endl; return; } int mi=101010; int LL,RR; FORR(x,C) FORR(y,C) if(D[x]>=D[y] && x!=y) { int lc=lca(x,y); int a,b,c; if(D[x]==D[y]) { int x2=getpar(x,D[x]-D[lc]-1); int y2=getpar(y,D[y]-D[lc]-1); a=S[R[x2]]-S[L[x2]]; b=S[R[y2]]-S[L[y2]]; } else if((D[x]+D[y])%2==0) { int z=D[lc]+(D[x]-D[y])/2; int x2=getpar(x,D[x]-z); int y2=getpar(x,D[x]-z-1); a=S[R[x2]]-S[L[x2]]; b=S[R[y2]]-S[L[y2]]; a-=b; } else { int z=D[lc]+(D[x]-D[y])/2; int x2=getpar(x,D[x]-z-1); a=S[R[x2]]-S[L[x2]]; b=0; } c=C.size()-a-b; if(max({a,b,c})<mi) { mi=max({a,b,c}); LL=x; RR=y; } } j=ask(LL,RR); for(i=1;i<=N;i++) { if(j==LL) { if(ddist[LL][i]>=ddist[RR][i]) O[i]=0; } else if(j==RR) { if(ddist[LL][i]<=ddist[RR][i]) O[i]=0; } else { if(ddist[LL][i]!=ddist[RR][i]) O[i]=0; } } } }
まとめ
重心解も思いついたけど、妙な解法を取ってバグを作りまくってしまった。