Codeforces Global #18

A. Closing The Gap

Problem - A - Codeforces

Problem - A - Codeforces

타워 \(n\)개가 주어진다.

타워의 최대 높이 - 최소 높이의 값을 최소화하는 문제이다.

 

타워들의 높이 합이 \(n\)으로 나누어 떨어지면 0, 나누어 떨어지지 않으면 1이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int tmp; cin >> tmp;
            sum += tmp;
        }
        cout << (sum % n ? 1 : 0) << '\n';
    }
    return 0;
}

 

 

B. And It's Non-Zero

Problem - B - Codeforces

Problem - B - Codeforces

\([l, r]\) 범위에서 숫자를 제거하여 bitwise AND 값이 0이 아니도록 만들 때, 최소 제거 횟수를 구하는 문제이다.

 

\(psum[i][j]\)를 \([1, j]\) 범위에서 \(i\)번째 비트가 \(0\)인 숫자들의 개수로 정의하자.

답은 \(\min(psum[i][r] - psum[i][l-1])\)이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const int MAX = 2e5+2;
int p[20][MAX];
 
int main(void) {
    for (int i = 0; i < 18; i++) {
        int cur = (1 << i);
        for (int j = 1; j < MAX; j++) {
            p[i][j] = p[i][j-1];
            if ((j & cur) == 0) {
                p[i][j]++;
            }
        }
    }
    int t; cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        int mn = INT_MAX;
        for (int i = 0; i < 18; i++) {
            mn = min(mn, p[i][r] - p[i][l-1]);
        }
        cout << mn << '\n';
    }
    return 0;
}

 

 

C. Menorah

Problem - C - Codeforces

Problem - C - Codeforces

길이 \(n\)의 binary string \(a, b\)가 주어진다.

어떤 비트 \(1\)을 선택하고 move하면 해당 비트를 제외한 나머지 비트들이 flip된다.

\(a\)를 \(b\)로 만드는 데 최소 몇 번의 move가 필요한지 구하는 문제이다.

 

두 번의 move가 어떤 효과를 갖는지 살펴보자.

1) 같은 비트를 선택했을 때

해당 비트를 제외한 나머지 비트들이 두 번 flip되므로 아무런 효과가 없다.

2) 서로 다른 비트를 선택했을 때

문자열에서 \(0\)과 \(1\)을 한 번 swap한 것과 같다.

 

다음과 같이 경우를 나누어 답을 구할 수 있다.

\(a\)와 \(b\)의 \(i\)번째 비트를 각각 \(a_i, b_i\)라고 하자.

1) 답이 짝수인 경우

\(a\)의 \(1\)의 개수와 \(b\)의 \(1\)의 개수가 동일하면 YES이다.

\(a_i \neq b_i\)를 만족하는 \(i\)의 개수가 답이다.

2) 답이 홀수인 경우

처음 한 번의 move 이후에는 답이 짝수인 경우와 동일하다.

\(a_i = b_i = 1\)인 \(i\)가 존재하고, \(a\)의 \(1\)의 개수 - \(1\)과 \(b\)의 \(0\)의 개수가 동일하면 YES이다.

\(a_i = b_i\)를 만족하는 \(i\)의 개수가 답이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string a, b;
        cin >> a >> b;
 
        int cnt = 0;
        int one[2] = { 0, 0 };
        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (a[i] == '1') one[0]++;
            if (b[i] == '1') one[1]++;
            if (a[i] == b[i]) {
                if (a[i] == '1') {
                    flag = true;
                }
                cnt++;
            }
        }
        int ans = INT_MAX;
        if (one[0] == one[1]) {
            ans = min(ans, n - cnt);
        }
        if (flag && one[0] - 1 == n - one[1]) {
            ans = min(ans, cnt);
        }
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
    return 0;
}

 

 

D. X(or)-mas Tree

Problem - D - Codeforces

Problem - D - Codeforces