[Easy] ImportantSequence
Topcoder SRM 540 Div1
operators[] 에 의해
a[i] + a[i+1] = C 혹은 a[i] - a[i+1] = C 가 나오는데
이걸 전부 잘 연립해서 a[i] 를 a[0] 에 대한 식으로 나타낼 수 있다.
구체적으로
a[i] = a[0] + X 혹은 a[i] = -a[0] + X 꼴이 된다.
모든 i에 대해 a[i] > 0 이어야 하므로
모든 부등식에 위 식을 대입해서 풀고
그 부등식들의 교집합을 구하면 a[0] 의 범위가 나온다.
이 범위를 만족하는 a[0] 의 가짓수가 답이 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <string> | |
| #include <algorithm> | |
| using namespace std; | |
| class ImportantSequence { | |
| public: | |
| int getCount(vector<int> B, string operators) { | |
| long long left = 1, right = 10000000000000ll; | |
| int sign = 1; | |
| long long offset = 0; | |
| for (int i = 0; i < B.size(); ++i) { | |
| if (operators[i] == '+') { | |
| sign = -sign; | |
| offset = -offset + B[i]; | |
| } | |
| else { | |
| sign = sign; | |
| offset = offset - B[i]; | |
| } | |
| if (sign == 1) { | |
| left = max(left, -offset + 1); | |
| } | |
| else { | |
| right = min(right, offset - 1); | |
| } | |
| } | |
| return right == 10000000000000ll ? -1 : max(right - left + 1, 0ll); | |
| } | |
| }; |