[CF] Round #668 (Div. 2) _ 200906

(2020년 9월 7일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #668 (Div. 2) - Codeforces

 

A.

배열을 그냥 거꾸로 출력하면 된다..ㅎ

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int cur;
	bool flag;
	int i;

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> num(N);
		flag = false;

		for (i = 0; i < N; i++) {
			cin >> num[i];
		}

		for (i = N - 1; i >= 0; i--) {
			cout << num[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

​

B.

pretest는 통과했는데 본 테스트에서 시간 초과가 났다.

어떻게 보면 당연한거 같기도...?

효규가 설명해줬는데

sum에 양수들만 저장해놓고

음수를 만나면 sum에서... 무슨 말인지 알겠지?

왜 이걸 생각 못했을까. 너무 아쉬워.​

int main()
{
	int T;
	int N;
	int i;
	ll sum, ans;
	ll temp;

	cin >> T;
	while (T--) {
		cin >> N;

		sum = ans = 0;
		for (i = 0; i < N; i++) {
			cin >> temp;
			if (temp > 0) {
				sum += temp;
			}
			else {
				if (sum > temp * -1) {
					sum += temp;
				}
				else {
					ans += (temp + sum) * -1;
					sum = 0;
				}
			}
		}

		cout << ans << '\n';
	}
}

​

C.

길이가 K인 substring.

맨 첫 substring이 가능한거라면

(불가능하다면 바로 끝내고)

첫 번째 문자랑 K+1번째 문자를 비교해서 둘이 다르면 불가능.

만약 K+1번째 문자가 ?이면 거기에 첫 번째 문자를 넣기.

만약 둘 다 물음표라면 그냥 패스.

이 과정에서, 0과 1의 개수가 모두 K/2인지 확인해줘야 함.

​

이런 식으로 하면 된다는데.

뭔가 미심쩍어서 반례를 찾아보려 했지만 맞는 거 같다.

왜냐하면 1번째 ~ K번째가 되는 상태이기 때문에

2번째 ~ K번째는 보장이 된 거고

그렇기 때문에 1번째랑 K+1번째만 비교하면 되는거고.

​

그렇게 뒤에를 채울 때 앞에 있는 물음표도 신경써야 하는 거 아니야?

라고 생각했는데,

앞에 있는 것들은 이미 지나간거니까 신경쓸 필요 없음.

그냥 그것들은 뭐든지 될 수 있는 애들인거니까.

뒤에 상황과 상관 없이, 항상 가능한 경우가 존재하는거다.​

int K;
string s;
vector<int> cnt(2);

void update(int index)
{
	int i;

	if (cnt[0] == K / 2 && cnt[1] == K / 2) {
		return;
	}

	if (cnt[0] == K / 2) {
		for (i = 0; i < K; i++) {
			if (s[index + i] == '?') {
				s[index + i] = '1';
			}
		}
		cnt[1] = K / 2;
	}
	else if (cnt[1] == K / 2) {
		for (i = 0; i < K; i++) {
			if (s[index + i] == '?') {
				s[index + i] = '0';
			}
		}
		cnt[0] = K / 2;
	}

	return;
}

bool isWrong()
{
	if (cnt[0] > K / 2 || cnt[1] > K / 2) {
		return true;
	}
	else {
		return false;
	}
}

int main()
{
	int T;
	int N;
	int i;

	cin >> T;
	while (T--) {
		cin >> N >> K;
		cin >> s;

		cnt[0] = cnt[1] = 0;
		for (i = 0; i < K; i++) {
			if (s[i] != '?') {
				cnt[s[i] - '0']++;
			}
		}
		if (isWrong()) {
			cout << "NO" << '\n';
			continue;
		}

		bool notOkay = false;
		for (i = 0; i < N - K; i++) {
			if (isWrong()) {
				notOkay = true;
				break;
			}
			update(i);

			if (s[i] == '?') {
				s[i] = s[i + K];
				if (s[i] != '?') {
					cnt[s[i] - '0']++;
				}
			}
			else { //s[i]가 이미 0 또는 1
				if (s[i + K] != '?' && s[i] != s[i + K]) {
					notOkay = true;
					break;
				}
				if (s[i + K] == '?') {
					s[i + K] = s[i];
				}
			}
		}

		if (notOkay) {
			cout << "NO" << '\n';
		}
		else {
			cout << "YES" << '\n';
		}
	}
}