Educational Codeforces Round 93

A - Bad Triangle

Problem - A - Codeforces

\(n\)길이의 배열이 \(a\)가 주어진다. 이 배열은 비내림차순으로 정렬되어 있다.

이 배열의 서로 다른 인덱스 \(i,j,k\)를 골라, 변의 길이가 각각 \(a_i, a_j, a_k\)인 삼각형이 존재하지 않도록 만들 수 있는지 여부를 알아내야 한다.

가능하다면, 골라야 하는 인덱스를 출력한다.

 

삼각형의 세 변의 길이를 \(a,b,c\)라고 하고, 그 중 \(c\)가 가장 길다고 가정하자.

그러면 \(c \lt a+b\)여야 삼각형을 만들 수 있다.

다시 말하면 \(c \ge a+b\)이면 삼각형을 만들 수 없으므로,

가장 큰 수 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;
int a[50001];
 
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];
        if (a[0] + a[1] > a[n - 1]) cout << "-1\n";
        else cout << "1 2 " << n << "\n";
    }
}

---

B - Substring Removal Game

Problem - B - Codeforces

이진 문자열 \(s\)가 주어진다. 이 문자열로 두 사람이 게임을 하려고 한다.

자신의 차례인 사람은 문자열에서 연속된 같은 문자를 골라, 문자열에서 삭제할 수 있다.

자신의 점수는 자신의 차례에 삭제한 1의 개수이다.

 

선공이 얻을 수 있는 최대 점수를 알아내야 한다.

 

관찰을 통해, 문자 0을 가져가는 것은 전혀 이득이 될 수 없음을 알 수 있다.

따라서 자신의 차례에 가장 긴 연속된 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; }
 
string s;
vector <int> v;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> s;
        v.clear();
 
        int cnt = 0;
        for (char c : s)
        {
            if (c == '0')
            {
                if (cnt) v.push_back(cnt);
                cnt = 0;
            }
            else cnt++;
        }
 
        v.push_back(cnt);
 
        sort(v.rbegin(), v.rend());
 
        int ans = 0;
        for (int i = 0; i < v.size(); i += 2) ans += v[i];
        cout << ans << '\n';
    }
}

---

C - Good Subarrays

Problem - C - Codeforces

\(n\)길이의 배열이 주어진다. 이 배열은 0 이상 9 이하의 정수로 이루어져 있다.

이 배열의 부분배열을 골랐을 때, 부분 배열의 원소의 합과 부분 배열의 원소의 수가 같다면, 이 부분배열을 좋은 부분배열이라고 한다.

 

배열이 주어졌을 때, 좋은 부분 배열의 개수를 구해야 한다.

 

우선 배열의 부분합을 미리 구해놓고, 이를 \(psum\)이라고 하자.

어떤 부분 배열 \(a[l..r]\)이 좋은 부분 배열이 되기 위해서는 \(psum_r - r = psum_{l-1}-(l-1)\)을 만족해야 한다.

 

모든 인덱스 \(i\)에 대해, \(psum_i - i\)를 계산한다음,

서로 같은 \(psum_i-i\)의 수를 \(x\)라고 했을 때, \(\frac {x(x-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;
int a[100001];
int psum[100001];
 
map <int, int> mp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        string s; cin >> s;
 
        mp.clear();
        for (int i = 1; i <= n; i++)
        {
            a[i] = s[i - 1] - '0';
            psum[i] = psum[i - 1] + a[i];
        }
 
        for (int i = 0; i <= n; i++)
        {
            mp[psum[i] - i]++;
        }
 
        ll ans = 0;
        for (auto it : mp)
        {
            ll c = it.second;
            ans += c * (c - 1) / 2;
        }
 
        cout << ans << '\n';
    }
}

---

D - Colored Rectangles

Problem - D - Codeforces

빨간 막대기가 \(R\)쌍, 초록 막대기가 \(G\)쌍, 파란 막대기가 \(B\)쌍 있다.

서로 다른 색의 막대기 쌍 2개를 골라 직사각형을 만들 수 있다.

 

이 때, 만들 수 있는 직사각형의 넓이의 합의 최대값을 구해야 한다.

 

빨간색과 초록색 막대기를 이용해 직사각형을 만든다고 가정해보자.

관찰을 통해, 현재 남아 있는 빨간색 막대기중 가장 긴 것과, 초록색 막대기중 가장 긴 것을 골라 직사각형을 만드는 것이 무조건 이득임을 알 수 있다.

 

만들 수 있는 직사각형의 종류가 RG, GB, BR로 총 3가지이므로, 막대의 길이를 정렬한다음 간단한 DP로 문제를 해결할 수 있다.

 

#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 R, G, B;
ll r[201], g[201], b[201];
 
ll dp[201][201][201];
ll solve(int ri, int gi, int bi)
{
    ll& ret = dp[ri][gi][bi];
    if (ret != -1) return ret;
 
    ret = 0;
 
    if (ri < R && gi < G)
    {
        ll res = solve(ri + 1, gi + 1, bi) + r[ri] * g[gi];
        ret = max(ret, res);
    }
 
    if (gi < G && bi < B)
    {
        ll res = solve(ri, gi + 1, bi + 1) + g[gi] * b[bi];
        ret = max(ret, res);
    }
 
    if (bi < B && ri < R)
    {
        ll res = solve(ri + 1, gi, bi + 1) + b[bi] * r[ri];
        ret = max(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> R >> G >> B;
    for (int i = 0; i < R; i++) cin >> r[i];
    for (int i = 0; i < G; i++) cin >> g[i];
    for (int i = 0; i < B; i++) cin >> b[i];
 
    sort(r, r + R); reverse(r, r + R);
    sort(g, g + G); reverse(g, g + G);
    sort(b, b + B); reverse(b, b + B);
 
    memset(dp, -1, sizeof dp);
 
    cout << solve(0, 0, 0);
}

---

E - Two Types of Spells

Problem - E - Codeforces

마법을 이용해 몬스터들과 싸우는 게임이 있다.

마법에는 불 마법과 번개 마법이 있다.

\(x\)강도의 불 마법은 몬스터에게 \(x\)만큼의 대미지를 주고,

\(y\)강도의 번개 마법은 몬스터에게 \(y\)만큼을 대미지를 주는 동시에, 다음 마법의 대미지를 2배 증가시킨다.

 

\(n\)번의 쿼리가 주어진다.

각 쿼리마다 \(d\) 강도의 불/번개 마법을 새로 익히거나,

\(d\)강도의 불/번개 마법을 잊어버린다.

 

쿼리가 주어진 이후에, 현재 알고 있는 모든 마법을 활용해 낼 수 있는 최대 대미지를 알아내야 한다.

 

우선 가능한 높은 강도의 마법의 대미지를 2배로 증가시키는게 가장 이득임을 알 수 있다.

쿼리가 들어올 때마다 현재 알고 있는 마법의 강도들을 내림차순으로 정렬했을 때, 상위 \(l\)개의 마법의 강도를 2배로 올리면 된다.

(\(l\) : 알고 있는 번개 마법의 수)

 

단 예외가 있는데, 상위 \(l\)개가 모두 번개 마법이라면 모두 대미지를 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 N = 200001;
 
vector <ll> x;
int getIdx(ll v) { return lower_bound(x.begin(), x.end(), v) - x.begin(); }
 
int n;
int cntTree[N * 4];
ll sumTree[N * 4];
int lTree[N * 4];
 
void lupdate(int ptr, int l, int r, int i, int val)
{
    if (i < l || r < i) return;
    if (l == r)
    {
        lTree[ptr] += val;
        return;
    }
 
    lupdate(ptr * 2, l, (l + r) / 2, i, val);
    lupdate(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
 
    lTree[ptr] = lTree[ptr * 2] + lTree[ptr * 2 + 1];
}
 
int lgetVal(int ptr, int l, int r, int i, int j)
{
    if (j < l || r < i) return 0;
    if (i <= l && r <= j) return lTree[ptr];
 
    return lgetVal(ptr * 2, l, (l + r) / 2, i, j)
        + lgetVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j);
}
 
void update(int ptr, int l, int r, int i, ll val)
{
    if (i < l || r < i) return;
    if (l == r)
    {
        sumTree[ptr] += val;
        if (val > 0) cntTree[ptr]++;
        else cntTree[ptr]--;
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
 
    sumTree[ptr] = sumTree[ptr * 2] + sumTree[ptr * 2 + 1];
    cntTree[ptr] = cntTree[ptr * 2] + cntTree[ptr * 2 + 1];
}
 
int getSegIdx(int ptr, int l, int r, int val)
{
    if (val == 0) return r + 1;
    if (l == r) return l;
 
    if (cntTree[ptr * 2 + 1] >= val)
    {
        return getSegIdx(ptr * 2 + 1, (l + r) / 2 + 1, r, val);
    }
    else
    {
        return getSegIdx(ptr * 2, l, (l + r) / 2, val - cntTree[ptr * 2 + 1]);
    }
}
 
ll getVal(int ptr, int l, int r, int i, int j)
{
    if (j < l || r < i) return 0;
    if (i <= l && r <= j) return sumTree[ptr];
 
    return getVal(ptr * 2, l, (l + r) / 2, i, j)
        + getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j);
}
 
multiset <ll> st;
vector <pll> query;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll tp, d; cin >> tp >> d;
        query.push_back({ tp,d });
        x.push_back(llabs(d));
    }
 
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
 
    ll sum = 0;
    int cl = 0;
    for (auto pll : query)
    {
        ll tp = pll.first;
        ll d = pll.second;
 
        int idx = getIdx(llabs(d));
 
        sum += d;
 
        if (tp == 1)
        {
            if (d > 0)
            {
                lupdate(1, 0, x.size() - 1, idx, 1);
                cl++;
            }
            else
            {
                lupdate(1, 0, x.size() - 1, idx, -1);
                cl--;
            }
        }
        else
        {
            if (d > 0) st.insert(d);
            else st.erase(st.find(-d));
        }
 
        update(1, 0, x.size() - 1, idx, d);
 
        int ti = getSegIdx(1, 0, x.size() - 1, cl);
 
        int lcnt = lgetVal(1, 0, x.size() - 1, ti, x.size() - 1);
        ll res = 0;
 
        if (lcnt == cl)
        {
            res = getVal(1, 0, x.size() - 1, ti + 1, x.size() - 1);
            if (!st.empty() && cl) res += *prev(st.end());
        }
        else
        {
            res = getVal(1, 0, x.size() - 1, ti, x.size() - 1);
        }
 
        cout << sum + res << '\n';
    }
}

---

F - Controversial Rounds

Problem - F - Codeforces

두 사람이 게임을 한다.

게임은 몇개의 세트로 이루어져 있는데, 어떤 플레이어가 \(x\)개의 라운드를 연속으로 승리하면 하나의 세트가 종료된다.

 

\(n\)개의 라운드가 주어진다.

각 라운드는 선공의 승리, 후공의 승리, 또는 누가 승리했는지 알 수 없음 총 3가지의 상태로 주어진다.

 

\(1 \le i \le n\)에 대해, 한 세트를 승리하기 위해 \(i\)개의 라운드를 연속으로 승리해야 될 때 이 게임에서 완료된 세트의 최대 개수를 알아내야 한다.

 

우선 답의 상한에 대해 생각해보자.

답이 가장 큰 경우는 모든 라운드를 한 사람이 이겼다고 할 수 있는 경우이다. 이 때 답은 다음과 같다.

\(\lfloor \frac n1 \rfloor + \lfloor \frac n2 \rfloor + \cdots \lfloor \frac nn \rfloor \le n\log n\)

 

따라서 각 \(i\)에 대해 가능한 라운드를 직접 세어도 \(n\log n\)번만에 필요한 라운드를 알 수 있다는 사실을 알 수 있다.

 

각 라운드부터 시작해서, 현재 라운드에서 이긴사람이 연속해서 이겼다고 할 수 있는 최대 라운드의 수를 계산할 수 있다.

이 배열을 \(mxLen\)이라고 하자.

1번 예제 같은 경우에는 이 값이 다음과 같다 : 3 2 4 3 2 1

 

현재 \(x\)개의 라운드를 연속으로 승리해야 될 때, 최대 세트의 수를 구해야 한다고 가정해보자.

현재 \(mxLen\)의 \(i\)번 인덱스부터 이를 계산해야 한다고 한다면, \(i\)보다 크거나 같은 인덱스에 대해 값이 \(x\)보다 크면서, 가장 작은 인덱스를 찾으면 된다는 사실을 알 수 있다.

 

이를 세그먼트 트리나 set등으로 \(\log n\)에 찾을 수 있는데, 그러면 총 시간복잡도가 \(O(n \log^2n)\)으로 매우 빡빡하고, 실제로 상수 최적화를 하지 않으면 시간초과가 난다.

Union-Find를 사용하면 위를 만족하는 값을 \(O(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 int N = 1000005;
 
int n;
string s;
 
int p0[N], p1[N], p2[N];
int mxLen[N];
 
int par[N];
int getPar(int x)
{
    if (par[x] == x) return x;
    return par[x] = getPar(par[x]);
}
 
void merge(int a, int b)
{
    a = getPar(a);
    b = getPar(b);
    par[a] = b;
}
 
int ans[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n + 1; i++) par[i] = i;
 
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '0') p0[i + 1] = 1;
        else if (s[i] == '1') p1[i + 1] = 1;
        else p2[i + 1] = 1;
 
        p0[i + 1] += p0[i];
        p1[i + 1] += p1[i];
        p2[i + 1] += p2[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        int l = i, r = n + 1;
        while (l + 1 < r)
        {
            int m = (l + r) / 2;
            int c0 = p0[m] - p0[i - 1];
            int c1 = p1[m] - p1[i - 1];
            int c2 = p2[m] - p2[i - 1];
 
            if (c0 + c2 == m - i + 1 || c1 + c2 == m - i + 1)
                l = m;
            else
                r = m;
        }
 
        int len = l - i + 1;
        mxLen[i] = len;
    }
 
    mxLen[n + 1] = n + 1;
 
    for (int i = 1; i <= n; i++)
    {
        int ci = 1;
        while (ci <= n)
        {
            while (mxLen[ci] < i)
            {
                merge(ci, ci + 1);
                ci = getPar(ci);
            }
 
            if (ci == n + 1) break;
            ans[i]++;
 
            ci = getPar(ci + i);
        }
    }
 
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

---

G - Running Competition

Problem - G - Codeforces

추가 예정