Codeforces Round #661 (Div. 3)

A - Remove Smallest

https://codeforces.com/contest/1399/problem/A

\(n\)개의 원소를 가진 배열 \(a\)가 주어진다.

한 번의 연산으로, 배열의 서로 다른 두 인덱스 \(i,j\)를 고른다음, \(a_i\)와 \(a_j\)의 차이가 1 이하라면 둘 중 작은 값을 삭제할 수 있다.

두 값이 같다면 둘 중 아무거나 하나를 삭제한다.

 

이 연산을 반복해서 배열에 원소 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[51];
 
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];
        sort(a, a + n);
 
        bool ans = true;
        for (int i = 1; i < n; i++) if (a[i - 1] + 1 < a[i]) ans = false;
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Gifts Fixing

https://codeforces.com/contest/1399/problem/B

\(n\)개의 선물이 있다. 각각의 선물은 \(a_i\)개의 캔디와 \(b_i\)개의 오렌지로 이루어져 있다.

 

한번의 연산으로, 하나의 선물을 골라 다음과 같은 연산 중 하나를 할 수 있다.

 

1. 이 선물에서 캔디 1개를 없앤다.

2. 이 선물에서 오랜지 1개를 없앤다.

3. 이 선물에서 캔디와 오렌지 1개를 없앤다.

 

이 연산을 이용해서, 각 선물에 들어있는 캔디의 개수가 각각 같고, 오렌지의 개수도 각각 같도록 하려고 한다.

필요한 연산의 최소값을 구해야 한다.

 

캔디와 오렌지 각각에 대해 가장 적게 들어있는 선물에 들어있는 개수를 각각 \(min_a, min_b\)라고 하자.

모든 선물에 든 캔디와 오렌지 개수를 \((min_a, min_b)\)로 맞춰주면 된다.

 

각 선물에 필요한 연산 수는 쉽게 계산할 수 있다.

 

#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 a[51], b[51];
 
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];
        for (int i = 0; i < n; i++) cin >> b[i];
 
        ll min_a = *min_element(a, a + n);
        ll min_b = *min_element(b, b + n);
 
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            ll ca = a[i] - min_a;
            ll cb = b[i] - min_b;
 
            ans += max(ca, cb);
        }
 
        cout << ans << '\n';
    }
}

---

C - Boats Competition

https://codeforces.com/contest/1399/problem/C

\(n\)명의 사람들이 있다. 각 사람들의 무게는 \(w_i\)이다.

 

사람들을 둘 씩 짝지어서 \(k\)개의 팀을 만드는데, 각 팀에 속한 두 사람의 무게의 합이 \(s\)로 같도록 하려고 한다.

\(s\)를 적절히 정했을 때, \(k\)의 최대값을 구해야 한다.

 

\(s\)를 \(2\)부터 \(2n\)까지 설정했을 때 각각에 대해, 생길 수 있는 팀의 수를 \(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;
int cnt[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        memset(cnt, 0, sizeof cnt);
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int w; cin >> w;
            cnt[w]++;
        }
 
        int ans = 0;
        for (int s = 2; s <= 100; s++)
        {
            int res = 0;
            for (int l = 1; l + l < s; l++)
            {
                res += min(cnt[l], cnt[s - l]);
            }
            if (s % 2 == 0) res += cnt[s / 2] / 2;
 
            if (res > ans)
            {
                ans = res;
            }
        }
 
        cout << ans << '\n';
    }
}

---

D - Binary String To Subsequences

https://codeforces.com/contest/1399/problem/D

\(n\)길이의 이진 문자열 \(s\)가 주어진다.

 

이 문자열을 여러개의 부분 수열로 분할해서, 각 부분 수열이 010101... 또는 101010... 이 되도록 하려고 한다.

분할하는 부분 수열을 최소로 했을 때, 가능한 해를 하나 출력해야 한다.

 

남아 있는 문자열이 '0'으로 시작한다면 이 '0'을 선택하고, 더 뒤에 있는 '1'중 가장 가장 가까운 것을 찾아 선택한다.

그리고 그 '1'의 뒤에 있는 '0'중 가장 가까운 것을 선택하는 것을 반복하면 맨 앞 문자를 포함하면서 현재 만들 수 있는 부분 수열 중 가장 긴 부분 수열을 하나 만들 수 있음을 알 수 있다.

 

이를 스택이나 set등으로 \(O(n)\)미만의 시간으로 가능하게 구현하면 총 \(O(n)\)또는 \(O(n \log 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 ans[200001];
 
set <int> idx[2];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s;
        idx[0].clear();
        idx[1].clear();
 
        for (int i = 0; i < s.size(); i++)
        {
            idx[s[i] - '0'].insert(i);
        }
 
        int cnt = 0;
        while (!idx[0].empty() || !idx[1].empty())
        {
            cnt++;
            int start, ci;
            if (idx[0].empty()) start = 1;
            else if (idx[1].empty()) start = 0;
            else
            {
                if (*idx[0].begin() < *idx[1].begin()) start = 0;
                else start = 1;
            }
 
            if (start == 0) ci = *idx[0].begin();
            else ci = *idx[1].begin();
 
            auto it = idx[start].lower_bound(ci);
            while (true)
            {
                ans[*it] = cnt;
                idx[start].erase(it);
 
                start = 1 - start;
                it = idx[start].lower_bound(ci);
                
                if (it == idx[start].end()) break;
                ci = *it;
            }
        }
 
        cout << cnt << '\n';
        for (int i = 0; i < n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

E - Weights Division (hard version)

https://codeforces.com/contest/1399/problem/E2

루트가 1이고 정점이 \(n\)개인 트리가 주어진다.

각각의 간선은 가중치와 비용(1 또는 2)을 포함하고 있다.

 

루트에서 리프까지 향하는 각 경로에 대해, 경로에 포함되어 있는 간선의 가중치의 합을 \(S\)이하로 낮추려고 한다.

이를 위해 연산을 할 수 있다. 한번의 연산으로, 간선 하나를 골라 가중치를 2로 나눌 수 있다. 이 때 그 간선에 설정된 비용이 든다.

 

최소한의 비용으로 루트에서 리프까지 향하는 모든 경로의 가중치의 합을 \(S\)이하로 줄이려고 한다. 이 때의 필요한 비용을 구해야 한다.

 

easy버전은 모든 간선의 비용이 1인 특수한 경우이다.

 

각각의 간선에 대해, 한번의 연산으로 줄어드는 가중치를 계산할 수 있다.

모든 간선의 비용이 같다면, 이 줄어드는 가중치가 큰 간선부터 줄여 나가는것이 이득임을 알 수 있다.

 

비용이 1인 모든 간선에 대해 \(x\)번 연산했을 때 줄어드는 가중치의 총량을 계산해 놓자.

그러면 비용이 2인 간선을 위와 같이 차례대로 줄여 나가면서, 현재 비용이 2인 간선을 \(y\)번 연산했을 때, 총 가중치가 \(S\)이하가 되기 위해 줄여야 하는 비용 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; ll s;
struct Node
{
    ll nv;
    ll w;
    ll c;
};
 
vector <Node> graph[100001];
set <pair<pair<ll, pll>, pii> > st1, st2;
 
ll cs = 0;
ll DFS(int v, int p)
{
    if (graph[v].size() == 1 && p)
        return 1;
 
    ll res = 0;
    for (auto it : graph[v])
    {
        int nv = it.nv;
        ll w = it.w;
        ll c = it.c;
 
        if (nv == p) continue;
 
        ll cr = DFS(nv, v);
 
        if (c == 1) st1.insert({ {(w - w / 2) * cr, {w, cr}}, {v, nv} });
        else if (c == 2) st2.insert({ {(w - w / 2) * cr, {w, cr}}, {v, nv} });
 
        res += cr;
        cs += cr * w;
    }
 
    return res;
}
 
vector <ll> s_all;
 
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 = 1; i <= n; i++) graph[i].clear();
        st1.clear(), st2.clear();
        cs = 0;
        s_all.clear();
        s_all.push_back(0);
 
        for (int i = 0; i < n - 1; i++)
        {
            ll u, v, w, c; cin >> u >> v >> w >> c;
            graph[u].push_back({ v,w,c });
            graph[v].push_back({ u,w,c });
        }
 
        DFS(1, 0);
 
        while (!st1.empty())
        {
            auto it = --st1.end();
            ll dc = it->first.first;
            ll w = it->first.second.first;
            ll cr = it->first.second.second;
            pii eg = it->second;
            w /= 2;
 
            st1.erase(it);
            s_all.push_back(s_all.back() + dc);
 
            if (w) st1.insert({ {(w - w / 2) * cr, {w, cr}}, eg });
        }
 
        ll ans = numeric_limits<ll>::max();
        
        int idx = lower_bound(s_all.begin(), s_all.end(), cs - s) - s_all.begin();
        if (idx != s_all.size()) ans = idx;
 
        ll cur_cost = 0;
 
        while (!st2.empty() && cs > s)
        {
            auto it = --st2.end();
            ll dc = it->first.first;
            ll w = it->first.second.first;
            ll cr = it->first.second.second;
            pii eg = it->second;
            w /= 2;
 
            cur_cost += 2;
            st2.erase(it);
            cs -= dc;
 
            ll remain = cs - s;
            int idx = lower_bound(s_all.begin(), s_all.end(), remain) - s_all.begin();
 
            if (idx != s_all.size())
            {
                ll res = cur_cost + idx;
                ans = min(ans, res);
            }
 
            if (w) st2.insert({ {(w - w / 2) * cr, {w, cr}}, eg });
        }
 
        cout << ans << '\n';
    }
}

---

F - Yet Another Segments Subset

https://codeforces.com/contest/1399/problem/F

\(n\)개의 구간이 주어진다.

 

다음 조건을 만족하는 구간의 집합의 크기의 최대값을 구해야 한다.

- 집합에 속한 서로 다른 두 구간을 선택했을 때, 둘 중 하나를 만족해야 한다.

1. 두 구간이 공통된 점을 가지지 않는다.

2. 한 구간이 다른 구간을 포함한다.

 

우선 구간의 범위가 크므로, 좌표압축을 하자.

구간을 \(l\)의 오름차순으로, \(l\)이 같다면 \(r\)의 내림차순으로 정렬하자.

그러면 어떤 구간 \(a\)가 \(b\)를 포함한다고 할 때, \(b\)는 무조건 \(a\)의 다음에 온다는 사실을 알 수 있다.

 

DP식을 다음과 같이 정의하자.

\(DP(idx, r)\) : \(idx\)번째와 그 이후의 구간만을 사용했을 때, 오른쪽 끝이 \(r\)인 구간에서 문제의 답

 

그러면 \(idx\)번째 구간을 사용할 때, 사용하지 않을 때 총 2가지의 부분 문제만을 계산하여 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 n;
pii seg[3001];
vector <int> x;
 
bool cmp(pii p1, pii p2)
{
    if (p1.first != p2.first) return p1.first < p2.first;
    return p1.second > p2.second;
}
 
int dp[3001][6001];
int solve(int idx, int r)
{
    if (idx == n) return 0;
 
    int& ret = dp[idx][r];
    if (ret != -1) return ret;
 
    ret = 0;
    ret = max(ret, solve(idx + 1, r));
 
    if (seg[idx].second <= r)
    {
        int nidx = lower_bound(seg + idx, seg + n, pii(seg[idx].second + 1, r), cmp) - seg;
        int res = solve(idx + 1, seg[idx].second)
            + solve(nidx, r) + 1;
 
        ret = max(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        x.clear();
 
        for (int i = 0; i < n; i++) for (int j = 0; j < n * 2; j++) dp[i][j] = -1;
 
        for (int i = 0; i < n; i++)
        {
            int l, r; cin >> l >> r;
            seg[i] = { l,r };
 
            x.push_back(l);
            x.push_back(r);
        }
 
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
 
        for (int i = 0; i < n; i++)
        {
            int& l = seg[i].first;
            int& r = seg[i].second;
 
            l = lower_bound(x.begin(), x.end(), l) - x.begin();
            r = lower_bound(x.begin(), x.end(), r) - x.begin();
        }
 
        sort(seg, seg + n, cmp);
        cout << solve(0, n * 2 - 1) << '\n';
    }
}