TopCoder SRM 678 Div2 Hard RevengeOfTheSith

今回のタイトルと登場人物はスターウォーズネタ？
https://community.topcoder.com/stat?c=problem_statement&pm=13191

問題

N段の段差を下りたい。
初期状態で各段の相対的な高さの差S[i]が与えられる。
段差を1段ずつ降りる際、D以上の高さHを下りるには(H-D)^2のコストが必要となる。

ここで、地面の位置(0段目相当)と最上位(N段目相当)の間にある1～(N-1)段目の高さを、以下の条件の元ずらすことができる。

• 高さは高くしても低くしても良い。
• 高さをずらした後も、各段の高さは単調増加でなければならない。
• 高さをずらした場合、その高さは整数値であること。

N段の段差に対し、M個の段の高さを変えられるとき、最小コストを求めよ。

解法

一見、以下のDPで解けそうである。
dp[段数][この段数の高さ][残り変更回数] := その状態を満たす最小コスト
ただ、このDPはO(N*(N*max(S))^2*M)=O(N^3*max(S)^2*M)かかりとても間に合わない。

そこでもう少し状態を減らしたDPを考えよう。
x段目とy段目を固定し、(x+1)～(y-1)段をずらせるとする。
コストの計算式を見る限り、大きな段差を作ると損なので(x+1)～(y-1)段は高さの差が均等になるようにずらすのが最適である。

このことから、DPに落とすことができる。
以下のような状態を考えよう。
dp[処理中の段数][ずらした段数] := 現在処理中の段差を固定したとき、0段目からその段までの最小コスト

x段からy段までを固定することを考えると、
dp[y][t] = max(dp[x][t+(y-x+1)] + (x～y段の間を均等配置したときのコスト))
とかける。
上記DPならO(N^2*M)で間に合う。

int dp[52][52];
int H[52];

class RevengeOfTheSith {
	public:
	
	int cost(int TH,int SP,int D) {
		int l=max(0,TH/SP-D);
		int r=max(0,TH/SP+1-D);
		int r2=TH%SP;
		int l2=SP-r2;
		
		return l*l*l2+r*r*r2;
		
	}
	
	int move(vector <int> steps, int T, int D) {
		int N=steps.size();
		int L,R,t;
		
		memset(dp,0x3e,sizeof(dp));
		FOR(t,N) H[t+1]=H[t]+steps[t];
		
		dp[0][T]=0;
		for(R=1;R<=N;R++) {
			for(t=0;t<=T;t++) {
				for(L=0;L<R;L++) {
					int mov=R-L-1;
					if(mov<=t) dp[R][t-mov]=min(dp[R][t-mov],dp[L][t]+cost(H[R]-H[L],R-L,D));
				}
			}
		}
		
		int mi=1<<30;
		FOR(t,T+1) mi=min(mi,dp[N][t]);
		return mi;
	}
}

まとめ

N,Mが微妙に小さく、TLE解をついとりたくなる制限だね。