読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.73 helloworld

問題はこちら
No.73 helloworld - yukicoder

helloworldに登場しない文字はどうでもいいので除いておく
文字の並びはそれぞれ固めておくのが良い
h..e..l..o..w..o..r..l..d..
と並べた時、helloworldの作り方を考える
l,o以外は、その文字数だけ選び方がある
oは2箇所にそれぞれx,y個分配すればx*y通りの選び方があるので、
前述の「和が一定の積を最大化」にしたがって、半分ずつ分ければ良い
lは2箇所にそれぞれx,y個分配すればC(x,2)*y通りの選び方があるので、
合計でN個あったとすればx*(x-1)/2*(N-x)の最大化問題

int main(){
	int a[26],p,q,t;
	for(t=0;t<26;t++)scanf("%d",a+t);
	for(q=a[11];q--;){
		t=q*(q-1)/2*(a[11]-q);
		p=p<t?t:p;
	}
	printf("%ld",1L*a[14]*a[14]/4*a[7]*a[4]*a[22]*a[17]*a[3]*p);
	//大量に掛け算するのでintの範囲を超えることに注意
	return 0;
}

ところで先の3次関数は、微分して極大値を求めると、
実数の範囲では x=(√(N^2-N+1)+N+1)/3 となる
√(N^2-N+1)=√((N-1/2)^2+3/4)なのでx=(2N+1/2+α)/3である(N≧3でα<1/6)
整数の範囲での最大値はceil(2N/3)と推測できる
実際にN≦100の範囲ではそれで正しい

前の方の値は使わないので捨てて、配列サイズもごまかす

a[9],t;
main(p){
	for(;~scanf("%d",a-3+t++);p=a[8]);
	t=p-p/3;
	//ceil(2N/3)=N-floor(N/3)
	t=!printf("%ld",a[11]*a[11]/4L*t*(t-1)/2*(p-t)*a[4]*a[1]*a[19]*a[14]**a);
}

131B

17/01/12追記
自明な2B

a[9],t;
main(p){
	for(;~scanf("%d",a-3+t++);)p=a[8];
	t=p-p/3;
	t=!printf("%ld",a[11]*a[11]/4L*t*~-t/2*(p-t)*a[4]*a[1]*a[19]*a[14]**a);
}