Educational Codeforces Round 85

A - Level Statistics

Problem - A - Codeforces

\(n\)개의 게임 플레이 기록이 시간 순으로 주어진다.

 

이 기록은 스테이지를 플레이한 사람 수 \(p_i\)와 클리어한 사람 수 \(c_i\)로 이루어져있는데,

누군가 게임을 플레이 했을 때, 스테이지를 클리어 했다면 \(p_i\)와 \(c_i\)가 동시에 1씩 증가하고,

그렇지 않았다면 \(p_i\)만 1 증가하게 된다.

 

이 게임 플레이 기록에 모순이 있는지 여부를 알아내야 한다.

 

\(p_i > p_{i+1}\)이거나, \(c_i > c_{i+1}\)이거나, \(p_{i+1}-p_i < c_{i+1}-c_i\)인 경우가 존재한다면 이 기록에는 모순이 있다.

 

#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; cin >> n;
 
        bool ans = true;
        int p, c; cin >> p >> c;
 
        if (p < c) ans = false;
        for (int i = 1; i < n; i++)
        {
            int tp, tc; cin >> tp >> tc;
            if (p > tp || c > tc) ans = false;
            if (tp - p < tc - c) ans = false;
 
            p = tp, c = tc;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Middle Class

Problem - B - Codeforces

\(n\)명의 사람들이 있다. 이 사람들은 각각 \(a_i\)만큼의 돈을 가지고 있다.

 

정부는 어떤 사람이 \(x\)이상의 돈을 가지고 있으면 부유하다고 생각한다.

부유한 사람들의 수를 늘리기 위해, 정부는 임의의 사람들을 고른 후에 그 사람들이 가진 돈을 전부 몰수 한 후 똑같이 나눠주려고 한다.

 

이런 개혁 이후 가능한 부유한 사람의 수의 최대값을 알아내야 한다.

 

당연하게도, 돈이 많은 사람일수록 개혁에 포함시키는게 유리하다는 것을 알 수 있다.

\(a_i\)를 내림차순으로 정렬 한 다음, 가장 돈이 많은 사람 부터 차례로 개혁에 포함시킨다고 하자.

돈을 재분배 했을 때, 모든 사람들의 돈이 \(x\) 이상이 되는 사람 수의 최대값이 답이다.

 

#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 n, x;
ll a[100001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
 
        ll ans = 0;
        ll sum = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            sum += a[i];
            if (sum / (n - i) >= x) ans = n - i;
        }
 
        cout << ans << '\n';
    }
}

---

C - Circle of Monsters

Problem - C - Codeforces

\(n\)마리의 몬스터를 토벌하려고 한다.

 

이 몬스터는 원형으로 서 있고, 시계방향으로 \(1\)번부터 \(n\)번까지 번호가 매겨져 있다.

\(i\)번째 몬스터는 \(a_i\)만큼의 체력을 갖고 있다.

 

이 몬스터를 토벌하려면 총으로 쏴야 하는데, 한 발 쏠 때마다 체력이 1씩 깎이게 된다.

그렇게 어떤 몬스터가 체력이 0이하가 된다면, 폭발하게 된다.

폭발하면서 본인의 바로 시계방향에 있는 적에게 \(b_i\)만큼의 대미지를 넣는다.

 

이 때, 몬스터를 모두 죽이기 위한 총으로 쏴야하는 최소 횟수를 구해야 한다.

 

먼저, \(b_i\)가 \(a_{i+1}\)보다 크면 의미가 없음을 알 수 있다.

모든 \(b_i\)를 \(min(b_i, a_{i+1})\)로 바꿔주자.

 

그러고 나면 모든 몬스터가 옆의 폭발 대미지를 입는다고 할 때, 필요한 총알의 수는 \(\sum_{i=1}^n (a_i-b_i)\)임을 알 수 있다.

다만 맨 처음으로 쏘는 몬스터는 폭발 대미지의 도움 없이 전부 총알을 이용해서 대미지를 입혀야 한다.

 

따라서 답은 \(\sum_{i=1}^n (a_i-b_i) + min_{i=1}^n b_i\)이다.

 

#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;
pll a[300001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i].first >> a[i].second;
 
        ll ans = 0;
        ll min_b = 1e18;
 
        for (int i = 0; i < n; i++)
        {
            if (a[i].second > a[(i + 1) % n].first)
                a[i].second = a[(i + 1) % n].first;
 
            ans += a[i].first - a[i].second;
            min_b = min(min_b, a[i].second);
        }
 
        cout << ans + min_b << '\n';
    }
}

---

D - Minimum Euler Cycle

Problem - D - Codeforces

\(n\)개의 정점으로 이루어진 완전 그래프가 있다.

모든 정점 \(u \ne v\)에 대하여 간선 \(u,v\)와 \(v,u\)가 존재한다.

 

이 모든 간선들을 한번씩 지나는 회로를 만드려고 하는데,

방문하는 정점을 차례대로 출력 했을 때 가장 사전순으로 앞서는 것을 알아내야 한다.

 

이 회로가 매우 길어질 수 있으니, \([l, r]\) 범위만큼만 출력하면 된다.

 

관찰을 잘 해보면, 답의 규칙을 알 수 있다.

 

ex) \(n=5\) 일 때

1-2-1-3-1-4-1-5 / 2-3-2-4-2-5 / 3-4-3-5 / 4-5 / 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 ans_2[4] = { 0,1,2,1 };
vector <ll> vec;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n, l, r; cin >> n >> l >> r;
        if (n == 2)
        {
            for (int i = l; i <= r; i++) cout << ans_2[i] << ' ';
            cout << '\n';
            continue;
        }
 
        vec.clear();        
        ll tmp = 0;
        for (ll k = n - 1; k > 0; k--)
        {
            tmp += k * 2;
            vec.push_back(tmp);
        }
        vec.push_back(tmp + 1);
 
        for (ll i = l; i <= r; i++)
        {
            int idx = lower_bound(vec.begin(), vec.end(), i) - vec.begin();
            if (idx != vec.size() - 1)
            {
                ll ci = i - 1;
                if (idx) ci -= vec[idx - 1];
 
                if (ci % 2 == 0) cout << idx + 1 << ' ';
                else cout << ci / 2 + idx + 2 << ' ';
            }
            else cout << "1 ";
        }
        cout << '\n';
    }
}

---

E - Divisor Paths

Problem - E - Codeforces

양의 정수 \(D\)가 주어진다.

 

다음과 같은 규칙으로 그래프를 만든다.

 

1. 모든 정점은 \(D\)의 약수이다.

2. 두 정점 \(x\)와 \(y\) \((x \gt y)\)는 \(x\)가 \(y\)로 나눠떨어지고, \(\frac{x}{y}\)가 소수일 때 방향성 없는 간선을 가진다.

3. 두 정점의 가중치는 \(x\)의 약수이면서 \(y\)의 약수가 아닌 수들의 개수이다.

 

각 \(q\)개의 쿼리에 대해, 정점 \(v, u\)가 주어진다.

두 정점 사이의 최단 경로의 개수를 \(998244353\)로 나눈 나머지를 각각 출력하면 된다.

 

관찰을 통해 다음과 같은 사실을 알아낼 수 있다.

 

3번 조건을 다시 말하면, 두 정점의 가중치는 \(x\)의 약수의 개수 - \(y\)의 약수의 개수와 같다.

따라서 어떤 두 정점 \(v, u\)사이의 최단 경로는 \(v\)에서 소수를 곱하거나 나누면서 생기는 약수의 변화량을 최소화한 값이라는 사실을 알 수 있다.

 

따라서 만약 두 정점 \(x\)와 \(y\) \((x \gt y)\)에 대하여 \(x\)가 \(y\)로 나눠 떨어진다면,
최단 경로는 \(x\)를 \(y\)가 될때까지 소수로 나누는 수들을 방문하는 경로가 될 것이고,
그 개수는 \(\frac{x}{y}\)를 소인수 분해 했을 때 나오는 소수들을 나열했을 때 서로 다른 순열의 수와 같다는 사실을 알 수 있다.

이 값을 \(f(\frac{x}{y})\)라고 하자. 
확장해서 \(x\)가 \(y\)로 나눠 떨어지지 않는다면, 
\(g = gcd(x,y)\)라고 할 때 \(f(\frac{x}{g}) \times f(\frac{y}{g})\)가 답이 된다는 사실도 알 수 있다.

 

이대로 계산해도 되겠지만, 쿼리가 많기 때문에 전처리를 할 필요가 있다.

위에서 나온 \(\frac{x}{y}\)도 역시 \(D\)의 약수이기 때문에, \(D\)의 약수 \(x\)에 대하여 \(f(x)\)를 미리 구해놓으면 쿼리를 빠르게 처리할 수 있다.

 

#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 d, q;
vector <ll> prm;
ll dp_pow[1000];
 
ll mpow(ll a, ll n)
{
    if (dp_pow[a] != -1) return dp_pow[a];
 
    if (n == 0) return 1;
    ll res = mpow(a, n / 2);
    res = res * res % MOD;
    if (n % 2) res = res * a % MOD;
    return dp_pow[a] = res;
}
 
map <ll, ll> mp;
ll dist(ll n)
{
    if (mp.count(n)) return mp[n];
    ll tn = n;
 
    ll all_cnt = 0;
    vector <ll> v;
    for (ll p : prm)
    {
        ll cnt = 0;
        while (n % p == 0)
        {
            n /= p;
            cnt++;
        }
 
        all_cnt += cnt;
        if (cnt) v.push_back(cnt);
    }
 
    ll res = 1;
    for (ll i = 1; i <= all_cnt; i++)
    {
        res *= i;
        res %= MOD;
    }
 
    for (ll cnt : v)
    {
        for (ll i = 1; i <= cnt; i++)
        {
            res *= mpow(i, MOD - 2);
            res %= MOD;
        }
    }
 
    return mp[tn] = res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(dp_pow, -1, sizeof dp_pow);
    cin >> d >> q;
    ll cd = d;
    for (ll i = 2; i * i <= d; i++)
    {
        ll cnt = 0;
        while (cd % i == 0)
        {
            cd /= i;
            cnt++;
        }
 
        if (cnt) prm.push_back(i);
    }
 
    if (cd != 1) prm.push_back(cd);
 
    while (q--)
    {
        ll u, v; cin >> u >> v;
        if (u == v)
        {
            cout << "1\n";
            continue;
        }
 
        ll g = gcd(u, v);
 
        ll ans = (dist(u / g) * dist(v / g)) % MOD;
        cout << ans << '\n';
    }
}

---

F - Strange Function

Problem - F - Codeforces

추가 예정

---

G - Substring Search

Problem - G - Codeforces

추가 예정