yukicoder : No.555 世界史のレポート

これ本番ちょっと手こずったんだよな。
https://yukicoder.me/problems/no/555

問題

初期状態でテキストボックスにはアルファベットが1文字書かれている。
このテキストボックスに対し、文字列をコピーするか、コピーした文字列を末尾に追加する処理を行える。
ただしそれぞれC,Vのコストがかかる。

アルファベットをN文字以上にする最小コストを求めよ。

解法

想定誤解法としては、コピーした文字列数と、テキストボックスの文字列数を状態とするDPがある。
これだと状態がO(N^2)となりMLEやTLEする。

発想を変えてみる。
一旦コピーしたら、次にコピーするまでは同じ文字数を追加することになる。

よって、a文字を構成する最小コストをf(a)とする。
aを(b-1)回ペーストすることを考えると、f(a*b)=f(a)+C+(b-1)*Vがf(a*b)の候補となる。

よってf(a)からf(a*b)を順次更新するようにすれば、計算量を落とすことができる。

int N,C,V;

ll A[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C>>V;
	for(i=1;i<=100000;i++) A[i]=1LL<<60;
	
	ll mi=1LL<<60;
	A[1]=0;
	for(i=1;i<=2*N;i++) {
		if(i>=N) mi=min(mi,A[i]);
		for(j=2*i;j<=2*N;j+=i) {
			A[j]=min(A[j],A[i]+C+1LL*(j/i-1)*V);	
		}
	}
	cout<<mi<<endl;
	
}

まとめ

シンプルな設定だけどちょっと工夫が必要なのがいいね。