[CF] Round #672 (Div. 2) _ 200924

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

 

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

 

A.

Bubble Sort에서 swap이 최대로 이루어지면 그 횟수는 N*(N-1)/2 이기 때문에

최대로 이루어지는 경우가 아니기만 하면 된다.

그 경우는 수열의 수들이 모두 감소하는 경우이고

그러니까 한번이라도 a[i-1] <= a[i]인 경우가 있으면 YES다.

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

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> arr(N);

		ans = false;
		cin >> arr[0];
		for (i = 1; i < N; i++) {
			cin >> arr[i];
			if (arr[i - 1] <= arr[i]) {
				ans = true;
			}
		}

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

	return 0;
}

​

B.

2^k <= a[i] < 2^(k+1)일때

a[j]도 저 범위에 들어있는 경우의 수를 구하면 된다.

구현의 방법에는 차이가 있겠지만

그냥 저 범위들에 들어있는 개수를 모두 구한 다음에

(개수)C2한 것들을 모두 더하면 된다.

순서 상관 없이 2개를 뽑는 경우의 수들의 합.

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

	vector<int> bin;
	for (i = 1; i <= 1000000000; i *= 2) {
		bin.push_back(i);
	}
	bin.push_back(i);

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i];
		}

		vector<int> cnt(40, 0);
		for (i = 0; i < N; i++) {
			k = upper_bound(bin.begin(), bin.end(), arr[i])-bin.begin() - 1;
			cnt[k]++;
		}

		ans = 0;
		for (i = 0; i < 40; i++) {
			ans += (ll)cnt[i] * (ll)(cnt[i] - 1) / 2;
		}

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

	return 0;
}

 

C1.

이걸 끝까지 못풀었어ㅠㅠㅠㅠㅠㅠㅠㅠ

DP적 사고가 정말정말 부족하구나.

효규의 풀이는​

dp[i][2]라고 두고

dp[i][0]은 -로 가져갈 때

dp[i][1]은 +로 가져갈 때면

dp[i][0] = max(dp[i-1][0], dp[i - 1][1] - arr[i]);
dp[i][1] = max(dp[i-1][0] + arr[i], dp[i-1][1]);

이렇게 하면 된다...

​

어떻게 해아할 지 모르겠어서

세그트리로 막 했는데

구현은 둘째치고 풀이 자체가 틀렸음을

한 번 틀리고 깨달았다...

​

으악 DP....