HackerRank 101 Hack 55 : D. Special Set Pairs

本番だいぶ頭が混乱して手間取った。
https://www.hackerrank.com/contests/101hack55/challenges/distribution

問題

N要素の整数列A[i]が与えられる。
x≦yに対しf(x,y)は以下のように定義される。

• 
• 

Aの添え字である整数1～Nの部分集合X,Yのうちx∈X、y∈Xに対し、x＜yかつf(x,y)=0を満たす者の数を求めよ。

解法

f(x,y)について以下の特性が成り立つ。

• x＜x'ならf(x,y)≧f(x'y)
• f(x,y)=0のとき、f(x,y')=0となるyより大きな最小のy'は、xに依存しない。

Xのうち最小値x、Yのうち最小値yを定めた場合を考える。

• 前者の特性より、(x+1)～(y-1)はXに含めても含めなくてもよい。
• 後者の特性より、yをYに含めるなら、以後f(x,y')=0となるy'の各要素は含めても含めなくてもよい。

xを大きい順に探索し、xに対しf(x,y)=0となるyの数と、その各yに対する(x+1)～(y-1)から得られる組み合わせ総数に関し順次和を取っていくことで、解が求められる。
…だいぶ端折っているのだが、上の２つの特性により２の累乗が多数出てくる点に注意してDPしていくとよい。

int N;
ll A[1010101];
ll S[1010101];
ll M[1010101];
int nex[1010101];
ll mul[1010101];
ll sum[1010101];
ll mo=1000000007;
ll p2[1010101];

ll F(int x,int y) {
	if(x==y) return max(0LL,A[x-1]);
	return max(0LL,F(x,y-1)+A[y-1]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	p2[0]=1;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		p2[i+1]=p2[i]*2%mo;
	}
	
	map<ll,int> mp;
	mp[-1LL<<60]=N+1;
	ll ret=0;
	for(i=N-1;i>=0;i--) {
		if(A[i]>0) {
			auto it=mp.lower_bound(S[i]+1);
			it--;
			if(it!=mp.begin()) {
				nex[i]=it->second;
				ret+=sum[nex[i]]*p2[nex[i]-i-1];
				ret%=mo;
			}
		}
		else {
			auto it=mp.lower_bound(S[i+1]+1);
			it--;
			if(it==mp.begin()) {
				mul[i]=1;
				sum[i]=1;
			}
			else {
				nex[i]=it->second;
				mul[i]=mul[nex[i]]+1;
				sum[i]=sum[nex[i]]*p2[nex[i]-i]+p2[mul[i]-1];
				sum[i]%=mo;
				ret+=sum[nex[i]]*p2[nex[i]-i-1];
				ret%=mo;
			}
		}
		while(mp.rbegin()->first>=S[i+1]) mp.erase(mp.rbegin()->first);
		mp[S[i+1]]=i;
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

ややこしい問題設定と状態遷移だが、どうにか解けて良かった。