Codeforces Round #631 (Div. 1, Div. 2)

A - Dreamoon and Ranking Collection

Problem - A - Codeforces

\(n\)개의 수로 이루어진 수열 \(a\)와 양수 \(x\)가 주어진다.

수열 \(a\)에 \(x\)개의 수를 추가했을 때 \(1\)과 \(v\)사이 모든 수가 \(a\)에 존재한다고 할때, \(v\)의 최대값을 구해야 한다.

 

\(1 \le a_i \le 100\) 이므로 각 수가 존재하는지 여부를 저장 한 다음, 1부터 차례대로 검사해서 없는 수가 나올 때마다 수를 채우는 것을 \(x\)번 하면 된다.

답이 100을 초과할수 있으니 주의하자.

 

#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, x;
bool isExist[301];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        memset(isExist, 0, sizeof isExist);
        cin >> n >> x;
        for (int i = 0; i < n; i++)
        {
            int a; cin >> a;
            isExist[a] = 1;
        }
 
        int ans = 0;
        while (true)
        {
            if (!isExist[ans + 1])
            {
                if (x) x--;
                else break;
            }
            ans++;
        }
 
        cout << ans << '\n';
    }
}

---

B - Dreamoon Likes Permutations

Problem - B - Codeforces

\(n\)개의 수로 이루어진 수열 \(a\)가 주어진다.

이 수열을 \(l_1, l_2\)길이의 수열 2개로 나누었을 때, 각 수열이 모두 순열을 이루는 경우를 모두 찾아야 한다.

 

어떤 \(l\)길이의 수열이 \(1\)부터 \(l\)까지 모든 수가 한번씩 들어있는지 여부는

1. 서로 다른 수의 개수가 \(l\)개인지

2. 수열의 최대값이 \(l\)인지

두 조건을 확인함으로써 알 수 있는데, STL set을 이용하면 쉽게 확인할 수 있다.

 

길이 \(1\)부터 \(n-1\)까지 모든 수열을 앞뒤에서 한번 씩 확인한 다음,

앞에서 \(i\)길이의 수열이 순열이고, 뒤에서 \(n-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;
int a[200001];
bool isValid[200001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
 
        vector <int> ans;
        set <int> s;
        for (int i = 1; i < n; i++)
        {
            s.insert(a[i]);
            if (s.size() == i && *--s.end() == i) isValid[i] = 1;
            else isValid[i] = 0;
        }
 
        s.clear();
        for (int i = 1; i < n; i++)
        {
            s.insert(a[n + 1 - i]);
            if (s.size() == i && *--s.end() == i)
            {
                if (isValid[n - i]) ans.push_back(n - i);
            }
        }
 
        cout << ans.size() << '\n';
        for (auto it : ans) cout << it << ' ' << n - it << '\n';
    }
}

---

A - Dreamoon Likes Coloring

Problem - A - Codeforces

\(n\)개의 연속된 셀이 있다. 처음에 이 셀들은 비어있다.

이 셀들을 \(m\)번 색칠하려고 하는데, 색칠할 때마다 \(l_i\)길이의 연속된 셀을 칠해야 한다.

색들은 모두 다르고, 색이 겹쳐져 칠해질 수 있다. 이때는 셀은 가장 마지막으로 칠해진 색깔로 칠해져 있게 된다.

 

모든 색칠이 끝난후에 모든 셀이 적어도 하나의 색으로 칠해져 있고, 모든 색깔이 적어도 한 개의 셀에 색칠되어 있을 수 있는지 알아내야 한다. 가능하면 그 방법을 출력하면 된다.

 

가장 간단한 방법을 생각해 보자. \(i\)번째 색칠할 때 \(i\)번 인덱스부터 칠한다면 모든 색깔이 적어도 한번씩 보이도록 할 수 있다.

이 과정에서 \(n\)번째 칸을 넘어가서 색칠되거나, 색칠되는 칸수의 합이 \(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; }
 
ll n, m;
ll l[100001];
ll last[100001];
int ans[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    ll sum = 0;
    for (int i = 0; i < m; i++)
        cin >> l[i], sum += l[i];
 
    if (sum < n)
    {
        cout << -1;
        return 0;
    }
 
    for (int i = 0; i < m; i++)
    {
        last[i] = i + l[i];
        if (i) last[i] = max(last[i - 1], last[i]);
 
        if (last[i] > n)
        {
            cout << -1;
            return 0;
        }
    }
 
    ll colored = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        if (last[i] + colored < n) ans[i] = n - colored - (l[i] - 1);
        else ans[i] = i + 1;
        colored += l[i];
    }
 
    for (int i = 0; i < m; i++) cout << ans[i] << ' ';
}

---

B - Dreamoon Likes Sequences

Problem - B - Codeforces

정수 \(d, m\)이 주어질 때, 다음을 만족하는 수열 \(a\)의 개수를 찾아야 한다.

1. \(a\)의 길이는 1이상이다.

2. \(1 \le a_1 \lt a_2 \lt \dots \lt a_n \le d \)

3. 다음과 같은 수열 \(b\)에 대해 : \(b_1 = a_1, b_i = b_{i-1} \oplus a_i\)

\(b_1 \lt b_2 \lt \dots \lt b_{n-1} \lt b_n\) 이다.

 

3번 조건을 만족하기 위해 수열이 어떻게 이루어져야 하는지 관찰해 보면,

\(a_i\)의 최상위 비트보다 \(a_{i+1}\)의 최상위 비트가 커야 한다는 사실을 알 수 있다.

간단한 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; }
 
ll res[50];
ll ans[50];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll d, m; cin >> d >> m;
        memset(res, 0, sizeof res);
        memset(ans, 0, sizeof ans);
 
        ll i = 1;
        while (true)
        {
            if ((1ll << i) > d) break;
 
            res[i - 1] = 1ll << (i - 1);
            i++;
        }
 
        res[i - 1] = (d - (1ll << (i - 1))) + 1;
 
        ll sum = 0;
        for (int j = i - 1; j >= 0; j--)
        {
            ans[j] = (ans[j + 1] + 1) * res[j] % m;
            ans[j] += ans[j + 1];
            ans[j] %= m;
        }
 
        cout << ans[0] << '\n';
    }
}

---

C - Drazil Likes Heap

Problem - C - Codeforces

\(h\) 높이의 꽉 찬 힙이 주어진다. 힙에 들어있는 모든 수는 서로 다르다.

이 힙에서 \(2^h-2^g\)개의 수를 삭제해서 \(g\) 높이의 꽉 찬 힙으로 만드려고 한다.

힙의 원소를 삭제할 때는 문제에 주어진 함수를 이용한다. (삭제하는 중에는 힙이 완전이진트리가 아닐 수도 있다.)

 

이 때 모든 삭제작업 이후 힙에 남아있는 수들의 합을 최소화 해야 한다.

 

관찰을 잘 해보면 현재 힙에서 가장 큰 수를 삭제 했을 때 최소 높이가 \(g\) 미만으로 내려가지 않는다면, 이 수를 삭제 하는 것이 최적임을 알 수 있다.

따라서 그리디하게 힙에서 삭제할 수 있는 수 중 가장 큰 수를 삭제하는 것을 반복하면 된다.

삭제 가능 여부를 확인하는 것, 실제 값을 삭제 하는 것 모두 \(O(h)\)이므로, \(O(nh)\)에 해결할 수 있다.

 

#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 h, g;
int idx[1048577];
int height[1048577];
int org_pq[1048577];
int pq[1048577];
 
vector <int> comp;
int getIdx(int x)
{
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}
 
void DFS(int v, int ch)
{
    if (v >= (1 << h)) return;
    height[v] = ch;
    DFS(v * 2, ch + 1);
    DFS(v * 2 + 1, ch + 1);
}
 
bool isOK(int v)
{
    int l, r;
    if (v * 2 >= (1 << h)) l = 0;
    else l = pq[v * 2];
    if (v * 2 + 1 >= (1 << h)) r = 0;
    else r = pq[v * 2 + 1];
 
    int org_l, org_r;
    if (v * 2 >= (1 << h)) org_l = 0;
    else org_l = org_pq[v * 2];
    if (v * 2 + 1 >= (1 << h)) org_r = 0;
    else org_r = org_pq[v * 2 + 1];
 
    if (l == 0 && r == 0)
    {
        if (height[v] > g)
        {
            pq[v] = 0;
            org_pq[v] = 0;
            return true;
        }
        else return false;
    }
 
    if (l > r)
    {
        if (isOK(v * 2))
        {
            idx[l] = v;
            pq[v] = l;
            org_pq[v] = org_l;
            return true;
        }
        else return false;
    }
    else
    {
        if (isOK(v * 2 + 1))
        {
            idx[r] = v;
            pq[v] = r;
            org_pq[v] = org_r;
            return true;
        }
        else return false;
    }
}
 
vector <int> ans;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ans.clear();
        comp.clear();
 
        cin >> h >> g;
        for (int i = 1; i <= (1 << h) - 1; i++)
        {
            cin >> org_pq[i];
            comp.push_back(org_pq[i]);
        }
 
        sort(comp.begin(), comp.end());
 
        for (int i = 1; i <= (1 << h) - 1; i++)
        {
            pq[i] = getIdx(org_pq[i]) + 1;
            idx[pq[i]] = i;
        }
 
        DFS(1, 1);
 
        int cur_num = (1 << h) - 1;
        int cnt = (1 << h) - (1 << g);
        while (cnt)
        {
            if (isOK(idx[cur_num]))
            {
                ans.push_back(idx[cur_num]);
                cnt--;
            }
 
            cur_num--;
        }
 
        ll sum = 0;
        for (int i = 1; i <= (1 << g) - 1; i++) sum += org_pq[i];
 
        cout << sum << '\n';
        for (auto it : ans) cout << it << ' ';
        cout << "\n";
    }
}

---

D - Dreamoon Likes Strings

Problem - D - Codeforces

추가 예정

---

E - Dreamoon Loves AA

Problem - E - Codeforces

추가 예정