topcoder

kojingharangの日記

2012-04-11

SRM Div2 500 ImportantSequence

23:07 |

B[N], OP('-'か'+')[N] が与えられて、A[i] OP[i] A[i+1] = B[i], A[i]>0 であるとき、A[0]～A[N] として可能な値の組み合わせはいくつあるか答える問題。無限にあるなら -1 を返す。

A[0] が決まると全ての A[i] が決まる。
なので、式 A[i] > 0 を A[0] '>'|'<' v に変換する。v と演算子によって A[0] の上限と下限が決まる。
上限か下限が無い場合、解は無限にあるので -1 をかえす
max(0, 上限 - 下限+1) が答え。
0 と max とってなくて死亡....

↓ (passed in practice room)

// PII, VI の定義を変えて ll を使うようにしてある
class ImportantSequence {
	public:
	PII f(int i, int op, ll v, vector <int>& B, string& OP) {
		if(i==0) return MP(op, v);
		op *= OP[i-1]=='-' ? 1 : -1;
		v *= (ll)(OP[i-1]=='-' ? 1 : -1);
		v += (ll)B[i-1];
		return f(i-1, op, v, B, OP);
	}
	int getCount(vector <int> B, string OP) {
		VI lb, ub;
		REP(i, B.size()+1) {
			PII p = f(i, 1, 0, B, OP);
			if(p.first== 1) lb.PB(p.second);
			if(p.first==-1) ub.PB(p.second);
		}
		//cout<<lb<<endl;
		if(lb.size()==0 || ub.size()==0) return -1;
		ll l = *max_element(ALL(lb));
		ll u = *min_element(ALL(ub));
		//cout<<l<<endl;
		//cout<<u<<endl;
		//return (u-1)-(l+1)+1; // NG!
		return max((ll)0, (u-1)-(l+1)+1);
	}
};