TopCoder SRM 682 Div2 Hard FriendlyRobot

Div1EasyもMediumも1ミスしたので、結果的に出なくてよかったかも？
https://community.topcoder.com/stat?c=problem_statement&pm=14165

問題

２次元座標上(0,0)にいるロボットが、命令列Sに従い動く。
命令列は、上下左右に1動く命令で構成されている。

この命令列を最大C文字まで書き換え可能な時、(0,0)を通る回数の最大値を求めよ。

解法

x文字命令処理後に原点にいるとき、その後y文字目まで命令を処理した時点でまた原点に戻るのに必要な最小書き換え回数を求めよう。
f(x,y)をそのような回数とする。
ただしy-xが奇数の場合は絶対に戻れないのでこの値は無限大(実質Cより大きければよい)となる。

f(x,y)は以下のように求められる。
S[(x+1)..y]における上下左右の移動回数を考える。
上移動と下移動の差がA回、左移動と右移動の差がB回とする。
これらが両方0となるように命令を書き換えたい。

上移動を下移動に置き換えればAを2減らせる。
よってまずはA/2回上移動を下移動にし(Aは負の場合、|A/2|回下移動を上移動にする。)、同様にB/2回左移動を右移動にしよう。
A,Bがともに奇数の場合、まだ上下左右に1ずつずれた位置にいるので、上下移動を一つ左右移動にすれば原点に戻せる。
まとめると、f(x,y) = |A/2| + |B/2| + |A%2|とおける。

あとは、単純なDPで
dp(y,n) := y文字目までにn回原点に戻るのに必要な最小書き換え数
をdp(y,n) = min(dp(x,n-1)+f(x,y))で更新していき、dp(|S|,n)がC以下となる最大のnを求めればよい。

int sum[4][303];
int mc[303][303];
int dp[303][303];


class FriendlyRobot {
	public:
	int getcost(int U,int D,int L,int R) {
		if((U+D+L+R)%2) return 1000;
		U=abs(U-D);
		L=abs(L-R);
		return U/2+L/2+U%2;
	}
	int findMaximumReturns(string instructions, int changesAllowed) {
		int i,j,k,x;
		int N=instructions.size();
		int ma=0;
		
		ZERO(sum);
		FOR(i,N) {
			sum[0][i+1]=sum[0][i]+(instructions[i]=='U');
			sum[1][i+1]=sum[1][i]+(instructions[i]=='D');
			sum[2][i+1]=sum[2][i]+(instructions[i]=='L');
			sum[3][i+1]=sum[3][i]+(instructions[i]=='R');
		}
		
		FOR(j,N+1) FOR(i,j) mc[i][j]=getcost(sum[0][j]-sum[0][i],sum[1][j]-sum[1][i],sum[2][j]-sum[2][i],sum[3][j]-sum[3][i]);
		
		FOR(i,N+1) FOR(j,N+1) dp[i][j]=1000;
		dp[0][0]=0;
		for(i=0;i<N;i++) {
			for(j=i+1;j<=N;j++) if(mc[i][j]<1000) {
				FOR(x,N) {
					dp[j][x+1]=min(dp[j][x+1],dp[i][x]+mc[i][j]);
					if(dp[j][x+1]<=changesAllowed) ma=max(ma,x+1);
				}
			}
		}
		
		
		
		return ma;
	}
}

まとめ

f(x,y)がO(1)で求められることに気づくと簡単。