[CF] Round #683 (Div. 2, by Meet IT) _ 201115

(2020년 11월 20일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #683 (Div. 2, by Meet IT) - Codeforces

 

A.

쉬운 문제인데 컨디션이 안 좋아서 오래 걸렸다.

결국 N을 1~N 수들을 하나씩 출력하면 되는 문제.

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;
		cout << N << '\n';
		for (i = 1; i <= N; i++) {
			cout << i << ' ';
		}
		cout << '\n';
	}
	return 0;
}

​

C.

B 모르겠어서 C부터 풀었다.

내림차순으로 정렬한 후 큰 것부터 고른다.

근데 더했을 때 W보다 커지면 안 고르고

그렇게 더해나갔을 때 범위 안에 들어가면 된다.

근데 여기서 W / 2가 홀수일 때 올림해야 하는데

그 부분을 놓쳐서 제출을 한 번 낭비했다.

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

	cin >> T;
	while (T--) {
		cin >> N >> W;
		vector<pair<ll, int>> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i].first;
			arr[i].second = i + 1;
		}
		sort(arr.begin(), arr.end(), greater<>());

		ll sum = 0;
		vector<int> list;
		for (i = 0; i < N; i++) {
			if ((W + 1) / 2 <= sum && sum <= W) {
				break;
			}

			if (sum + arr[i].first <= W) {
				sum += arr[i].first;
				list.push_back(arr[i].second);
			}
		}
		
		if (!((W + 1) / 2 <= sum && sum <= W)) {
			cout << -1 << '\n';
			continue;
		}

		cout << list.size() << '\n';
		sort(list.begin(), list.end());
		for (i = 0; i < list.size(); i++) {
			cout << list[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

B.

처음에 생각한 아이디어는

NM이 되게 작아서, NM 칸을 모두 돌면서

바꿨을 때 값의 변화가 최대가 되는 곳을 저장해놓고

그 위치의 값을 바꾸는 방법으로 했는데

틀렸고

반례를 찾았고

마이너스들끼리 묶어놓아야 한다는 걸 깨달았다.

​

그래서 0 이하의 수의 개수를 세놓고

그게 짝수면, abs들의 합이 답이고

그게 홀수면 abs들의 합 - (가장 작은 abs) * 2

이게 답이다

....

효규가 이 문제를 8분만에 푼 데에는 다 이유가 있었다....

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, M;
	int sum;
	int cnt;
	int min_;
	int i, j;

	cin >> T;
	while (T--) {
		cin >> N >> M;
		vector<vector<int>> arr(N, vector<int>(M));
		sum = 0;
		cnt = 0;
		min_ = int_inf;
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				cin >> arr[i][j];
				sum += abs(arr[i][j]);
				min_ = min(min_, abs(arr[i][j]));
				if (arr[i][j] <= 0) {
					cnt++;
				}
			}
		}

		if (cnt % 2 == 0) {
			cout << sum << '\n';
		}
		else {
			cout << sum - 2 * abs(min_) << '\n';
		}

	}
	return 0;
}