問題
http://community.topcoder.com/stat?c=problem_statement&pm=11842&rd=14732
解き方
上限と下限を決めるのに、最初の数字は増加列になる。
a(i)=s*a0+t、(初項はs=1,t=0)とする。
+が現れた時、そのときの数字B[i]について
a(i)+a(i+1)=B[i]となるので
a(i+1)=-s*a0+B[i]-tとなり、このとき切片が上限となる。
同様に-が現れた時、a(i)-a(i+1)=B[i]から
a(i+1)=s*a0+t-B[i]となり、このとき切片が下限となる。
以上の条件を満たしていくことで上下限が求められる。
コード
class ImportantSequence {
public: int getCount(vector<int> B, string operators) {
int n=B.size();
long long s=1,t=0;
long long low=0,high=LONG_MAX;
FORE(i,0,n+1){
if(s==1){
low=max(low,-t);
}else{
high=min(high,t);
}
if(i==n)break;
if(operators[i]=='+'){
s*=-1;
t=B[i]-t;
}else{
t=t-B[i];
}
}
if(high==LONG_MAX)return -1;
if(low>=high)return 0;
return high-low-1;
}
};
public: int getCount(vector<int> B, string operators) {
int n=B.size();
long long s=1,t=0;
long long low=0,high=LONG_MAX;
FORE(i,0,n+1){
if(s==1){
low=max(low,-t);
}else{
high=min(high,t);
}
if(i==n)break;
if(operators[i]=='+'){
s*=-1;
t=B[i]-t;
}else{
t=t-B[i];
}
}
if(high==LONG_MAX)return -1;
if(low>=high)return 0;
return high-low-1;
}
};