yukicoder : No.1862 Copy and Paste

これはなんとか解けた。
https://yukicoder.me/problems/no/1862

問題

今文字列S="p"、T=""とする。
以下の処理を任意順で行うとき、|S|がN以上となるのに必要な最小処理回数はいくつか

• T=S
• S+=T

解法

前者を行った後、後者をn回実行することは、|S|をn+1倍することに相当する。
前者を行う回数kを固定すると、長さkの非負数列Aに対し、(A[0]+1)*(A[1]+1)*...*(A[k-1]+1)が最大となるのが|S|を最大化するのに有効である。

そこで、以下kを総当たりしつつ、Aを構築してみよう。
Aの総和が決まっているので、上記積を最大化するにはAを均等に増やしていくとよい。
N=1だけコーナーケースなので注意。

ll A,B;
ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>N;
	ll ret=A+(N-1)*B;
	if(N==1) ret=0;
	
	for(i=2;i<=30;i++) {
		vector<ll> V(i,1);
		ll a=1;
		ll cur=i*A;
		x=0;
		while(a<N) {
			cur+=B;
			a/=V[x];
			a*=++V[x];
			x++;
			x%=i;
		}
		ret=min(ret,cur);
	}
	
	cout<<ret<<endl;
	
}

まとめ

N=1でまんまと失敗しました。