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

メモ

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

yukicoder No.77 レンガのピラミッド

問題はこちら
No.77 レンガのピラミッド - yukicoder

{小さなピラミッド}⊂{大きなピラミッド}なので
{小さなピラミッドを作るため動かさないレンガ}⊂{大きなピラミッドを作るため動かさないレンガ}
となる。よって可能な限り大きなサイズのピラミッドを作れば良い
中心の高さがkであるようなピラミッドにはk^2個のレンガが必要なので
作ることができるピラミッドの最大サイズはレンガの総数の平方根となる
「動かすレンガの数」は面倒なので「動かさないレンガの数」を全体から引く

int main(){
	int a[210],n,m,s,i;
	//雑なプログラムだから配列が200までいる
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	//indexは1からがいいです…
	s=0;
	for(i=1;i<=n;i++)s+=a[i];
	m=sqrt(s);
	//sは最大10000なのでmは最大100
	for(i=1;i<=m;i++)s-=a[i]<i?a[i]:i;
	for(i=m+1;i<2*m;i++)s-=a[i]<2*m-i?a[i]:2*m-i;
	//動かさないレンガの数=min{その場所にあるレンガの数,その場所に作るピラミッドの高さ}
	printf("%d",s);
	return 0;
}

いつもどおり圧縮

a[210],i,j,s;
main(n){
	for(;~scanf("%d",a+i);s+=!!i*a[i++]);
	for(n=sqrt(s);++j<2*n;)s-=2*n-j<(i=a[j])?j<n?j:2*n-j:i<j?i:j;
	i=!printf("%d",s);
}

138B

16/07/29追記
fminを使って縮む

s-=2*n-j<(i=a[j])?j<n?j:2*n-j:i<j?i:j;
s-=fmin(fmin(a[j],j),2*n-j);

更にループ圧縮

for(;~scanf("%d",a+i);s+=!!i*a[i++]);for(n=sqrt(s);++j<2*n;)s-=fmin(fmin(a[j],j),2*n-j);
for(;~scanf("%d",a+i)?n=sqrt(s+=!!i*a[i++]),1:++j<2*n?s-=fmin(fmin(a[j],j),2*n-j):0;);

まとめると

a[210],i,j,s;
main(n){
	for(;~scanf("%d",a+i)?n=sqrt(s+=!!i*a[i++]),1:++j<2*n?s-=fmin(fmin(a[j],j),2*n-j):0;);
	i=!printf("%d",s);
}

126B