Codeforces Educational #120

A. Construct a Rectangle

Problem - A - Codeforces

Problem - A - Codeforces

세 막대 \(a, b, c\)가 주어진다.

이 중 하나의 막대를 쪼개 두 개의 막대로 만든다.

막대 네 개로 직사각형을 만들 수 있으면 YES, 없으면 NO이다.

 

WLOG, 막대 \(c\)를 쪼갠다고 가정하자.

\(c\)를 쪼개어 얻은 막대 두 개를 각각 \(p, q\)라고 하자.

 

다음과 같이 경우를 나눌 수 있다.

1) \(p\)와 \(q\)가 마주보는 경우: \(c \% 2 = 0\) and \(a = b\)

2) \(p\)와 \(q\)가 이웃한 경우: \(a + b = c\)

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        if ((a%2 == 0 && b == c || a == b + c)
            || (b%2 == 0 && a == c || b == a + c)
            || (c%2 == 0 && a == b || c == a + b)) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
    return 0;
}

 

 

B. Berland Music

Problem - B - Codeforces

Problem - B - Codeforces

음악 \(n\)개에 대한 선호도가 순열 \(p\)로 주어진다.

모든 노래를 한번씩 듣고 좋아요 또는 싫어요 버튼을 누른다.

이를 기반으로 새로운 선호도 \(q\)를 만든다.

 

새로운 선호도 \(q\)는 다음 조건을 만족해야 한다.

1) \(q\) 역시 순열을 이룬다.

2) 좋아요를 받은 노래는 싫어요를 받은 노래보다 항상 선호도가 높다.

 

\(\displaystyle \sum_{i=1}^{n} {|p_i - q_i|}\)의 값이 최소가 되는 순열 \(q\)를 출력해야한다.

 

싫어요 버튼을 누른 횟수를 \(k\)라고 하자.

싫어요를 받은 노래들의 선호도 \(a\)는 \(1\) ~ \(k\)로 이루어진 순열이고

좋아요를 받은 노래들의 선호도 \(b\)는 \(k+1\) ~ \(n\)로 이루어진 순열다.

 

\(a, b\)를 각각 오름차순으로 정렬하고 숫자도 오름차순으로 배정하면 답을 구할 수 있다.

이는 다음과 같은 방법으로 증명할 수 있다.

\( |d_1 - 1| + |d_2 - 2| + \dots + |d_k - k| \)가 최적해이고

\(i < j\)이면서 \(d_i \gt d_j\)인 \(i, j\)가 존재한다고 가정하자. (inversion)

\( |d_i - i| + |d_j - j| \ge |d_i - j| + |d_j - i| \)이므로 \(d_i , d_j\)를 swap해도 최적해를 증가시키지 않는다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        string s; cin >> s;
        
        vector<pii> zero, one;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                one.push_back({p[i], i});
            }
            else {
                zero.push_back({p[i], i});
            }
        }
        sort(zero.begin(), zero.end());
        sort(one.begin(), one.end());
        int cur = 0;
        for (auto [x, y]: zero) {
            p[y] = ++cur;
        }
        for (auto [x, y]: one) {
            p[y] = ++cur;
        }
        for (int i: p) {
            cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

 

 

C. Set or Decrease

Problem - C - Codeforces

Problem - C - Codeforces

길이 \(n\)의 배열 \(a\)와 정수 \(k\)가 주어진다.

 

step 마다 다음 두 가지 동작 중 하나를 선택할 수 있다.

1) 어떤 인덱스 \(i\)를 선택하고 \(a_i\)의 값을 1 감소시킨다. (\(a_i = a_i - 1\))

2) 두 인덱스 \(i, j\)를 선택하고 \(a_i\)의 값을 \(a_j\)로 만든다. (\(a_i = a_j\))

 

\(\displaystyle \sum_{i=1}^{n} {a_i} \le k \)가 성립하기 위해 최소 몇 번의 step이 필요한지 구하는 문제이다.

 

배열 \(a\)를 내림차순으로 정렬하고, 다음의 순서로 step을 수행한다.

1. \(a_n\)을 \(x\)만큼 감소시킨다. \( \Rightarrow x\)번

2. 조건을 만족할 때까지 \(a_i = a_n  (1 \le i \lt n) \)을 수행한다. \( \rightarrow i\)번

\( \Rightarrow x+i\)번

 

이때 \(x\)는 \(i\)에 의해 결정된다.

\(i * (a_n - x) + \sum_{p = i+1}^{n-1}{a_p} + (a_n - x) \le k \)
\(\Rightarrow x \ge a_n - \displaystyle \frac{k - \sum_{p = i+1}^{n-1}{a_p}}{i+1} \)

\(\Rightarrow x = \max(0, a_n - \displaystyle \big\lfloor \frac{k - \sum_{p = i+1}^{n-1}{a_p}}{i+1} \big\rfloor ) \)

 

주의: 음수 나눗셈

\(a = bq + r (a < 0) \Rightarrow r \le 0\)

\(\therefore \text{ if } bq > a \text{ then } q = q - 1\) 

 

답은 \(\displaystyle \min_{0 \le i \lt n}(i + x)\)이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> v(n);
        for (ll& i: v) cin >> i;
        sort(v.begin(), v.end(), greater<ll>());
 
        if (n == 1) {
            cout << max(0LL, v[0] - k) << '\n';
            continue;
        }
        ll mn = v.back();
        ll ans = __LONG_LONG_MAX__;
        partial_sum(v.begin(), v.end(), v.begin());
        for (int i = -1; i < n-1; i++) {
            ll psum = v[n-2] - (i == -1 ? 0 : v[i]);
            ll q = (k - psum) / (i + 2);
            if (q * (i + 2) > k - psum) q--;
            ll x = max(0LL, mn - q);
            ans = min(ans, x+i+1);
        }
        cout << ans << '\n';
    }
    return 0;
}

 

 

D. Shuffle

Problem - D - Codeforces

Problem - D - Codeforces

정수 \(n, k\), 길이 \(n\)의 binary string \(s\)가 주어진다.

\(1\)을 정확히 \(k\)개 포함하는 substring을 셔플하여 만들 수 있는 서로 다른 string의 개수를 구하는 문제이다.

 

포함-배제와 달리 처음부터 중복되는 케이스를 만들지 않는 방법을 사용한다.

셔플 후 달라지는 문자들 중 첫번째 문자 \(i\)와 마지막 문자 \(j\)로 경우를 나눈다. (중복 발생 X)

 

다음 사항을 주의해야 한다.

1) \(s\)에 포함된 \(1\)의 개수가 \(k\) 미만인 경우

2) \(i\)와 \(j\) 사이에 포함된 \(1\)의 개수가 \(k\) 초과인 경우

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const ll MOD = 998244353;
const int MAX = 5000;
int dp[MAX+1][MAX+1];
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n, k; string s;
    cin >> n >> k >> s;
 
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        if (i) v[i] = v[i-1];
        if (s[i] == '1') v[i]++;
    }
 
    ll ans = 1;
    if (v.back() < k) {
        cout << ans;
        return 0;
    }
    for (int i = 0; i <= MAX; i++) {
        dp[i][0] = dp[i][i] = 1;
    }
    for (int i = 1; i <= MAX; i++) {
        for (int j = 1; j < i; j++) {
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % MOD;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int one = v[j] - (i ? v[i-1] : 0);
            int zero = j - i + 1 - one;
            if (one > k) continue;
            if (s[i] == '1') zero--;
            else one--;
            if (s[j] == '1') zero--;
            else one--;
            if (one >= 0 && zero >= 0) {
                ans += dp[one+zero][one];
                ans %= MOD;
            }
        }
    }
    cout << ans;    
    return 0;
}