グダグダすぎる…。
https://beta.atcoder.jp/contests/agc027/tasks/agc027_b
問題
1次元の数直線上にN個のゴミがあり、その座標はX[i]である。
ゴミ箱が座標0にあり、そこから初めて、数直線上を移動しながらゴミを拾い集めることを考える。
- ゴミを拾うコストはY
- 手持ちのゴミをまとめて捨てるコストもY
- ゴミをk個持つときに1移動するコストは(k+1)^2
最適な手順で移動やゴミ拾いをしたとき、全てのゴミをゴミ箱に集めるコストの最小値を求めよ。
解法
1回でいくつかのゴミを拾う場合、一番遠いゴミのところまで手ぶらで移動して、戻りながら拾い集めるのが効率が良い。
その際、遠い順に座標をa,b,c,d....とすると、かかるコストはY+(Y+5a)+(Y+5b)+(Y+7c)+(Y+9d)+(Y+11e)+....と、後に拾うほど座標のコストへの影響が大きくなる。
よって、仮にm往復してゴミを拾い集める場合、最も遠いm個を最初に拾うゴミとし、次のm個を2番目に拾うゴミ…とするのがよい。
そこで往復数mを総当たりしよう。
ゴミの座標の累積和を事前に計算しておけば、総当たり時の計算量はO(N*(1/1+1/2+1/3+...))なので間に合う。
ll N; ll X[202020],Y; __int128 S[202020]; ll dp[202020]; int ok[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Y; FOR(i,N) cin>>X[i+1], S[i+1]=S[i]+X[i+1]; __int128 ret=1LL<<60; for(int i=1;i<=N;i++) { __int128 tot=i*Y; int left=N; int step=1; while(left>0) { if(step==1) { tot+=5*(S[left]-S[max(left-i,0)]); } else { tot+=(2*step+1)*(S[left]-S[max(left-i,0)]); } left-=i; step++; } ret=min(ret,tot); } cout<<((ll)ret+N*Y)<<endl; }
まとめ
まんまと典型嘘解法にはまってしまった…。