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

メモ

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

yukicoder No.71 そろばん

問題はこちら
No.71 そろばん - yukicoder

N個のうちk個を上の珠として扱うと
上の珠の状態はk+1通り
下の珠の状態は(N-k)+1通りなので
扱える最大の値は(k+1)(N-k+1)-1となる
ところでこれは、和が一定の2数の積を最大化する問題なので、2数が近くなるようにすれば良い
(∵ab=((a+b)^2-(a-b)^2)/4)
よってk=floor(N/2)としたときの値が求める答え

int main(){
	int n;
	scanf("%d",&n);
	printf("%ld",1L*(n/2+1)*(n-n/2+1)-1);
	return 0;
}

この結果は
Nが偶数の時(N/2+1)(N/2+1)-1=N*N/4+N
Nが奇数の時((N-1)/2+1)((N+1)/2+1)-1=(N*N-1)/4+N
となるので、結局 floor(N*N/4)+N とまとめられる

n;main(){n=scanf("%d",&n)>printf("%ld",1L*n*n/4+n);}

52B