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

DP解法との賢い数学解法がある

・DP解
N文字以上を作る最小コスト=min{ちょうどK文字を作る最小コスト|K≧N}
K文字を作る際には、その過程で必ずK/2文字以上の状態を経由するので、Kの上限は2Nとしてよい。
・もらうDP
ちょうどi文字を作るための最小コストをd[i]とする。d[1]=1。
ちょうどi文字を作るためには、最後にコピーを行う際の文字数kはiの約数でなければならない。
このときペーストはi/k-1回行われるので、コストはd[k]+C+(i/k-1)*Vとなる
約数列挙にO(√i)かかるので全体で、Σ√i=O(N√N)
・配るDP
上の解法を配るDPに書き換えるだけ
j≧2に対して、d[i*j]=min(d[i*j],d[i]+C+(j-1)*V)とすればよい
ΣN/i=O(NlogN)

n,c,v;
dp[100010];
ans=1e9;
main(){
	scanf("%d%d%d",&n,&c,&v);
	for(int i=0;i<2*n+5;i++)dp[i]=1e9;
	dp[1]=0;
	for(int i=1;i<n;i++)for(int j=2;i*j<2*n;j++)dp[i*j]=fmin(dp[i*j],dp[i]+c+(j-1)*v);
	for(int i=n;i<2*n;i++)ans=fmin(ans,dp[i]);
	printf("%d",ans);
}

・O(logN)の賢い解法
操作は「コピー、(ペースト)×a1、全体をコピー、(ペースト)×a2、全体をコピー、……」となる。
このときペーストの回数を順にaiとすれば、最終的な文字数は $\prod_{i=1}^{k}(1+a_i)$ となる。
各kに対して最小コストを考える。
$\prod_{i=1}^{k}(1+a_i)\geqq N$ の条件下で
$C*k+V*\sum_{i=1}^{k}a_i$ を最小化する問題を考える。
kは固定しているので、これは結局
$\sum_{i=1}^{k}(1+a_i)$ を最小化することと同じ。
以下1+aiをaiと改めて書く。
さて、相加相乗平均の関係から、Σaiの最小値はaiたちが等しい値をとるとき（∀i,j.|ai-aj|≦1)に達成される。
よって、aiたちはfloor(N^(1/k))及びそれ+1の値を、Πai≧Nとなるように取ればよいことがわかり、最小値はO(1)で求められる。
またai≧2よりΠai≧2^kなのでkはlog2(N)+1まで調べればよく、全体ではO(logN)で求める事ができる。

n,c,v;
a,b,t;
ans=1e9;
main(){
	scanf("%d%d%d",&n,&c,&v);
	for(int k=1;k<log2(n)+1;k++){
		a=pow(n,1.0/k);//aiたちの小さい方の値
		b=(log(n)-k*log(a))/(log(a+1)-log(a))+1-1e-9;//大きい方の個数
		//+1-1e-9は切り上げのため
		t=(c-v)*k+v*(a*k+b);
		ans=fmin(ans,t);
	}
	printf("%d",ans);
}

・発想の転換
実はdfsでも解ける
f(現在の文字数,クリップボードの文字数)=必要な残りコスト
という関数を考えると

n,c,v;
f(a,b){
	if(a>=n)return 0;
	return fmin(f(a+b,b)+v,f(a+a,a)+c+v);
}
main(){
	scanf("%d%d%d",&n,&c,&v);
	printf("%d",f(1,1)+c);
}

と書くことができる
最大ケースのN=50000でもfは168685291回≒1.6×10^8回しか呼び出されないらしく間に合う。
これをギュッとする

n,c,v;
f(a,b){
	return a<n?fmin(f(a+b,b),f(a+a,a)+c)+v:c;
}
main(){
	scanf("%d%d%d",&n,&c,&v);
	printf("%d",f(1,1));
}

return文を省略

x,n,c,v;
f(a,b){
	x=a<n?fmin(f(a+b,b),f(a+a,a)+c)+v:c;
}
main(){
	scanf("%d%d%d",&n,&c,&v);
	printf("%d",f(1,1));
}

105B

メモ

yukicoderでゆるふわgolf

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