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; } };