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