kmjp's blog

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

yukicoder : No.484 収穫

あと1分速く解きたかったね。
http://yukicoder.me/problems/no/484

問題

1~N番のN個の木が順に左右に並んでいる。

タヌキは時刻0で任意の位置にいることができる。
また、時間1をかけて隣の木に移動することができる。
i番の木には、時刻A[i]に実がなることがわかっている。

タヌキはすべての木を回り、すべての木の実を収穫したい。(収穫にかかる時間は無視できる)
最適な順で移動した際にかかる最短の時間を求めよ。

解法

遠くにある木の実を回収しようとする場合、その途中にある(すでに生っている)実は回収できる。
そこで、左右それぞれもっとも遠い場所で、残りどこまで収穫しなければならないかを考える。

f(L,R,side)を以下のように定義する。

  • f(L,R,left) := あと区間[L,R]の木の実を収穫しなければいけない状態で、ちょうどL番の実を収穫した状態になる最短時刻
  • f(L,R,right) := あと区間[L,R]の木の実を収穫しなければいけない状態で、ちょうどR番の実を収穫した状態になる最短時刻

それぞれ、f(1,N,left) = A[1]、f(1,N,right) = A[N]を初期値とし、f(L-1,R,left)およびf(L,R+1,right)からf(L,R,left)、f(L,R,right)を更新していこう。
最終的にmin_x(f(x,x,left))が解。(L=Rの場合残る実は1つなので第3引数はleftでもrightでも同じ)

int N;
ll A[2020];
ll memo[2020][2020][2];

ll hoge(int L,int R,int S) {
	if(memo[L][R][S]>=0) return memo[L][R][S];
	ll& ret=memo[L][R][S];
	ret=1LL<<60;
	
	if(L==0 && R==N-1) {
		if(S==0) ret=A[0];
		else ret=A[N-1];
	}
	else {
		if(S==0) {
			if(L) ret=min(ret,hoge(L-1,R,0)+1);
			if(R<N-1) ret=min(ret,hoge(L,R+1,1)+(R+1-L));
			ret=max(ret,A[L]);
		}
		else {
			if(L) ret=min(ret,hoge(L-1,R,0)+(R-(L-1)));
			if(R<N-1) ret=min(ret,hoge(L,R+1,1)+1);
			ret=max(ret,A[R]);
		}
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	MINUS(memo);
	
	ll mi=1LL<<50;
	FOR(i,N) mi=min(mi,hoge(i,i,0));
	cout<<mi<<endl;
	
}

まとめ

面白かったです。
なんか二分探索解を書いてる人が多かったね(最小値を求める問題なので気持ちはわかる)。