Educational Codeforces Round 88

A - Berland Poker

Problem - A - Codeforces

\(n\)개의 카드가 있고, 그 중 \(m\)개의 카드는 조커이다. \(k\)명의 플레이어가 게임에 참가한다.

 

각각의 플레이어는 \(\frac nk\)개의 카드를 가져가게 된다.

조커를 가장 많이 가져간 사람이 이기고, (본인 조커 개수 - 나머지 사람들 중 가장 조커가 많은 사람의 조커 개수) 만큼의 점수를 받는다.

 

\(n,m,k\)가 주어졌을 때, 나올 수 있는 최대 점수를 구해야 한다.

 

한 사람이 가져갈 수 있는 조커의 개수의 최대값은 \(min(\frac nk, m)\)이다.

남은 사람들이 남은 조커를 최대한 고르게 가져갔을 때 가져갈 수 있는 조커의 최대값을 계산해서 빼면 된다.

 

#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--)
    {
        int n, m, k; cin >> n >> m >> k;
        int wn = min(n / k, m);
        int lo = (m - wn) / (k - 1);
        if ((m - wn) % (k - 1)) lo++;
 
        cout << wn - lo << '\n';
    }
}

---

B - New Theatre Square

Problem - B - Codeforces

\(n \times m\) 크기의 격자가 있다. 이 격자는 검정색 또는 하얀색으로 칠해져 있다.

두 가지 타일을 이용해 격자의 하얀 부분을 모두 덮어야 하는데,

\(x\)원을 소모해 \(1 \times 1\)크기의 타일을 사용하거나

\(y\)원을 소모해 \(1 \times 2\)크기의 타일을 사용할 수 있다.

단, \(1 \times 2\)크기의 타일은 회전할 수 없다.

 

하얀색으로 칠해진 부분을 모두 타일로 덮는데 필요한 비용의 최소값을 구해야 한다.

 

먼저 타일을 회전할 수 없기 때문에, 문제를 각 행에 대해서 독립적으로 풀 수 있다는 사실을 알 수 있다.

 

먼저 \(y\)가 \(2x\)보다 크다면, 하얀 부분을 모두 \(1 \times 1\)크기의 타일로 채우는게 최적이다.

그렇지 않다면 최대한 \(1 \times 2\)크기의 타일로 채우고 나머지를 \(1 \times 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; }
 
int n, m, x, y;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m >> x >> y;
        y = min(y, 2 * x);
 
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            string board; cin >> board;
 
            int cnt = 0;
            for (int j = 0; j < m; j++)
            {
                if (board[j] == '.') cnt++;
                else
                {
                    ans += cnt / 2 * y + cnt % 2 * x;
                    cnt = 0;
                }
            }
 
            ans += cnt / 2 * y + cnt % 2 * x;
        }
 
        cout << ans << '\n';
    }
}

---

C - Mixing Water

Problem - C - Codeforces

온도 \(h\)인 뜨거운 물과 온도 \(c\)인 차가운 물이 있다.

 

이 물들을 다음과 같은 연산으로 온도 \(t\)에 최대한 가깝게 만드려고 한다.

 

1. 홀수번째에는 뜨거운 물을 한 컵 섞는다.

2. 짝수번째에는 차가운 물을 한 컵 섞는다.

 

온도 \(t\)에 가장 가까워졌을 때의 최소 연산 횟수를 구해야 한다.

 

먼저 \(t \le \frac{h+c}{2}\)라면, 2번이 무조건 답임을 알 수 있다.

그렇지 않다면, 답은 홀수이다.

 

답이 \(X\)라고 했을 때, \(X=2x+1\)라고 하자.

\(\frac{h+(h+c)x}{2x+1} = t\)라는 식을 이끌어 낼 수 있고, 식을 정리하면 해를 \(O(1)\)에 구할 수 있다.

\(x\)가 정수가 아닐 수 있으므로, \(floor(x), ceil(x)\)중 계산결과가 \(t\)에 가까운 값을 취하면 된다.

 

#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 n, m, x, y;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        ll h, c, t; cin >> h >> c >> t;
        if (h + c >= t * 2)
        {
            cout << "2\n";
            continue;
        }
 
        ll cnt = (t - h) / (h + c - 2 * t) + 1;
 
        ll v1 = (t * (cnt * 2 + 1) - (h + (h + c) * cnt)) * ((cnt - 1) * 2 + 1);
        ll v2 = (h + (h + c) * (cnt - 1) - t * ((cnt - 1) * 2 + 1)) * (cnt * 2 + 1);
 
        if (v1 < v2) cout << cnt * 2 + 1 << '\n';
        else cout << cnt * 2 - 1 << '\n';
    }
}

---

D - Yet Another Yet Another Task

Problem - D - Codeforces

\(n\)개의 수로 이루어진 수열 \(a\)가 있다.

\(a\)의 어떤 구간 \([l,r]\)를 선택하고, 그 구간에서 가장 큰 수 하나를 제거 했을 때의 부분합의 최대값을 알아내야 한다.

 

\(-30 \le a_i \le 30\)이므로, 선택한 구간의 최대값이 \(0 \le x \le 30\)인 모든 경우에 대해 각각 부분합의 최대값을 구하면 된다.

DP를 이용해 수열의 부분합의 최대값을 \(O(n)\)에 구할 수 있음을 이용하자.

 

#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 = 100001;
 
int n;
int a[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
 
    int ans = 0;
    for (int mx = 0; mx <= 30; mx++)
    {
        bool hasVal = false;
        int curSum = 0;
 
        for (int i = 0; i < n; i++)
        {
            if (a[i] > mx)
            {
                hasVal = false;
                curSum = 0;
                continue;
            }
 
            if (a[i] == mx) hasVal = true;
 
            if (curSum < 0) curSum = 0;
            curSum += a[i];
 
            if (hasVal) ans = max(ans, curSum - mx);
        }
    }
 
    cout << ans;
}

---

E - Modular Stability

Problem - E - Codeforces

정수 \(n, k\)가 주어진다.

 

다음 조건을 만족하는 수열의 개수를 알아내야 한다.

 

1. 수열의 길이는 \(k\)이고, \(1 \le a_1 \lt a_2 \lt \cdots \lt a_k \le n\)을 만족한다.

2. 수열의 모든 순열에 대해, \((((x \bmod a_1) \bmod a_2) \dots \bmod a_{k-1}) \bmod a_k\)의 값이 모두 같다.

 

먼저, \(a_1 = 1\)이라면 뒤에 나오는 수가 무엇이든 상관없이 항상 위의 조건을 만족한다.

이를 일반적으로 확장해보면, \(a_x\) (\(x > 1\))가 모두 \(a_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; }
 
const ll MOD = 998244353;
 
ll fac[500001];
ll mpow(ll a, ll n)
{
    if (n == 0) return 1;
    ll res = mpow(a, n / 2);
    res = res * res % MOD;
    if (n % 2) res = res * a % MOD;
    return res;
}
 
ll ncr(ll n, ll r)
{
    return fac[n] * mpow(fac[r], MOD - 2) % MOD * mpow(fac[n - r], MOD - 2) % MOD;
}
 
ll n, k;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    fac[0] = 1;
    for (ll i = 1; i <= 500000; i++)
        fac[i] = fac[i - 1] * i % MOD;
 
    ll ans = 0;
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        if (n / i - 1 < k - 1) continue;
        ans += ncr(n / i - 1, k - 1);
        ans %= MOD;
    }
 
    cout << ans;
}

---

F - RC Kaboom Show

Problem - F - Codeforces

추가 예정