Educational Codeforces Round 86

A - Road To Zero

Problem - A - Codeforces

두 수 \(x, y\)가 주어진다.

 

이 두 수중 하나에 1을 더하거나 빼는 연산을 하는데 \(a\)의 비용이, 둘 다 1을 더하거나 빼는 연산을 하는데 \(b\)의 비용이 든다.

두 수를 모두 0으로 만들기 위한 최소 비용을 구해야 한다.

 

\(b > 2a\) 라면 두번째 연산을 할 필요가 없다.

그렇지 않다면, 두번째 연산을 \(min(a,b)\)번 해서 둘 중 하나를 0으로 만든 다음, 나머지 수에 첫번째 연산을 해서 0으로 만들면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll x, y; cin >> x >> y;
        ll a, b; cin >> a >> b;
 
        if (x > y) swap(x, y);
        ll m = min(x, y);
 
        if (a * 2 > b)
        {
            cout << m * b + (y - m) * a << '\n';
        }
        else
        {
            cout << a * (x + y) << '\n';
        }
    }
}

---

B - Binary Period

Problem - B - Codeforces

 

0과 1로만 이루어진 문자열 \(t\)가 주어지는데, 다음 조건을 만족하는 문자열 \(s\)를 구해야 한다.

1. \(s\)는 0과 1로만 이루어져 있어야 한다.

2. \(s\)의 길이는 \(2\cdot |t|\)를 초과해서는 안된다.

3. \(t\)는 \(s\)의 부분수열이다.

4. \(s\)는 1,2,3번 조건을 만족하는 문자열 중 가장 작은 주기를 가진다.

 

먼저 \(t\)가 0과 1 둘 중 한가지로만 이루어져 있다면, 주기가 1인 문자열 \(t\) 자신이 답이다.

그렇지 않다면, 문자열 "01"을 \(|t|\)회 반복한 문자열은 위의 모든 조건을 만족하면서 주기가 2인 문자열이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
        int cnt[2] = { 0,0 };
        for (auto c : s)
            cnt[c - '0']++;
 
        if (cnt[0] == 0 || cnt[1] == 0) cout << s << '\n';
        else
        {
            for (int i = 0; i < s.size(); i++) cout << "01";
            cout << '\n';
        }
    }
}

---

C - Yet Another Counting Problem

Problem - C - Codeforces

두 정수 \(a,b\)가 주어지고, \(q\)개의 쿼리가 주어진다.

\(i\)번째 쿼리는 \(l_i, r_i\) 2가지 숫자로 이루어져 있는데, 각 쿼리마다 \(l_i \le x \le r_i\)를 만족하는 정수 \(x\)에 대해

\(((x\bmod a)\bmod b) \ne ((x\bmod b)\bmod a\))를 만족하는 수의 개수를 출력해야 한다.

 

위의 부등식의 만족 여부는 \(ab\)의 주기로 반복된다는 것을 알 수 있다.

 

\(a\)와 \(b\)가 최대 \(200\)이므로, \(1\)부터 \(ab\)까지 모든 수에 대해 저 부등식을 만족하는지 미리 계산해 놓자.

그리고 \(1\)부터 \(k\)까지 (\(k \le ab\)) 위의 부등식을 만족하는 수의 개수를 부분합을 이용해 계산해 놓으면,

\(1\)부터 임의의 정수 \(x\)까지 위의 부등식을 만족하는 수의 개수도 \(O(1)\)에 구할 수 있음을 알 수 있다.

이 개수를 \(f(x)\)라고 하자.

 

각 쿼리마다 \(f(r_i) - f(l_i-1)\)을 구해 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll _LCM;
ll psum[40001];
 
ll solve(ll x)
{
    ll res = x / _LCM * psum[_LCM];
    res += psum[x % _LCM];
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll a, b, q; cin >> a >> b >> q;
        if (a > b) swap(a, b);
 
        ll g = gcd(a, b);
        _LCM = a * b / g;
        
        memset(psum, 0, sizeof psum);
        for (ll i = 1; i <= _LCM; i++)
        {
            if (i % a % b != i % b % a) psum[i] = 1;
            psum[i] += psum[i - 1];
        }
 
        vector <ll> ans;
        while (q--)
        {
            ll l, r; cin >> l >> r;
            ans.push_back(solve(r) - solve(l - 1));
        }
 
        for (auto it : ans) cout << it << ' ';
        cout << '\n';
    }
}

---

D - Multiple Testcases

Problem - D - Codeforces

\(n\)개의 수가 있다. 이 수는 모두 \(1\)이상 \(k\)이하이다.

 

이 수들을 몇개씩 묶으려고 하는데, 각 묶음에는 \(1\)이상인 수가 \(c_1\)개 이하, \(2\)이상인 수가 \(c_2\)개 이하, \(\dots\), \(k\)이상인 수가 \(c_k\)개 이하 들어있어야 한다.

 

묶음의 수를 최소화 했을 때의 묶음의 수와, 각 묶음에 들어있는 수를 출력해야 한다.

 

\(1 \le x \le k\)인 모든 \(x\)에 대해, \(x\)이상인 수의 개수를 \(cnt_x\)라고 하자.

그러면 묶음의 수의 하한은 \(max_{1 \le x \le k}(\lceil cnt_x/c_x\rceil)\)임을 알 수 있다.

 

답을 구했으니 수들을 조건에 맞게 적절히 넣으면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int N = 200001;
int n, k;
int m[N];
int c[N];
int cnt[N];
int psum[N];
 
vector <int> ans[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> m[i];
        cnt[m[i]]++;
        psum[m[i]]++;
    }
    for (int i = 1; i <= k; i++) cin >> c[i];
 
    for (int i = k - 1; i >= 1; i--) psum[i] += psum[i + 1];
 
    int mx = 0;
    for (int i = k; i >= 1; i--)
    {
        int res = (psum[i] - 1) / c[i] + 1;
        if (res > mx)
        {
            mx = res;
        }
    }
 
    cout << mx << '\n';
 
    int idx = 0;
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < cnt[i]; j++)
        {
            ans[idx].push_back(i);
            idx = (idx + 1) % mx;
        }
    }
 
    for (int i = 0; i < mx; i++)
    {
        cout << ans[i].size();
        for (auto it : ans[i]) cout << ' ' << it;
        cout << '\n';
    }
}

---

E - Placing Rooks

Problem - E - Codeforces

\(n \times n\)크기의 체스판에 룩을 \(n\)개 놓으려고 한다.

 

모든 칸이 룩에 의해 공격받고 있으면서, \(k\)쌍의 룩이 서로 공격받도록 룩을 놓는 경우의 수를 구해야 한다.

 

조건을 만족하기 위해 룩이 있을 수 있는 위치를 관찰해보자.

 

먼저 모든 칸이 룩에 의해 공격받기 위해서는 모든 행(또는 열)에 적어도 룩이 하나씩 있어야 한다.

동시에 \(k\)쌍이 룩이 공격 받기 위해서는, 룩이 \(n-k\)개의 열(또는 행)에만 존재하면 된다는 사실을 알 수 있다.

 

이 경우의 수를 계산해보자.

룩이 모든 행에 하나씩 있고, 정확히 고정된 \(n-k\)개의 열에 존재하는 경우의 수를 계산해보자.

\((n-k)^n\)라고 쉽게 생각할 수 있지만, 여기에는 \(n-k-1\)개, \(n-k-2\)개, \(\dots\), \(1\)개의 열에만 룩이 존재하는 경우가 포함되어 있고, 이 경우는 문제의 조건에 위배된다.

 

따라서 포함-배제의 원리에 의해

$$\sum_{i=0}^{n-k-1} (-1)^i \cdot (_{n-k}C_{n-k-i}) \cdot (n-k-i)^n$$

이 답이 된다.

 

이 값에 \(n\)개의 열에서 \(n-k\)개를 선택해야 되므로 \(_nC_{n-k}\)를 곱하고,

열과 행을 서로 바꿀 수 있으므로 \(2\)를 곱하면 답이 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const ll MOD = 998244353;
ll n, k;
ll fac[200001];
ll inv_fac[200001];
 
ll mpow(ll n, ll a)
{
    if (a == 0) return 1;
    ll res = mpow(n, a / 2);
    res = res * res % MOD;
    if (a % 2) res = res * n % MOD;
    return res;
}
 
ll ncr(ll n, ll r)
{
    return fac[n] * inv_fac[r] % MOD * inv_fac[n - r] % MOD;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
 
    if (n <= k)
    {
        cout << 0;
        return 0;
    }
 
    if (k == 0)
    {
        ll ans = 1;
        for (ll i = 1; i <= n; i++) ans *= i, ans %= MOD;
        cout << ans;
        return 0;
    }
 
    fac[0] = inv_fac[0] = 1;
    ll tmp = 1, inv_tmp = 1;
    for (ll i = 1; i <= n; i++)
    {
        tmp *= i; tmp %= MOD;
        fac[i] = tmp;
 
        inv_tmp *= mpow(i, MOD - 2); inv_tmp %= MOD;
        inv_fac[i] = inv_tmp;
    }
 
    ll ans = 0;
    for (ll i = 0; i < n - k; i++)
    {
        ll t = n - k - i;
        ll res = ncr(n - k, t) * mpow(t, n) % MOD;
        
        if (i % 2 == 0) ans += res, ans %= MOD;
        else ans += MOD - res, ans %= MOD;
    }
    ans *= ncr(n, k), ans %= MOD;
    ans *= 2, ans %= MOD;
    cout << ans;
}

---

F - Make It Ascending

Problem - F - Codeforces

추가 예정