AtCoder ABC #290 (Toyota Programming Contest 2023 Spring Qual B) : G - Edge Elimination

これはどうにか。
https://atcoder.jp/contests/abc290/tasks/abc290_g

問題

深さDの完全K分木がある。
いくつか辺を切って、X要素の連結成分を作るには、最小何辺切ればよいか。

解法

葉の要素は必ず1個以上使った方がよい。
そうでない場合、残すX要素を葉に向けて深さ1個分スライドさせた方が、切る辺の数が減るためである。

その際、残す連結成分のうち一番浅い頂点の深さを総当たりしよう。
極力、各深いところから残す成分を詰めていくようにし、X要素残す際不要なSubTreeを切り離していくことを考えていく。

int T;
ll D,K;
ll X;
ll P[62],S[62];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>D>>K>>X;
		P[0]=S[0]=1;
		FOR(i,D) {
			P[i+1]=P[i]*K;
			S[i+1]=1+S[i]*K;
		}
		
		ll mi=1LL<<60;
		
		for(i=0;i<=D;i++) {
			if(S[i]>=X) {
				ll ret=0;
				if(i!=D) ret++;
				ll V=X;
				for(x=i;x>0&&V;x--) {
					V--;
					ll rem=S[x-1]*K-V;
					ret+=rem/S[x-1];
					V%=S[x-1];
				}
				mi=min(mi,ret);
			}
		}
		cout<<mi<<endl;
		
	}
}

まとめ

ちょっと手間取ったけどまぁまぁの考察時間で解けてよかったね。