Codeforces Round #768 (Div. 2)

죄송합니다

 

썸네일의 민트 돈가스를 보고 아실 분들은 아셨겠지만.. 저 민트 갔어요! 오예

 

 

 

 

사실 주위에 고수들이 많아서 그동안 민트를 좀 만만하게 봤다.

(내 주위에 코포하는 사람들은 대부분 블루 이상이라서...)

만만한 건 내 실력이었고 ㅋㅋ

 

보시다시피 민트 바로 앞에서 쭉 떨어지고 다시 고생을 좀 했습니다 ㅠㅠ

 

턱걸이로 찍은 거긴 하지만,,, 기분이 매우 좋다!

암튼 최근 3번이나 후기글을 안 썼는데, 오늘 민트 간 기념으로 간만에 쓴다 ㅎㅎ.

 

와! 1시간동안 3솔!

---

A.

같은 크기의 수열 a와 수열 b가 주어진다. idx가 같은 a의 원소와 b의 원소를 원하는 만큼 swap할 수 있다.

max(a1,a2,…,an)⋅max(b1,b2,…,bn) 이거의 최솟값을 구하는 게 문제다.

 

1부터 n까지 순회하면서 각 ai, bi에 대해서 ai>=bi가 되게 swap작업을 해준다.

 

그 후 수열 a와 수열 b를 내림차순으로 정렬한 뒤, 맨 앞 원소들끼리 곱해주면 된다.

 

왜 이렇게 되는지는 조금 생각해보면 알 수 있다.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n;

void solve() {
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < n; i++) cin >> b[i];
    for (ll i = 0; i < n; i++) {
        if (a[i] < b[i]) swap(a[i], b[i]);
    }
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end(), greater<>());
    cout << a[0] * b[0] << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; cin >> tc;
    while (tc--) solve();
    return 0;
}

 

B.

수열이 주어진다. 다음 행위를 x번 하여 수열의 모든 수가 같아지게 만들어야 한다. x의 최솟값을 구하는 문제이다.

 

그 수열의 연속된 부분수열을 선택한다. (길이가 짝수인)

그런 뒤, 그 부분수열의 앞의 반을 뒤의 반으로 바꾼다.

(예를 들어, 1 2 3 4 5 6이라는 수열이 있다고 하자. 그럼 만약 구간 3~6을 선택한 후 위의 행위를 하면 1 2 5 6 5 6이 된다.)

 

잘 관찰해보면, 뒤에서부터 보면서 앞 뒤 원소가 다르면 바로 뒤의 값으로 덮는 작업을 해줘야 한다는 것을 알 수 있다.

만약, 바로 작업하지 않고 나중에 하게 된다면 작업 횟수가 늘어날 수밖에 없음을 알 수 있다.

 

암튼 그렇게 작업을 하다보면 뒤에서부터 원소가 같은 길이가 2배씩 되는 것을 알 수 있다.

이를 잘 구현해보자.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n;

void solve() {
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll same = 1; //끝에서부터 똑같은 숫자의 개수
    ll ans = 0;
    ll x = a[n - 1];
    for (ll i = n - 1; i >= 1;) {
        if (a[i] != a[i - 1]) {
            ans++;
            i -= same;
            if (i >= 0) a[i] = x;
            same *= 2;
        }
        else {
            same++;
            i--;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; cin >> tc;
    while (tc--) solve();
    return 0;
}

 

C.

테스트 케이스(n==4인 경우)에 함정이 있는 문제이다. 그러므로 n==4가 아닌 경우로 먼저 풀겠다...

오늘 같이 풀었던 사람들 모두 이것 때문에 한 번 이상씩 틀렸다. 암튼 n==4인 경우는 끝에서 다시 얘기하자.

 

n과 k가 주어진다. (n은 2의 제곱수로만 주어진다.)

우리는 0~n-1을 2개씩 짝지어야 한다.

2개씩 짝지어서 &연산을 진행시킨다. &연산의 결괏값의 합이 k가 되게 짝지어주는 문제이다.

 

설명의 편의를 위해 n==8일 때를 보자.

일단 기본적으로 아래와 같이 짝을 지으면 합이 0이 나온다는 사실을 기억하자!

즉, k가 0인 경우는 위처럼 짝지으면 된다.

 

그럼 k가 1인 경우는?

k를 n-1과 짝지어보자. 그럼 &연산의 결과는 k가 된다! 그렇다면 위 사진에서의 k, n-1의 짝을 제외하고는 위 사진 그대로 짝지어주자. 그럼 그 쌍들의 &연산 결괏값은 0이니까 아직도 k가 유지된다.

그렇다면 000과 기존k의 짝만 남는다. 이건 &연산해도 당연히 0이니까 k값이 유지된다.

 

k가 2,3,4,5,6인 경우도 위의 방식대로 하면 된다.

 

k가 7인 경우는?

테스트 케이스에 낚여서 k==n-1이면 안 된다고 생각할 수 있다. 그치만 조금 잘 생각해보면 이 경우에도 가능함을 알 수 있다.

 

n-2와 n-1을 짝지어준다. 두 개를 &연산 해주면 k-1이 나오는 것을 알 수 있다. 그렇다면 우리는 1이 더 필요하다.

 

1과 3을 짝지어준다. 두 개를 &연산 해주면 1이 나온다. 이제 총합이 k가 되었으니 남은 숫자들은 아까처럼 잘 짝지어주자!

(n이 4인 경우에는 되지 않음을 알 수 있다. 이 경우는 예외처리를 해주자!)

 

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n, k;

void solve() {
    cin >> n >> k;
    if (k == n - 1) {
        if (n == 4) {//n이 4인 경우 예외처리
            cout << -1 << endl;
            return;
        }
        cout << 0 << ' ' << n - 4 << endl;
        cout << 1 << ' ' << 3 << endl;
        cout << n - 2 << ' ' << n - 1 << endl;
        for (ll i = 0; i < n / 2; i++) {
            if (i == 0 || i == 1 || i == 3) continue;
            else cout << i << ' ' << n - 1 - i << endl;
        }
        return;
    }
    if (k == 0) {//k가 0인 경우
        for (ll i = 0; i < n / 2; i++) {
            cout << i << ' ' << n - 1 - i << endl;
        }
        return;
    }

    //k가 1~(n-2)인 경우
    ll tmp; //k의 짝궁을 tmp라 하자.
    if (k >= n / 2) tmp = n - 1 - k;
    else tmp = n - 1 - k;
    cout << 0 << ' ' << tmp << endl; //0과 k의 짝꿍
    cout << k << ' ' << n - 1 << endl; //k와 n-1  
    for (ll i = 0; i < n / 2; i++) {
        if (i == 0 || i == tmp || i == k || i == n - 1) continue;
        else cout << i << ' ' << n - 1 - i << endl;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int tc = 1; cin >> tc;
    while (tc--) solve();
    return 0;
}

 

 

앞으로도 떡상하자~~~~~~~~~~~~~

코포의 맛... 알아버렸다.