TopCoder SRM 569 Div1 Medium TheJediTest

さてDiv2 Easyのアレンジ問題、Div1 Medium。
http://community.topcoder.com/stat?c=problem_statement&pm=12265

問題

Div2 Easy同様、要素が20個までの整数値配列と数値Kが与えられる。
Kをいくつか使って、各要素の数を上回る最小のKを答える問題。
ただしこの問題では、各要素は一部一つ隣の要素に移動させることができる。

解法

配列の部分配列をgreedyに処理していくことを考える。
Kの数を少なくするには、各要素ができるだけKの倍数にそろうように要素を移動させればよい。
よって部分配列について、そのように右に数値を寄せたり不足分だけ右から左に寄せたりすればよい。

あとは、この部分配列の取り方を列挙して最小値を求めず。
部分配列の数は20個の数値のうち境目をどこに入れるかカウントするので一見2^19通りあるが、実際にはDPを使えば余分な再計算を防いでO(N^2)回の処理で処理できる。

上記greedyな処理を合わせるとO(N^3)なんだけど、なんでこの問題N<=20なんだろ。
いつも通りN<=50でも計算間に合いそうなのに。
配列の各整数値は100,000,000までなので、N<=50だとintから溢れて具合悪いのはわかるけど、それは整数値の上限を10,000,000にすればいいだけに思えるしなぁ。

class TheJediTest {
	public:
	int N,K;
	ll memo1[25][25];
	ll memo2[25];
	
	ll gr(vector <int> S, int s, int t) {
		int i;
		if(s>=t) return 0;
		if(memo1[s][t]>=0) return memo1[s][t];
		ll to = 0;
		
		if(t-s<=3) {
			for(i=s;i<t;i++) to+=S[i];
			return memo1[s][t]=(to+(K-1))/K;
		}
		
		ll le = S[s];
		for(i=s+1;i<t-1;i++) {
			if(le==0) le=S[i];
			else {
				int mo = (K-(le%K))%K;
				to += (le+(K-1))/K;
				if(S[i]<mo) {
					if(S[i+1]<mo-S[i]) S[i+1]=0;
					else S[i+1] -= mo-S[i];
					le=0;
				}
				else {
					le = (le+S[i])-((le+(K-1))/K)*K;
					to += le/K;
					le %= K;
				}
			}
		}
		return memo1[s][t]=to + (le+S[t-1]+(K-1))/K;
	}
	
	ll range(vector<int> S, int s) {
		int i;
		if(s>=N) return 0;
		if(memo2[s]>=0) return memo2[s];
		memo2[s]=3e9;
		
		for(i=s+1;i<=N;i++) memo2[s] = min(memo2[s], gr(S,s,i)+range(S,i));
		return memo2[s];
	}
	
	int minimumSupervisors(vector<int> S, int K) {
		int loop,i,x,y;
		this->K=K;
		N=S.size();
		if(N<=3) {
			x=0;
			FOR(i,S.size()) x+=S[i];
			return (x+(K-1))/K;
		}
		
		FOR(x,25) FOR(y,25) memo1[x][y]=-1;
		FOR(x,25) memo2[x]=-1;
		return (int)range(S,0);
	}
};

*まとめ

最初部分配列に区切るのではなく、全体をgreedyに処理するだけでsubmitしてミスを繰り返した。
テストケースが緩かったのも一因だな。