TopCoder SRM 632 Div2 Medium PotentialGeometricSequence

Div1のアレンジだね。こちらの方が簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13390

問題

Div1 Easy同様、1以上の整数列A[i]から生成した、2進数表記の末尾の0の数を並べた数列d[i]が与えられる。
d[i]の連続した部分列d[x]～d[y]のうち、対応するA[x]～A[y]が等比数列になっている可能性のあるものの数を答えよ。

解法

公比を素因数分解したとき、奇数の素因数はd[i]の値に影響がないから無視できる。
公比が2^kである場合、d[x+1]=d[x]+kでなければならない。

よって、A[x]～A[y]が等比数列であるとはd[x]～d[y]が等差数列であると同義と考えてよい。
後はそんな部分列の数をカウントするだけ。

class PotentialGeometricSequence {
	public:
	int numberOfSubsequences(vector <int> d) {
		int N,ret=0,x,y;
		N=d.size();
		FOR(x,N) for(y=x+1;y<=N;y++) {
			if(y-x<=2) ret++;
			else {
				int dd=d[x+1]-d[x];
				int i,ok=1;
				FOR(i,y-x) if(d[x+i]!=d[x]+dd*i) ok=0;
				ret+=ok;
			}
		}
		return ret;
		
	}
}

まとめ

Div1が解けていればあっさり。