kmjp's blog

競技プログラミング参加記です

AtCoder AGC #027 : B - Garbage Collector

グダグダすぎる…。
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;
}

まとめ

まんまと典型嘘解法にはまってしまった…。