Codeforces #380 Div1 C. Subordinates

木構造に関する問題、たまに上司と部下の設定があるよね。
http://codeforces.com/contest/737/problem/C

問題

N個の頂点からなる根付グラフがある。
根はS番の頂点である。

各頂点iの根からの深さがD[i]であるという情報がある。
ただこの情報は一部誤っている(つまりそのようなDを満たす根付き木が生成できない)可能性がある。
Dを満たす根付き木が生成できるためには、最低何個の情報を修正しなければならないか。

解法

まず「Dを満たす根付き木が生成できる」には以下が成り立てばよい。

• D[S]=0でなければならず、またS以外のxはD[x]=0になってはならない。
• 最大の木の深さをAとする場合、D[x]=0～D[x]=Aとなる頂点が最低１個以上なければならない。

自分はAを小さい順に探索し、修正数の最小値を求めた。
まずD[S]!=0の場合はD[S]=0にするのは確定である。
またS以外でD[x]==0の場合、その頂点xは誤っているのでどこかに動かさなければならない。

D[0]～D[A]の間にいくつかD[y]=0となるyがあるとする。ここは何とかして埋めなければならない。
この場合、以下の頂点はいずれにせよ動かさなければならないので、まずいずれかで埋める。

• 上記D[x]=0である頂点x
• D[z]＞Aとなる頂点z

これでも埋めなければならないyが残っている場合、同じ深さに複数の頂点があったら1つ残してそれらを動かし埋めればよい。

上記頂点x,yの数および最悪移動可能な余剰頂点の数を順次Aを動かしながら更新し、動かす頂点数の最小値を求めればよい。

int N,S;
int num[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int ret=0,hoge=0;
	FOR(i,N) {
		cin>>x;
		if(i==S-1) {
			if(x) {
				x=0;
				ret++;
			}
			num[x]++;
		}
		else if(x==0) {
			hoge++;
		}
		else {
			num[x]++;
		}
	}
	
	int mi=(1<<19);
	int yet=N-hoge;
	int left=0;
	int sho=0;
	for(i=0;i<1<<19;i++) {
		if(num[i]==0) {
			sho++;
		}
		else {
			yet -= num[i];
			left += num[i]-1;
		}
		//_P("%d  le:%d yet:%d hoge:%d sho:%d  %d\n",i,left,yet,hoge,sho,(left+yet+hoge>=sho));
		if(left+yet+hoge>=sho) mi=min(mi,max(yet+hoge,sho));
	}
	
	
	cout<<mi+ret<<endl;
	
	
}

まとめ

1000ptということでいつものCより簡単。