AtCoder AGC #004 : E - Salvage Robots

近いところまで行ったけど一歩及ばず。
http://agc004.contest.atcoder.jp/tasks/agc004_e

問題

H*Wのマス目があり、初期状態で１か所に出口がある。
また、それ以外の何マスかにロボがいる。

ロボ全体に指令を出すと、全ロボを同時に同じ方向の隣接マスに移動させることができる。
ただし、元のマス目から一旦はみ出たロボは撤去され戻ってこない。
また、出口マスに到達したロボは救出され、回収される。

最適な順でロボを動かしたとき、最大何体のロボが回収できるか。

解法

ロボを動かすと面倒なので、出口とマスの境界を動かすことを考える。
何度か出口を動かす過程で、最大で出口を初期状態よりL回分まで左に動かしたことがあったとする。
すると、元のロボのうち、右端L列にいたロボットは全てマス外に出てしまっているはずである。
また、初期状態より左側L列以内のロボについては、(左右方向について)新たにこれ以上のロボを落とすことはないため、全て回収済みとする。

そんな要領で、以下の状態を考える。
f(L,R,U,D) := 最大で左右上下にL列,R列,U行,D行まで出口を動かした場合に回収できるロボの最大数

DPまたはメモ化再帰の要領でL,R,U,Dを1ずつ広げ、マス目全体をカバーするL,R,U,Dに対応するfの値を求めよう。
f(L,R,U,D)が分かっているとき、出口の初期状態に対し左右上下L,R,U,Dマスの範囲の矩形内のロボはすべて回収または撤去済みである。
また、端から右左下上L,R,U,Dマスの範囲のロボも撤去済みである。
ここから、L,R,U,Dのいずれかを1動かすと、それぞれの領域が少し増減する。ここで新たに(移動後の)左右上下L,R,U,Dマスの範囲の矩形内に入るロボは回収可能なロボとなる。

int H,W;
string S[101];
int SY,SX;
int dp[101][101][101][101];
int sum[105][105];

int range(int L,int R,int T,int B) {
	if(L>R || T>B) return 0;
	if(L>=W || R<0 || T>=H || B<0) return 0;
	return sum[B+1][R+1]-sum[T][R+1]-sum[B+1][L]+sum[T][L];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			if(S[y][x]=='E') S[y][x]='.', SY=y,SX=x;
			if(S[y][x]=='o') sum[y+1][x+1]=1;
			sum[y+1][x+1] += sum[y][x+1] + sum[y+1][x] - sum[y][x];
		}
	}
	
	int L,R,U,D;
	for(L=0;SX-L>=0;L++) for(R=0;SX+R<W;R++) for(U=0;SY-U>=0;U++) for(D=0;SY+D<H;D++) {
		int& ret=dp[L][R][U][D];
		//_P("%d %d %d %d : %d\n",L,R,U,D,ret);
		int AL=max(SX-L,R);
		int AR=min(SX+R,W-1-L);
		int AT=max(SY-U,D);
		int AB=min(SY+D,H-1-U);
		
		dp[L][R+1][U][D]=max(dp[L][R+1][U][D], ret+((AR+1<W-L)?range(AR+1,AR+1,AT,AB):0));
		dp[L+1][R][U][D]=max(dp[L+1][R][U][D], ret+((R+1<=AL)?range(AL-1,AL-1,AT,AB):0));
		dp[L][R][U][D+1]=max(dp[L][R][U][D+1], ret+((AB+1<H-U)?range(AL,AR,AB+1,AB+1):0));
		dp[L][R][U+1][D]=max(dp[L][R][U+1][D], ret+((D+1<=AT)?range(AL,AR,AT-1,AT-1):0));
	}
	
	cout<<dp[SX][W-1-SX][SY][H-1-SY]<<endl;
	
}

まとめ

ロボじゃなく出口と周囲が動くDPは思いついたが、うまく状態遷移させられなかった。