SRM540 Div1 Easy

250

1次式にして値の範囲を決める。
数式だけ見ると簡単なんだけど、Div1が阿鼻叫喚になるような問題だった。



最初のサンプルだと
"+-+"
3, -1, 7

式を A + B - C + D とすると、
(A + B) = 3
(B - C) = -1
(C + D) = 7
これを
B = 3 - A
C = 4 - A
D = -3 + A
とすると A の範囲が決められる。
どうやればいいのか一見して思い浮かばなかったけど、符号の反転に注意して頭から計算すればいいだけだった。

class ImportantSequence {
public:
  int getCount(vector <int> B_, string O)
  {
    const int size = B_.size();
    vector<lli> B;
    for (int i = 0; i < (int)size; ++i) {
      B.push_back(B_[i]);
    }

    const lli inf = 1LL << 60;

    int sign = 0;
    lli n = 0;

    lli pA = 1;
    lli nA = inf;

    for (int i = 0; i < (int)size; ++i) {
      if (O[i] == '+') {
        n = B[i] - n;
        sign ^= 1;
      } else {
        n = -B[i] + n;
      }
      
      if (sign) {
        nA = min(nA, n - 1);
      } else {
        pA = max(pA, -n + 1);
      }
    }

    lli ret = nA - pA + 1LL;

    if (ret < 0) return 0;
    if (ret < INT_MAX) return ret;
    return -1;
  }
};