TopCoder SRM 816 : Div1 Easy Div2 Hard BalancedAirplane

とてもしょうもないミスで落としてるのが残念。
https://community.topcoder.com/stat?c=problem_statement&pm=17221&rd=18894

問題

01で構成された行列が与えられる。
いくつかの連続した行を選択したとき、各列の総和が一致するようにしたい。
そのような行の選び方は何通りか。

解法

R行目までにおける、各列の値の和からなる数列をC[R]とする。
C'[R]を、C[R]からそのうち最小値を引いた数列とする。
C'[R]=C'[R']となる(R,R')が存在する場合、(R+1)行目からR'行目までを選択すると条件を満たす。

あとはvectorのmapなど使い数え上げて行こう。

class BalancedAirplane {
	public:
	long long count(int S, int R, vector <int> Aprefix) {
		int L=Aprefix.size();
		vector<ll> A;
		int i,j;
		FOR(i,L) A.push_back(Aprefix[i]);
		ll state=A[L-1];
		for(i=L;i<R;i++) {
			state=(state * 1103515245 + 12345) %(1LL<<31);
			A.push_back(state>>(31-S));
		}
		ll ret=0;
		vector<int> C(S,0);
		map<vector<int>,int> M;
		M[C]++;
		FOR(i,R) {
			FOR(j,S) if(A[i]&(1LL<<j)) C[j]++;
			int mi=1<<30;
			FORR(a,C) mi=min(mi,a);
			FORR(a,C) a-=mi;
			ret+=M[C];
			M[C]++;
		}
		
		return ret;
		
	}
}

まとめ

なんだかなぁ。