'🏆 Codeforces' 카테고리의 글 목록

🏆 Codeforces

[C++] Codeforces #768 Div.2 C : And Matching 2022.02.02
[C++] Codeforces #768 Div.2 B : Fun with Even Subarrays 2022.01.29
[C++] Codeforces #768 Div.2 A : Min Max Swap 2022.01.29
Codeforces Round #768 (Div. 2) : 첫 참가 후기 2022.01.28

[C++] Codeforces #768 Div.2 C : And Matching

2022. 2. 2. 19:19

문제

문제 해결

어떻게 해결해야 할 지 도저히 감이 안와서 상위 랭커분들의 코드를 참고했다. (들어가서 보고싶은 해당 문제 번호를 더블 클릭하면 된다.)

https://codeforces.com/contest/1631/standings

풀이의 핵심은 n이 2의 거듭제곱 꼴로 주어진다는 것에 있다. n이 2의 m제곱이라면 n-1의 이진수는 첫 번째부터 m번째까지의 모든 비트가 1이다. 예를 들어 n = 8(2의 3제곱)은 0부터 7까지므로 이를 이진수로 나열하면 아래와 같다. 편의상 하위 8비트까지만 나타냈다.

0 : 0000 0000
1 : 0000 0001
2 : 0000 0010
3 : 0000 0011

4 : 0000 0100
5 : 0000 0101
6 : 0000 0110
7 : 0000 0111

여기서 알고 있어야 하는 중요한 개념은 다음과 같다.

① (0 & (n-1)) + (1 & (n-2)) + ... + ((n/2-1) & (n/2)) = 0

② 0 ≤ i ≤ n-1일 때, i & (n-1) = i가 항상 성립한다. n은 2의 거듭제곱이기 때문에 n-1과 &연산을 하면 항상 자기 자신이 나온다.

①의 내용을 좀 더 살펴보자.

0의 m번째 비트까지 ^(XOR)연산을 한 결과는 n-1 → 0의 짝은 n-1,

1의 m번째 비트까지 ^(XOR)연산을 한 결과는 n-2 → 1의 짝은 n-2,

...

으로 설정할 수 있고, 두 수가 짝이 될 수 있는 이유는 &연산의 결과가 모두 0이기 때문이다. 또한 모든 수는 항상 자신의 짝이 존재하며 짝의 총 개수는 n/2개다.

m번째 비트까지 모두 1인 수는 n-1이므로, i와 그의 짝은 ((n-1)^i)로 구할 수 있다.

문제는 크게 세 가지 경우로 나눌 수 있다.

(1) k가 0인 경우

(2) k가 n-1인 경우

(3) 1 ≤ k ≤ n-2인 경우

(1) k가 0인 경우 :

(0 & (n-1)) + (1 & (n-2)) + ... + ((n/2-1) & (n/2)) = 0이므로 각각의 짝을 출력하면 된다.

(2) k가 n-1인 경우 :

n - 1 = n - 2 + 1 로 볼 수 있는데, n - 2는 ((n-1) & (n-2))로 구할 수 있다.

그렇다면 구해야 될 남은수는 1이고, 원래 각각 n-1, n-2의 짝이었던 0, 1은 짝이 사라진 상태가 된다.

위 두 상황을 한 번에 해결하는 방법이 0, 1의 잃어버린 짝을 각각 n/2, n/2-1로 설정하는 것이다. n/2와 n/2-1은 항상 서로 짝이므로 이를 0과 1에 매칭시키는 것이다.또한 n/2-1은 항상 홀수이기 때문에 n/2-1의 최하위 비트는 1이기 때문에 이를 1과 &연산하면 1을 얻을 수 있다.

하지만 n = 4, k = 3은 만족하는 경우가 없으므로 해당 경우만 예외로 처리해준다.

(3) 1 ≤ k ≤ n-2인 경우 :

앞서 i와 n-1을 & 연산하면 항상 i가 나온다고 했으므로, i의 원래 짝이었던 ((n-1)^i)과 n-1의 원래 짝이었던 0을 짝으로 만들어준다.

코드

#include <iostream>
using namespace std;

int t;

void solution() {

	int n, k;

	cin >> n >> k;

	if (k == n - 1) {
		if (n == 4)
			cout << -1 << '\n';

		else {
			cout << n - 1 << " " << n - 2 << '\n';
			cout << n / 2 - 1 << " " << 1 << '\n';
			cout << 0 << " " << n / 2 << '\n';
			for (int i = 2; i < n / 2 - 1; i++)
				cout << i << " " << ((n - 1) ^ i) << '\n';
		}
	}

	else if (k == 0) {
		for (int i = 0; i < n / 2; i++)
			cout << i << " " << ((n - 1) ^ i) << '\n';
	}

	else {	// 1 <= k <= n-2 일 때
		cout << n - 1 << " " << k << '\n';
		cout << 0 << " " << ((n - 1) ^ k) << '\n';
		for (int i = 0; i < n / 2; i++) {
			if (i == 0 || i == k || i == ((n - 1) ^ k)) continue;
			cout << i << " " << ((n - 1) ^ i) << '\n';
		}
	}
}

int main() {
	cin >> t;

	while (t--) {
		solution();
	}
}

저작자표시 비영리 변경금지

[C++] Codeforces #768 Div.2 B : Fun with Even Subarrays

2022. 1. 29. 03:36

문제

문제 해결

엉뚱한 지점에서 나를 헤매게 만들었던 문제다.. 하고 싶은 말이 많지만 각설하고 알고리즘은 다음과 같다.

매 operation마다 인덱스가 증가하면서, 뒷요소 값이 앞요소에 채워지므로 앞부분을 미리 같게 만드는 것은 아무런 의미 없다. 결국 모든 요소의 값이 같아지려면 맨 뒤의 값으로 채워져야하기 때문이다.

배열 a가 {4, 2, 1, 3}인 경우, 최종적으로는 {3, 3, 3, 3}이 될 수 밖에 없다.
이것이 문제에서 요구하는 알고리즘이다. (문제를 읽고 나름 빨리 알아챘지만 이미 다른 곳의 삽질에 심취해 있었을 때였다;)

입력 배열의 크기만 200,000 정도까지 된다는 것을 보고 이중 for문은 사용하지 않겠구나 싶어 일찍이 변수 l의 필요성에 대해 의심하기 시작했다.

끝부분부터 operation마다 1개, 2개, 4개, 8개, ... , 2^n개 꼴로 같은 값이 되므로 k가 n보다 크거나 같아질 때 반복문을 종료하면 된다. 단, 여기서 매우 중요한 점이 있는데.

예를 들어 n이 9이고 a의 입력이 {1, 1, 1, 1, 2, 1, 1, 1, 2}인 경우 (밑줄은 operation이 완료된 인덱스)

first operation result : a = {1, 1, 1, 1, 2, 1, 1, 2, 2}
second operation result : a = {1, 1, 1, 1, 2, 2, 2, 2, 2}

가 되는데 이때 second operation이 끝난 후 이미 같은 값으로 할당돼있는 개수를 세지 않으면 총 4번의 연산을 해야하지만, 개수를 센다면 3번의 연산으로 단축된다.

따라서 매 반복마다 완료된 인덱스 앞에 연속적인 같은 값의 개수를 추가로 세주어야 한다.

코드

#include <iostream>
using namespace std;

int t, nn, n, a[200002];

int main() {
    cin >> t;

    while (t--) {
        cin >> n;

        int k = 0;
        int res = 0;

        for (int i = 1; i <= n; i++) scanf("%d", a + i);

        while (1) {
            int x = n - k;
            
            while (x && a[x] == a[n]) {
                k++;
                x--;
            }

            if (k >= n) break;

            k *= 2;
            res++;
        }

        cout << res << '\n';
    }
}

저작자표시 비영리 변경금지

'🏆 Codeforces > ⏳ Solved on time' 카테고리의 다른 글

[C++] Codeforces #768 Div.2 A : Min Max Swap (0)	2022.01.29

[C++] Codeforces #768 Div.2 A : Min Max Swap

2022. 1. 29. 03:07

문제

문제 해결

두 배열의 각각의 max 값들을 곱해야하므로 모든 수 중 가장 큰 수는 무조건 계산에 들어가게 된다.

처음에는 배열 a, b를 합쳐서 오름차순으로 정렬한 뒤, 6번째 수와 12번째 수를 곱하면 될 줄 알았지만..

자세히 다시보니 같은 인덱스끼리만 swap 가능하다는 조건이 있었다.

간단하게 인덱스 0부터 n-1까지 큰 수를 a, b 중 한 곳에 몰아주면 된다.

코드

#include <iostream>
using namespace std;
 
int t, n, am, bm, a[101], b[101];
 
int main() {
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
 
        for (int i = 0; i < n; i++) if (a[i] > b[i]) swap(a[i], b[i]);
        am = 0;
        bm = 0;
 
        for (int i = 0; i < n; i++) {
            am = max(am, a[i]);
            bm = max(bm, b[i]);
        }
 
        cout << am * bm << '\n';
    }
}