メモ

yukicoderでゆるふわgolf

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

問題はこちら
No.555 世界史のレポート - yukicoder

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 No.566 だいたい完全二分木

問題はこちら
No.566 だいたい完全二分木 - yukicoder

○激ヤバ解法
シャッフルすれば高確率で通る

○まじめな解法
普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする
・方針1
完全二分木を作る過程で、2と3を入れ替える。
そうすると
 2
/\
1 3
の部分が
 3

1

 2
または
  3
 /
 2

1
となり高さが1増える。ほかの部分には影響がないのでこれにより全体の高さがKになる
・方針2
完全二分木を作る過程で、最大値2^K-1の代わりに0を入れる
そうすると
 2
/\
1 3
の部分が
  2
 /\
 1 3

0
となり高さが1増える。
登場する数が0~2^K-2になっているので、全体に1を加えることで1~2^K-1にする

○実装について
・DFSっぽいの
自分が最初に思いついたのはこれだった。
方針1を再帰で実装する

f(n,c){
	printf("%d ",n!=2&&n!=3?n:5-n);
	if(c>=0){
		f(n-(1<<c),c-1);//左側
		f(n+(1<<c),c-1);//右側
	}
}

main(){
	int k;
	scanf("%d",&k);
	f(1<<(k-1),k-2);
}

・BFSっぽいの
完全二分木を、根に近いほうから順に配っていく
例えばK=4なら、頂点が8、その次が4,12、次が2,6,10,14、…となる
初項が2^i、公差が2^(i+1)の等差数列をなしている
方針2を実装する

main(){
	int k;
	scanf("%d",&k);
	for(int i=1<<(k-1);i;i/=2)for(int j=i;j<(1<<k);j+=i*2)printf("%d ",j);
}


・方針3
次の比較関数でソートする

c(int*a,int*b){
	int ta=*a,tb=*b;
	while(ta%2==0)ta/=2;
	while(tb%2==0)tb/=2;
	return ta-tb;
}

a[5000];
main(){
	int k;
	scanf("%d",&k);
	for(int i=0;i<(1<<k)-1;i++)a[i]=i+1;
	qsort(a,(1<<k)-1,4,c);
	for(int i=0;i<(1<<k)-1;i++)printf("%d ",a[i]);
}

この解法はtailsさんの提出C言語に書きなおしたものである
(なおこの提出はシャッフル解でないもののなかで最短)
少しわかりにくいが、このソートにより高さ2K-1の木が得られることがKに関する帰納法で示せる。

このソートにより出力は、1,2,4,…、3,6,12,…、5,10,20,…、…となる。
初項2*i-1、公比2の等比数列からなる群数列なので、単なる二重ループで書ける。

main(){
	int k;
	scanf("%d",&k);
	for(int i=1;i<(1<<k);i+=2)for(int j=i;j<(1<<k);j*=2)printf("%d ",j);
}

これをちゃちゃっと縮める

j,k;main(i){for(k=1<<atoi(gets(&k));i<k;i+=2)for(j=i;j<k;j*=2)printf("%d ",j);}

79B
まだ縮む余地はありそう

yukicoder No.567 コンプリート

問題はこちら
No.567 コンプリート - yukicoder

包除原理やるだけ(説明は後述)

main(n){
	scanf("%d",&n);
	printf("%.9f",
		1
		- 6*pow(5/6.,n)
		+15*pow(4/6.,n)
		-20*pow(3/6.,n)
		+15*pow(2/6.,n)
		- 6*pow(1/6.,n)
	);
}

事象A1,…,A6を、
A1:1が出ない

A6:6が出ない
とおく。このとき、6種類が揃う確率は、余事象を考えて 1-P(A1∪A2∪A3∪A4∪A5∪A6)となる。
ところで明らかに
P(Ai)=(5/6)^n
P(Ai∩Aj)=(4/6)^n (i≠j)
……
であるから、包除原理より冒頭のプログラムの式が得られる


単に式を書き換えるよりも、for文で1つにまとめてしまった方が短くなった。
powの前についている係数は二項係数なので順次計算できることに注意して次のように書ける

double A;
n,i;
main(s){
	for(scanf("%d",&n);++i<7;A+=pow(i/6.,n)*s)s=s*(i-7)/i;
	printf("%.9f",A);
}

93B

yukicoder No.564 背の順

問題はこちら
No.564 背の順 - yukicoder

最初は1位で、高い人が現れるたびに順位は1つ下がる

h,n,t,S;
main(){
	scanf("%d%d",&h,&n);
	S=1;
	for(int i=1;i<n;i++){
		scanf("%d",&t);
		if(t>h)S++;
	}
	printf("%d",S);
	if(S%10==1)puts("st");
	else if(S%10==2)puts("nd");
	else if(S%10==3)puts("rd");
	else puts("th");
}

最初の順位を0位にしておけば最初の処理がまとめられる
また、文字の出力部分は適当なフォーマット指定により短くできる(はじめて知った)

h,t,s;
main(i){
	for(;~scanf("%d",&t);){
		if(!h)h=t;
		if(i--)s+=t>=h;//nだけ読み飛ばし
	}
	printf("%d%.2s",s,"thstndrd"+(s%10<4)*s%10*2);
}
h,t,s;
main(i){
	for(;~scanf("%d",&t);s+=i--&&t/h)h=h?:t;
	printf("%d%.2s",s,"thstndrd"+(s%10<4)*s%10*2);
}

101B

yukicoder No.549 素材合成システム

問題はこちら
No.549 素材合成システム - yukicoder

合成素材の側の経験値の最終的な寄与度は高々floor(a/2)
実際に、一番経験値が高い奴をベースにし、残りを素材として順次合成していくことで最大になる。

c(int*a,int*b){return*b-*a;}

a[100010],n,S;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	qsort(a,n,4,c);
	S=a[0];
	for(int i=1;i<n;i++)S+=a[i]/2;
	printf("%d",S);
}

ソートしなくても、最大値を記憶しておくことで先頭から順に読み込むことができる

#define max(p,q)(p>q?p:q)
t,n,M,S;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		M=max(M,t);
		S+=t/2;
	}
	printf("%d",S-M/2+M);
}

式を変形して最後の出力をS-~M/2にできる
ぎゅっとする

s,x,m;
main(i){
	for(;~scanf("%d",&x);)--i?m<x?m=x:0,s+=x/2:0;
	printf("%d",s-~m/2);
}

80B