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

Source

ニコニコミュニティ
問題文

問題概要

左端から，区画 $1,2,\ldots,$ と半無限に続く区画がある．
左端から二次元ピラミッドを作りたい．
これは，左端から，レンガの数が，$1,2,\ldots,k-1,k,k-1,\ldots,2,1,0,0,\ldots$ と $1$ から始まり，最初は $1$ ずつ増え，途中から $1$ ずつ減り，$0$ になったらずっと $0$ というものである．
最初，左から $N$ 個の区画にはレンガが幾つかあり，左から $i$ 番目の区画にはレンガが $A_i$ 個ある．
レンガは移動させることや，捨てることができるが，どちらも $1$ 個あたりコストが $1$ だけ必要になる．
また，新しくレンガを追加することはできない．
どのようなサイズのピラミッドを作っても良いので，ピラミッドを作るための最小コストを求める問題．

解法

動かさなければいけない（捨てるのも含む）レンガの数がコストであるから，使いまわせるレンガの数を最大化すれば良い．
大きいサイズのピラミッドは小さいピラミッドを包含しているから，レンガの数が足りるなら，大きいサイズのピラミッドを作った方が，使いまわせるレンガの数を考えると，良いことは自明．
よって，作れる最も大きいサイズのピラミッドを求め，各場所について，何個のレンガを使いまわせるかを求めれば良い．
時間計算量は $O(N + \sqrt{A_1+A_2+\ldots+A_N})$．
また，制約は大きくないので，全てのサイズのピラミッドに対して，使いまわせるレンガの数を求めてしまっても良い（以下のコードはこれ）．
この場合は，時間計算量は $O(N \sqrt{A_1+A_2+\ldots+A_N})$．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N, A[1000], B[1000], T[1000];

int main(){
  int i, j, k;
  int tot;
  int res = 1000000000, tmp;

  reader(&N);
  rep(i,N) reader(A+i);

  REP(k,1,333){
    rep(i,1000) B[i] = 0;
    rep(i,N) B[i] = A[i];
    rep(i,k) T[i] = i+1;
    REP(i,1,k) T[k+i-1] = T[k+i-2] - 1;

    tot = 0;
    rep(i,1000) tot += B[i];
    rep(i,1000) tot -= T[i];
    if(tot < 0) break;

    tmp = 0;
    rep(i,1000) tmp += max(0, B[i]-T[i]);
    res = min(res, tmp);
  }

  writerLn(res);

  return 0;
}

Current time: 2024年04月26日02時04分41秒
Last modified: 2014年12月23日23時54分59秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：