SRM 540 250pt : ImportantSequence

問題概要

ある数列A(|A|=N<50)がある。この数列は隣接する二項がA[i] op[i] A[i+1] = B[i] (op[i] = + or -, |B[i]|<10^9)となる。B[i]とop[i]からAが何通りに復元できるか求めよ。ただしA[i]>0でなくてはならない。無数にある場合は指摘せよ。有限である場合、答えはsinged 32bit integerの範囲に収まる。

解法

こういうのは何も考えずに初項を適当に変数で置いてそれ以降を表す。こうすると上限と下限が得られるので範囲を絞れる。オーバーフローなどに注意すること。

acceptされたコード

計算量O(N)。

#include <vector>
#include <string>
using namespace std;

typedef long long int64;

const int64 INF = 1LL<<59;


struct ImportantSequence {

	int getCount(vector<int> xs, string str) {
		const int N = xs.size();
		int64 lower = 1, upper = INF;

		bool plus = true;
		int64 sub = 0;
		for(int i=0; i<N; ++i){
			if(str[i] == '+'){
				plus ^= true;
				sub = xs[i] - sub;
			}
			else{
				sub = sub - xs[i];
			}

			//upperとlowerを更新
			if(plus){
				lower = max(lower, -sub + 1);
			}
			else{
				upper = min(upper, sub - 1);
			}
		}

		int64 ans = max(upper - lower + 1, 0LL);
		return ans > (1LL<<55) ? -1 : ans;
	}

};