Educational Codeforces Round 103

A - K-divisible Sum

Problem - A - Codeforces

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

\(n\)길이의 양의 정수 배열 \(a\)를 만드는데, \(a\)의 모든 원소의 합이 \(k\)로 나누어 떨어져야 하고 \(a\)의 원소중 최대값이 최소가 되어야 한다.

 

이 때 \(a\)의 원소의 최대값을 구해야 한다.

 

해설은 생략한다.

 

#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 n, k; cin >> n >> k;
        ll a = (n / k) + (n % k ? 1 : 0);
 
        cout << (k * a - n) / n + ((k * a - n) % n ? 1 : 0) + 1 << '\n';
    }
}

---

B - Inflation

Problem - B - Codeforces

\(n\)길이의 배열 \(p\)가 주어진다.

 

각 인덱스 \(i\)에 대해, \(\sum_{j=1}^{i-1} p[j]  \le \frac {k}{100} \) 을 만족해야 하는데,

이를 위해 임의의 \(p_i\)를 증가시킬 수 있다.

 

위의 조건을 만족하기 위한 총 증가량의 최소값을 구해야 한다.

 

맨 앞원소 (\(p_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 n, k;
ll a[101];
ll p[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            p[i] = a[i] + p[i - 1];
        }
 
        ll ans = 0;
        for (int i = n; i > 1; i--)
        {
            if (a[i] * 100 <= k * (p[i - 1] + ans)) continue;
 
            ll rm = (a[i] * 100 / k + (a[i] * 100 % k ? 1 : 0)) - (p[i - 1] + ans);
            ans += rm;
        }
 
        cout << ans << '\n';
    }
}

---

C - Longest Simple Cycle

Problem - C - Codeforces

\(n\)개의 체인이 있다. 각 체인의 길이는 \(c_i\)이다.

1번째 체인을 제외한 모든 체인의 양 끝은 이전 체인의 임의의 점과 연결되어 있다.

 

이 때, 이 체인에서 만들 수 있는 가장 긴 단순 사이클의 길이를 알아내야 한다.

 

 

\(i\)번째 체인을 사이클을 이루는 마지막 체인이라고 했을 때, 가장 긴 단순 사이클의 길이를 \(y_i\)라고 하자.

 

\(i\)번째 체인의 양 끝이 이전 체인의 같은 점에 연결되어 있다면 \(y_i = c_i + 2\)이고,

그렇지 않다면 \(y_i = c_i+2+y_{i-1}-|a_i-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;
ll c[100001];
ll a[100001];
ll b[100001];
 
ll res[100001];
 
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 >> c[i];
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++)
        {
            cin >> b[i];
            if (a[i] > b[i]) swap(a[i], b[i]);
        }
 
        a[n] = 1, b[n] = c[n - 1];
 
        ll ans = 0;
 
        res[0] = -1e12;
        for (int i = 1; i < n; i++)
        {
            ll tmp = a[i + 1] - 1 + c[i] - b[i + 1] + 2;
            if (a[i] != b[i]) tmp += max(b[i] - a[i], res[i - 1]);
 
            res[i] = tmp;
            ans = max(ans, res[i] + b[i + 1] - a[i + 1]);
        }
 
        cout << ans << '\n';
    }
}

---

D - Journey

Problem - D - Codeforces

\(n+1\)개의 도시가 있다.

이웃한 두 도시는 각각 하나의 일방통행인 길로 연결되어 있다.

한 번 길을 이용하고 나면, 모든 길의 일방통행 방향이 반전된다.

 

모든 도시에서, 길을 통해 이동할 수 있는 서로 다른 도시의 최대 개수를 출력해야 한다.

 

 

각 도시에서 이전 도시로 갈 수 있는 최대 횟수와 다음 도시로 갈 수 있는 최대 횟수를 구한 다음, 둘을 더하면 된다.

 

왼쪽과 오른쪽으로 한번씩 훑으면 이를 각각 \(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; }
 
int n;
string s;
 
int l[300001], r[300001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> s;
 
        for (int i = 0; i < n; i++)
        {
            if (s[i] != 'R')
            {
                r[i] = 0;
                continue;
            }
 
            int cur = 'R';
            int cnt = 0;
 
            int mx = i;
            for (; mx < n; mx++)
            {
                if (s[mx] == cur)
                {
                    cnt++;
                    if (cur == 'R') cur = 'L';
                    else cur = 'R';
                }
                else
                {
                    r[mx] = 0;
                    break;
                }
            }
 
            for (int j = i; j < mx; j++)
            {
                if (s[j] == 'R') r[j] = cnt;
                else r[j] = 0;
 
                cnt--;
            }
 
            i = mx - 1;
        }
 
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] != 'L')
            {
                l[i + 1] = 0;
                continue;
            }
 
            int cur = 'L';
            int cnt = 0;
 
            int mx = i;
            for (; mx >= 0; mx--)
            {
                if (s[mx] == cur)
                {
                    cnt++;
                    if (cur == 'R') cur = 'L';
                    else cur = 'R';
                }
                else
                {
                    l[mx + 1] = 0;
                    break;
                }
            }
 
            for (int j = i; j > mx; j--)
            {
                if (s[j] == 'L') l[j + 1] = cnt;
                else l[j + 1] = 0;
 
                cnt--;
            }
 
            i = mx + 1;
        }
 
        r[n] = 0;
        l[0] = 0;
 
        for (int i = 0; i <= n; i++)
        {
            int res = l[i] + r[i] + 1;
            cout << res << ' ';
        }
 
        cout << '\n';
    }
}

---

E - Pattern Matching

Problem - E - Codeforces

\(n\)개의 패턴과 \(m\)개의 문자열이 주어진다.

패턴과 문자열의 길이는 모두 \(k\)이다.

 

패턴을 재배치 한 다음, 맨 위에 있는 패턴부터 차례로 문자열과 매칭을 시도한다.

각 문자열과 매칭되어야 하는 패턴 \(mt\)이 무엇인지 주어질 때 이것이 가능한지 여부를 알아내고,

가능하다면 재배치한 패턴의 순서를 출력해야 한다.

 

각 문자열에 대해, 매칭되는 패턴의 최대 개수는 \(2^k\)개 임을 알 수 있다.

이 때 이 패턴들은 다음을 모두 만족해야 한다.

 

1. 적어도 하나는 \(p_{mt_i}\)와 일치해야 한다.

2. \(p_{mt_i}\)는 다른 패턴보다 먼저 등장해야 한다.

 

1번 조건은 간단히 확인할 수 있고, 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 n, m, k;
 
string p[100001];
string s[100001];
int mt[100001];
 
int ridx[600001];
 
vector <int> graph[100001];
int in[100001];
vector <int> ans;
 
int getHash(string s)
{
    int ans = 0;
    for (int i = 0; i < k; i++)
    {
        ans *= 27;
        if (s[i] == '_') continue;
        else ans += s[i] - 'a' + 1;
    }
 
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        int idx = getHash(p[i]);
        ridx[idx] = i;
    }
 
    bool hasAns = true;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i] >> mt[i];
 
        bool flag = false;
        vector <int> vec;
 
        for (int bt = 0; bt < (1 << k); bt++)
        {
            string tmp = s[i];
            for (int j = 0; j < k; j++)
            {
                if (bt & (1 << j)) tmp[j] = '_';
            }
 
            int idx = getHash(tmp);
            if (ridx[idx] == 0) continue;
 
            if (ridx[idx] == mt[i]) flag = true;
            else vec.push_back(ridx[idx]);
        }
 
        if (!flag)
        {
            hasAns = false;
            break;
        }
 
        for (int v : vec)
        {
            graph[mt[i]].push_back(v);
            in[v]++;
        }
    }
 
    int cnt = 0;
    queue <int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);
 
    while (!q.empty())
    {
        int v = q.front(); q.pop(); cnt++;
        ans.push_back(v);
 
        for (int nv : graph[v])
            if (--in[nv] == 0) q.push(nv);
    }
 
    if (cnt < n) hasAns = false;
 
    if (!hasAns)
    {
        cout << "NO";
        return 0;
    }
 
    cout << "YES\n";
    for (int v : ans) cout << v << ' ';
}

---

F - Lanterns

Problem - F - Codeforces

추가 예정

---

G - Minimum Difference

Problem - G - Codeforces

추가 예정