kmjp's blog

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

AtCoder ARC #125 : F - Tree Degree Subset Sum

こういう考察苦手だな…。
https://atcoder.jp/contests/arc125/tasks/arc125_f

問題

N頂点の木を成すグラフが与えられる。
この時、任意の頂点x個を選んだ時に、その点の次数の総和をyとしたとき、(x,y)として取れる値は何通りか。

解法

各点vの次数から1引いた値をd[v]とする。
vをx個選んだ時、sum(d[v])=yとなるyの数を数え上げたい。

証明はEditorialを参照頂くとして、yを固定すると実は対応するxは連続する単一の区間となる。
そこで、y、すなわちd[v]の総和に対し、対応するxの最小値と最大値をDPで処理して行こう。
d[v]が一致する値を一括して扱うと、この問題はO(N√N)で解ける。

int N;
int C[202020];
int ma[202020];
int mi[202020];
deque<pair<int,int>> Dmi[202020],Dma[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		C[x-1]++;
		C[y-1]++;
	}
	map<int,int> M;
	FOR(i,N) M[C[i]-1]++;
	
	FOR(i,N+2) mi[i]=1<<30, ma[i]=-1<<30;
	mi[0]=0;
	ma[0]=M[0];
	
	int sum=0;
	FORR2(a,b,M) if(a) {
		sum+=a*b;
		FOR(i,sum+1) {
			x=i%a;
			int pmi=mi[i];
			int pma=ma[i];
			
			if(Dmi[x].size()&&(i-Dmi[x].front().first)/a>b) Dmi[x].pop_front();
			if(Dma[x].size()&&(i-Dma[x].front().first)/a>b) Dma[x].pop_front();
			if(Dmi[x].size()) mi[i]=min(mi[i],Dmi[x].front().second+(i-Dmi[x].front().first)/a);
			if(Dma[x].size()) ma[i]=max(ma[i],Dma[x].front().second+(i-Dma[x].front().first)/a);
			
			while(Dmi[x].size()&&Dmi[x].back().second+(i-Dmi[x].back().first)/a>=pmi) Dmi[x].pop_back();
			while(Dma[x].size()&&Dma[x].back().second+(i-Dma[x].back().first)/a<=pma) Dma[x].pop_back();
			Dmi[x].push_back({i,pmi});
			Dma[x].push_back({i,pma});
			
		}
		FOR(i,a) Dmi[i].clear(),Dma[i].clear();
	}
	ll ret=0;
	FOR(i,N) if(ma[i]>=mi[i]) {
		ret+=ma[i]-mi[i]+1;
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

xに対して、yは不連続な値を取れるな…と思って手が止まってしまった。
色々実験すれば気づけたのかな。