Educational Codeforces Round 92

A - LCM Problem

Problem - A - Codeforces

정수 \(l, r\)이 주어진다.

\(l \le x \lt y \le r\)을 만족하면서, \(l \le LCM(x,y) \le r\)을 만족하는 \(x,y\)가 존재하는지 알아내고, 존재한다면 출력해야 한다.

서로 다른 \(x,y\)에 대해서, \(LCM(x,y)\)가 가장 작아지는 경우는 \(y = 2x\)인 경우이다.

 

\(2l \le r\)이면 \(l, 2l\)을 출력하면 되고, 그렇지 않다면 불가능하다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned 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 a, b; cin >> a >> b;
        if (a * 2 > b) cout << "-1 -1\n";
        else cout << a << ' ' << a * 2 << '\n';
    }
}

---

B - Array Walk

Problem - B - Codeforces

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

이 배열의 1번 인덱스부터 시작해 왼쪽이나 오른쪽으로 이동하는데, 이동한 인덱스에 있는 수를 점수에 더할 수 있다.

총 \(k\)번 이동할 수 있는데, 왼쪽으로는 최대 \(z\)번만 이동할 수 있고, 연속해서 2번 왼쪽으로 이동할 수는 없다.

 

얻을 수 있는 점수의 최대값을 알아내야 한다.

 

왼쪽으로 이동하는 연산을 해서 이득이 되려면 큰 수를 여러번 밟아야 하므로, 한번 왼쪽으로 이동하는 연산을 사용했다면 그 자리에서 가능한 많이 좌우로 진동해야 한다.

 

가능한 모든 자리에서 최대한 많이 진동했을 때 점수를 각각 구한다음, 그 중 최대값이 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned 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, z;
ll a[100001];
ll psum[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k >> z;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            psum[i] = psum[i - 1] + a[i];
        }
 
        ll ans = 0;
 
        for (ll i = 2; i <= k + 1; i++)
        {
            ll res = psum[i];
            ll rv = min(z * 2, k - (i - 1));
            ll rm = k - (i - 1) - rv;
 
            res += (a[i] + a[i - 1]) * (rv / 2);
            if (rv % 2) res += a[i - 1];
 
            if (rv % 2) res += psum[i + rm - 1] - psum[i - 1];
            else res += psum[i + rm] - psum[i];
 
            ans = max(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

C - Good String

Problem - C - Codeforces

숫자로 이루어진 문자열 \(s\)가 주어진다.

이 문자열을 왼쪽으로 한칸 쉬프트했을 때와 오른쪽으로 한칸 쉬프트했을 때 결과가 똑같도록 문자 몇개를 지우려고 한다.

지워야 하는 문자의 최소 개수를 구해야 한다.

 

좌우로 쉬프트했을 때 결과가 같기위해서는, 문자열이 AAAA..AA 형태거나 ABAB...AB 형태여야 함을 알 수 있다.

가능한 \(10^2\)가지에 대해 모두 계산해보면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned 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; }
 
string s;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> s;
 
        int ans = 987654321;
        for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++)
        {
            int res = 0;
            bool b = 0;
            for (char c : s)
            {
                if (!b && c - '0' == i || b && c - '0' == j)
                {
                    b = !b;
                    continue;
                }
 
                res++;
            }
 
            if (i != j && b) res++;
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

D - Segment Intersections

Problem - D - Codeforces

서로 다른 두 구간 \(a,b\)가 \(n\)쌍씩 있다.

한번의 연산으로, 하나의 구간을 선택해 왼쪽이나 오른쪽으로 1 확장시킬 수 있다.

모든 구간쌍에 대해, \(a,b\)가 겹치는 길이의 합이 \(k\)이상이 되기 위해 해야하는 연산의 최소 횟수를 구해야 한다.

 

먼저, 모든 구간을 다 사용하는것보다 일부만 사용하는것이 더 이득일 수 있음을 예제에서 알 수 있다.

또, 몇 개의 구간만을 사용하겠다고 결정했다면 최대한 고르게 구간을 확장시키는것이 가장 이득임을 알 수 있다.

 

그러면 구간을 최소 1개에서 최대 \(n\)개까지 사용했을 때 각각에 대해, 필요한 연산 수를 \(O(1)\)에 계산할 수 있게 된다.

모든 경우에 대해 계산한다음 최소값을 구하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned 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 l1, r1, l2, r2;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cin >> l1 >> r1 >> l2 >> r2;
 
        if (l1 > l2)
        {
            swap(l1, l2);
            swap(r1, r2);
        }
 
        ll its = 0;
        if (r1 > l2)
        {
            if (r1 <= r2) its = r1 - l2;
            else its = r2 - l2;
        }
 
        if (its * n >= k)
        {
            cout << "0\n";
            continue;
        }
 
        ll rm = k - its * n;
 
        ll ans = numeric_limits<ll>::max();
        for (int i = 0; i < n; i++) // 쓰지 않을거의 개수
        {
            ll res = 0;
 
            ll inc = rm / (n - i);
            ll irm = rm - inc * (n - i);
 
            if (r1 <= l2)
            {
                res += (l2 - r1) * irm;
            }
 
            ll tmp = min(inc + 1, max(r1, r2) - l1 - its);
            res += tmp * irm;
            res += (inc + 1 - tmp) * 2 * irm;
 
            if (inc)
            {
                if (r1 <= l2)
                {
                    res += (l2 - r1) * (n - i - irm);
                }
 
                ll tmp = min(inc, max(r1, r2) - l1 - its);
                res += tmp * (n - i - irm);
                res += (inc - tmp) * 2 * (n - i - irm);
            }
 
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

E - Calendar Ambiguity

Problem - E - Codeforces

Berland의 한 해는 \(d\)일로 이루어진 \(m\)개의 달로 이루어져 있다.

한 주는 \(w\)일이다. 한 해의 첫번째 날은 항상 한 주의 첫번째 날이므로, 한 해의 마지막 주는 \(w\)일이 아닐 수 있다.

 

\(x\)번째 달의 \(y\)번째 날과, \(y\)번째 달의 \(x\)번째 날의 요일이 같은 순서쌍 \((x,y)\)의 개수를 구해야 한다. ((\(x \lt y\))

 

다음과 같은 식을 만들 수 있다.

 

\((dx + y) \equiv (dy + x) \mod w\)

\((d-1)(y-x) \equiv 0 \mod w\)

 

\(d-1\)은 상수이므로, 여기에 \(y-x\)를 곱했을 때 \(w\)로 나누어지도록 하는 \(y-x\)의 조건을 생각해 보자.

\(g = \gcd(d-1, w)\)라고 했을 때,

\(y-x\)는 \((d-1)/g\)의 배수여야 한다.

 

각 \(y-x\)에 대해 가능한 순서쌍 \((x,y)\)의 수는 \(O(1)\)에 구할 수 있고,

가능한 \(y-x\)가 등차수열을 이루므로 가능한 총 순서쌍도 식을 정리하여 \(O(1)\)에 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned 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 m, d, w;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> m >> d >> w;
        ll g = gcd(d - 1, w);
 
        ll dd = w / g;
 
        if (d == 1)
        {
            cout << "0\n";
            continue;
        }
 
        ll cnt = (min(d, m) - 1) / dd;
        ll ans = min(d, m) * cnt - cnt * (cnt + 1) / 2 * dd;
        cout << ans << '\n';
    }
}

---

F - Bicolored Segments

Problem - F - Codeforces

추가 예정

---

G - Directing Edges

Problem - G - Codeforces

추가 예정