問題はこちら
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); }