[CF] Round #649 (Div. 2) _ 200926

(2020년 10월 4일에 작성한 글입니다.)

 

Standings - Codeforces Round #649 (Div. 2) - Codeforces

학회 코드포스 스터디에서 버추얼로 풀었다.

 

A.

일단 'subarray'의 정의를 잘못 파악해서 처음에 틀렸다...

delete several elements from the beginning and from the end인데

sequence처럼 중간에 빼서 합쳐도 되는 줄

여튼 그거 때문에 처음에는

sum을 구해놓고 X로 나누어떨어지는지 확인해서

만약 안 나누어 떨어지면 N이 답이고

나누어 떨어지면, X의 배수가 아닌 수가 있는지 확인하고

만약에 있으면 N-1, 없으면 -1을 출력하는 방식으로 했는데

틀려서

subarray의 정의를 다시 체크한 다음에

input을 받을때부터 X의 배수가 아닌 수의 인덱스를 vector에 저장해놓고

sum이 X의 배수가 아니면 N 출력,

X의 배수이면, vector의 크기가 0이면 -1 출력,

아니면 앞, 뒤를 제거해서 subarray를 만들었을 때 더 긴 것을 출력

이런 식으로 했다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, X;
	int sum;
	int temp;
	bool flag;
	int i;

	cin >> T;
	while (T--) {
		cin >> N >> X;
		flag = false;
		sum = 0;
		vector<int> index;
		for (i = 0; i < N; i++) {
			cin >> temp;
			sum += temp;
			if (temp % X != 0) {
				flag = true;
				index.push_back(i);
			}
		}

		if (sum % X == 0) {
			if (flag) {
				cout << max(N - index.front() - 1, index.back()) << '\n';
			}
			else {
				cout << -1 << '\n';
			}
		}
		else {
			cout << N << '\n';
		}		
	}

	return 0;
}

 

B.

이것도 처음에 생각을 이상하게 해서 틀렸다.

만약에 연속적으로 증가하거나 감소하는 부분이 있으면

가장 첫 수와 마지막 수만 남겨놓고 나머지는 다 없애면 된다.

한 마디로 극대/극소 지점만 남겨놓으면 된다.

근데 이걸 처음엔 이상하게 풀었다..

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

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i];
		}
		
		vector<int> ans;
		ans.push_back(arr[0]);
		for (i = 0; i < N - 1;) { //i 종료조건 뭐야?
			if (arr[i] < arr[i + 1]) {
				for (; i < N - 1 && arr[i] < arr[i + 1]; i++);
			}
			else {
				for (; i < N - 1 && arr[i] > arr[i + 1]; i++);
			}
			ans.push_back(arr[i]);
		}

		cout << ans.size() << '\n';
		for (i = 0; i < ans.size(); i++) {
			cout << ans[i] << ' ';
		}
		cout << '\n';

	}

	return 0;
}