SRM 540 div1 easy: ImportantSequence
問題
TopCoder Statistics - Problem Statement
n 個の要素からなる数列 B と, n 個のオペレータ(+ か -)の列 ops が与えられる。
数列 A は正整数から構成され, A[i] `ops[i]` A[i+1] = B[i] を満たすように構成しなければならない。この条件を満たす数列 A は何通り考えられるか。
解法
A[0] さえ決めれば, 他の要素も決定します。そこで, A[0] = 1 の時の数列 A を求めておきます。
また, A[0] の値を 1 上昇させた際の A[i] の変化量(+1 か -1)もわかります。これらの情報が分かれば, 「A[i] を正の値にするためには, A[0] の値は 1 から最低いくつ上昇させないとダメで, これ以上上昇させてはダメ」という下限と上限がわかります。
上限の最小値 - 下限の最大値 + 1 が答えです。
下のコードはこれをめっちゃ愚直に書いてますが, A[0] の値を 1 上昇させた際の A[i] の変化量が +1 か -1 であることが分かっていればもっと簡単に書けます。
const ll INF = 1ll<<55; class ImportantSequence { public: int getCount(vector <int> B, string ops) { int n = B.size(); bool inf = true; for (int i = 0; i < n; i++) inf &= ops[i] == '-'; if (inf) return -1; vector<ll> A(n+1), trans(n+1); A[0] = 1; trans[0] = 1; for (int i = 0; i < n; i++) { if (ops[i] == '+') { A[i+1] = B[i]-A[i]; trans[i+1] = -trans[i]; } else { A[i+1] = A[i]-B[i]; trans[i+1] = trans[i]; } } vector<ll> mini(n+1), maxi(n+1); for (int i = 0; i <= n; i++) { if (trans[i] == 0) { if (A[i] <= 0) return 0; else mini[i] = 0, maxi[i] = INF; } else if (trans[i] > 0) { maxi[i] = INF; if (A[i] > 0) mini[i] = 0; else { ll need = 1-A[i]; mini[i] = need/trans[i] + !!(need%trans[i]); } } else { mini[i] = 0; if (A[i] <= 0) return 0; else { maxi[i] = (A[i]-1) / (-trans[i]); } } } for (int i = 0; i <= n; i++) { maxi[0] = min(maxi[0], maxi[i]); mini[0] = max(mini[0], mini[i]); } if (maxi[0] < mini[0]) return 0; else return maxi[0]-mini[0]+1; } };