TopCoderOpen 2015 Round2D Easy BalancedSubstrings

EasyはキープしたけどMedはミスるしChallengeは失敗するちいまいち。
http://community.topcoder.com/stat?c=problem_statement&pm=13885

問題

'01'だけで構成された長さLの文字列Tに対し、以下の状態を考える。
長さ(N-1)の重さの無い棒を考える、端から長さiの地点に、T[i]=='1'なら(同じ重さの)重りを一つぶら下げる。
棒の端からの長さが整数の位置に天秤の中心を置いたとき、この天秤が傾かないなら、この文字列はバランスが取れていると考える。

N文字の'01'だけで構成された文字列Sがある。
Sの部分文字列のうち、バランスが取れているものがいくつあるか。

解法

O(N^2*logN)解法やO(N^2)解法があるようだ。
自分は前者。

自分は天秤の中心の位置iを総当たりし、左右それぞれ部分文字列の左端・右端を伸ばした際、棒の左側・右側の重さをmapで数え上げ、左右同じ重さの組み合わせを掛け合わせた。
注意点は棒全体の重さが0の場合で、これは天秤の中心がどこでもバランスが取れてしまい、多重カウントの恐れがあるのでそれだけ別に数えた。

O(N^2)解法は棒の左端を決め、右端を徐々に伸ばしながらバランスが取れる位置に中心を微調整していく解法などがある。

class BalancedSubstrings {
	public:
	int countSubstrings(string s) {
		int N=s.size();
		int i,c,ret=0;
		
		FOR(i,N) s[i]-='0';
		
		FOR(c,N) {
			map<int,int> M[2];
			int ls=0,rs=0;
			
			for(i=c;i>=0;i--) ls += s[i]*(c-i), M[0][ls]++;
			for(i=c;i<N;i++) rs += s[i]*(i-c), M[1][rs]++;
			ITR(it,M[0]) if(it->first || s[c]==1) ret+=it->second*M[1][it->first];
		}
		int len=0;
		FOR(c,N) ret += (len = (s[c]?0:len+1));
		
		return ret;
	}
}

まとめ

O(N^3)解法書く人いると思ったんだけどなぁ。