Codeforces Round #757 (Div. 2) A부터 C까지 업솔빙

Codeforces Round #757 (Div. 2) A부터 C까지 업솔빙

이번에도 B번 문제까지 풀어서 퍼포가 1070정도 나온 대회이다. 솔직히 마지막 문제는 너무 뻔한 이진수 + 조합론 + XOR문제였는데, 아직 경험이 부족해서 문제를 못푼 것 같았다. 이런 문제를 처음 봤었으면 절대로 못풀었겠지만 지금와서 보면 생각보다 코드포스에서 나오는 문제들이 정형화되어있다는 것을 느꼈다. 그런데 느끼기만 하면 뭐해... 풀어야지...
이번 대회에서 배운 것은

1. 자릿수와 이진수
2. 당황하지 않기

A. Divan and a Store (*800)

접기/펼치기

문제 설명
$n$개 초콜릿 바가 있다. $i$번째 초콜릿 바는 $a_i$원이다. 이 값이 $r$원 보다 크면 비싸다고 생각하고, 이 값이 $l$원 보다 작으면 너무 싸다고 생각한다. 그리고 민호는 너무 비싸거나 너무 싼 초콜릿바는 사지 않는다.

민호는 최대 $k$원을 사용해서 초콜릿 바를 최대한 많이 사려고 한다.

민호가 살 수 있는 최대 초콜릿 바의 개수는 무엇일까?

문제 해설
기본 그리디 문제. 오름차순으로 값을 정렬하고, 값이 $l$과 $r$사이에 들어온다면 $k$에서 빼주고, 아니면 빼지 않는다. $k$가 음수가 되는 순간에 break를 해주는 것도 잊지 말아야 한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, l, r, k; cin >> n >> l >> r >> k;
        int a[n];
        for(auto& x : a) cin >> x;
        sort(a, a + n);
        int cnt = 0;
        for(auto x : a){
            if(k < x) break;
            if(l <= x && x <= r) cnt++, k -= x;
        }
        cout << cnt << "\n";
    }
    return 0;
}

B. Divan and a New Project (*1000)

접기/펼치기

문제 설명
민수 전자는 수직선에 빌딩 $n + 1$개를 새우려고 한다. 그리고 다음 조건을 만족해야 한다.

• 각 빌딩의 좌표는 정수다.
• 한 좌표에 두개 이상의 빌딩이 동시에 있을 수 없다.

$x_i$를 빌딩 $i$의 좌표라고 할때, 빌딩 $i$에서 빌딩 $j$까지 이동하려면 $|x_i - x_j|$분이 걸린다.

모든 빌딩은 $0$부터 $n$까지 번호가 붙여져 있으며 민수는 빌딩 $0$에 있다. 민수는 $0$번 빌딩을 제외한 모든 빌딩을 $a_i$번 방문해야 한다. 그리고 $0$번째 빌딩에서 $i$번째 빌딩까지 왔다 갔다 하는데 걸리는 시간은 $2 \cdot |x_0 - x_i|$ 이다.

우리가 해야할 것은 민수가 빌딩을 방문할 때 최소시간이 걸리게 $n + 1$ 개 빌딩의 좌표를 설정하는 것이다.

문제 해설
좌표를 구성하는 구성적 알고리즘 문제이다. 좌표를 아무거나 설정한다고 했기 때문에 처음에 0번째 빌딩은 항상 0으로 고정했다. 그러면 단순하게 생각하면 가장 많이 방문해야 하는 빌딩을 0과 가까운 곳에 위치해야 무조건 최소 시간만큼 이동할 수 있을 것이라는 생각이 들 것이고 이 생각이 이 문제의 전부이다.

0번째 빌딩을 0에 위치하고 $a_i$가 큰 순서대로 각각 $1, -1, 2, -2, ...$ 이런 식으로 좌표를 퐁당 퐁당 배치하면 답을 구할 수 있다. 총 합계 계산은 그냥 하면 된다.

이 문제에서는 $a_i$와 이 빌딩이 몇번째 빌딩인지까지 알아야 하기 때문에 pair을 사용해서 정렬해야한다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<pair<int, int>> v;
        for(int i = 1; i <= n; i++){
            int num; cin >> num;
            v.push_back({num, i});
        }
        sort(v.begin(), v.end(), greater<>());
        vector<int> ans(n + 1);
        long long sum = 0;
        for(int i = 0; i < n; i++){
            if(i & 1) ans[v[i].second] = i / 2 + 1;
            else ans[v[i].second] = -(i / 2 + 1);
            sum += 2 * 1LL * v[i].first * (i / 2 + 1);
        }
        cout << sum << "\n";
        for(auto x : ans) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

C. Divan and bitwise operations (*1500)

접기/펼치기

문제 설명
민수는 $n$개의 음이 아닌 정수로 이루어진 수열 $a_1, a_2, ..., a_n$을 분석하려고 한다. 수열 $a$의 모든 subseqence에 있는 모든 원소들을 XOR한 값을 전부 더한 값을 수열 $a$ 의 coziness 라고 하자.

민수는 이 분석을 매우 좋아하지만 수열 $a$를 까먹어 버렸다! 그리고 coziness 또한 잊어버렸다. 민수가 기억하는 숫자는 $m$개의 연속한 수열 $a$의 subseqence에 있는 모든 원소값의 OR값이다.

민수가 기억하는 정보를 가지고 수열 $a$의 coziness 를 구하라. 만약 답이 여러개라면 아무거나 출력한다. 결과값이 매우 크기 때문에 $10^9 + 7$을 나눈 나머지 값을 출력한다.

문제 해설
뻔하디 뻔한 문제지만 풀지 못한 문제.

이런 문제는 결국

1. XOR은 1을 홀수번 연산하면 1이고, 짝수번 연산하면 0이다.
2. $nC0 + nC1 + .... + nCn == 2^{n}$ 이다.

이 두 성질을 사용하는데, 거기에 자릿수 개념까지 추가했다.

일단 알수 있는 것은 OR값을 연산 결과로 보여줬기 때문에 주어진 subseqence 구간에 한 원소만 OR값으로 지정하고 나머지 값을 0으로 해도 조건을 만족한다는 것이다. 만약 1 4 5라고 주어지면 이 subseqnece는 $[0, 0, 0, 5]$라고 할 수 있는 것이다. 그리고 이런식으로 수열을 구성하면 이야기가 쉬워진다. $m$개의 조건에 나오는 모든 OR연산값이 결국 최종 수열에 1번씩 나오고, 나머지 수열 값은 0으로 하는 수열이 존재한다는 것과 마찬가지이기 때문이다.

그러면 평소 하던 것처럼 이 수들을 비트별로 나눠서 생각해보자. 전체 $n$개의 수가 이 수열에 있을 텐데, 이 수들의 $i$번째 비트를 보자. $0$과 $0$ 끼리 xor연산을 하면 값이 변하지 않기 때문에 $i$번째 비트가 0인 수들의 집합을 $A$라고 하고, $i$번째 비트가 $1$인 수들의 집합을 $B$라고 하자.

일단 집합 $A$의 수 끼리 아무리 XOR을 한다 해도 $i$번째 비트 값은 0이기 때문에 집합 $A$에서 나올 수 있는 모든 경우의 수인 $2^{|A|}$ 만큼 $0$이 나온다.

이제 집합 $B$가 문제인데, 1을 홀수번 연산하면 1이기 때문에 집합 B의 수를 홀수개 선택하는 경우의 수를 구해야 하고 이 수는 이항정리에 의해서 $2^{|B| - 1}$ 이다. 이 두 경우의 수를 곱하면 $i$번째 비트가 1이 되는 경우의 수를 모두 구했고, $1$을 $2^{|A| + |B| - 1}$ 번 더한다. 이때 $|A| + |B| = n$이기 때문에 $2^{n - 1}$개 만큼 $i$번째 비트의 1을 더한다.

$i$번째 비트에 있는 모든 수가 0이면 그 수는 고려할 필요가 없고, 하나라도 1이면 그 수는 고려해야한다. 따라서 $m$개 수를 모두 or한 값이 $1$이면 이 자리 비트는 고려해야 한다는 뜻이다. 각 자릿수마다 경우의 수가 $2^{n - 1}$ 이고, 자릿수가 $2^{i - 1}$이기 때문에 그냥 이 문제의 답은 $2^{n - 1} \cdot $ 모든 $m$개의 수를 OR한 값이다. $n$이 큰 수이기 때문에 빠른 거듭제곱 알고리즘을 사용해서 문제를 반드시 풀어야 한다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;

ll ppow(ll x, ll n){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = (res * x) % mod;
        n >>= 1;
        x = (x * x) % mod;
    }
    return res % mod;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll n, m; cin >> n >> m;
        ll sum = 0;
        while(m--){
            ll l, r, x; cin >> l >> r >> x;
            sum |= x;
        }
        cout << (ppow(2, n - 1) * sum) % mod << "\n";
    }
    return 0;
}