近いところまで行ったけど一歩及ばず。
http://agc004.contest.atcoder.jp/tasks/agc004_e
問題
H*Wのマス目があり、初期状態で1か所に出口がある。
また、それ以外の何マスかにロボがいる。
ロボ全体に指令を出すと、全ロボを同時に同じ方向の隣接マスに移動させることができる。
ただし、元のマス目から一旦はみ出たロボは撤去され戻ってこない。
また、出口マスに到達したロボは救出され、回収される。
最適な順でロボを動かしたとき、最大何体のロボが回収できるか。
解法
ロボを動かすと面倒なので、出口とマスの境界を動かすことを考える。
何度か出口を動かす過程で、最大で出口を初期状態より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は思いついたが、うまく状態遷移させられなかった。