TopCoder SRM 632 Div1 Easy PotentialArithmeticSequence

問題文を読み間違えたりしてEasyが激遅になるなどひどい結果に。
http://community.topcoder.com/stat?c=problem_statement&pm=13389

問題

N要素の1以上の整数列A[i]について、各数値を2進数表記したとき末尾につく0の数を並べたものをd[i]とする。
ここで、A[i]はわからないがd[i]が与えられているとする。
d[i]のうち連続した部分列d[x]～d[y]のうち、対応するA[x]～A[y]が1ずつ増える数列になる可能性があるものの数を答えよ。

解法

A[i]はN要素なので、N<=50だと部分列d[x]～d[y]のうち7以上となるものは1個以下である。
よって、7より大きなd[i]は7であると仮定する。

A[x]を1～128であると仮置きして、A[x]～A[y]に対しd[x]～d[y]が整合するものの数をカウントすればよい。

ll dp[401];
int mb[401];
class PotentialArithmeticSequence {
	public:
	int N;
	
	int ok(vector<int> d,int x,int y) {
		int i,j;
		for(i=1;i<=128;i++) {
			int ng=0;
			FOR(j,y-x) {
				if(mb[i+j]!=d[x+j]) ng++;
			}
			if(ng==0) return 1;
		}
		return 0;
	}
	
	int numberOfSubsequences(vector <int> d) {
		int i,j,k,x,y;
		N=d.size();
		FOR(i,N) if(d[i]>7) d[i]=7;
		int ret=0;
		for(i=1;i<=400;i++) {
			mb[i]=0;
			while((i&(1<<mb[i]))==0) mb[i]++;
		}
		FOR(x,N) for(y=x+1;y<=N;y++) {
			if(ok(d,x,y)) ret++;
		}
		
		return (int)ret;
	}
}

まとめ

本番は不連続でも良いと勘違いして手間取った…。