알고스팟 - 외계 신호 분석 (ITES) [C++]

 이 문제는 덱을 이용해서 풀었다. 최대 수행 시간이 15000ms 이므로 15초이다. 즉, 15억번의 연산 안에 알고리즘을 짜면 된다. 

 

 부분 수열이 연속적인 부분 수열이고, 범위의 중복이 가능하다고 했으므로 덱을 이용해서 풀어야겠다고 생각했다. 유의할 점은 ll A[MAX + 1] 배열을 만들면 메모리 초과가 뜨는데, 이를 해결하기 위해서는 매 루프마다 A[i] 의 값을 직접 계산하면 된다.

 

#include <iostream>
#include <deque>

using namespace std;

typedef long long ll;
typedef unsigned int ui;

#define MAX 50000000
#define INIT_MOD 4294967296ll

ll solve(int K, int N) {
	ll acc = 0;
	ll answer = 0;
	deque<int> dq;

	ll A = 1983;

	for (int i = 1; i <= N; i++) {
		if (i != 1) {
			A = (A * 214013 + 2531011) % INIT_MOD;
		}

		ll presentNum = A % 10000 + 1;
		acc += presentNum;
		dq.push_back(presentNum);

		if (acc == K) {
			answer++;
			continue;
		}

		if (acc > K) {
			while (!dq.empty() && acc > K) {
				int front = dq.front();
				dq.pop_front();
				
				acc -= front;

				if (acc == K) {
					answer++;
				}
			}
		}
	}

	while (!dq.empty() && acc > K) {
		int front = dq.front();
		dq.pop_front();

		acc -= front;

		if (acc == K) {
			answer++;
		}
	}

	return answer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		int K, N;

		cin >> K >> N;

		ll answer = solve(K, N);

		cout << answer << '\n';
	}

	return 0;
}