Educational Codeforces Round 101

A - Regular Bracket Sequence

Problem - A - Codeforces

'('와 ')', 물음표로 이루어진 괄호 문자열이 주어진다.

'('와 ')'는 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        string s; cin >> s;
 
        bool ans = true;
        if (s.size() % 2) ans = false;
 
        if (s[0] == ')' || s[s.size() - 1] == '(') ans = false;
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Red and Blue

Problem - B - Codeforces

\(n+m\)개의 원소로 이루어진 수열 \(a\)가 있다.

이 수열을 \(n\)개의 원소를 가진 수열 \(r\), \(m\)개의 원소를 가진 수열 \(b\)로 분할했다.

 

\(r, b\)가 주어졌을 때, \(a\)를 복원해야 한다.

단, \(a\)의 prefix sum중 최대값이 최대한 크도록 복원해야 하고, 이 때 그 값을 출력해야 한다.

 

 

\(r\)의 최대 prefix sum과 \(b\)의 최대 prefix sum의 합이 답이다.

 

#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;
int r[101], b[101];
 
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 >> r[i], r[i] += r[i - 1];
        cin >> m;
        for (int i = 1; i <= m; i++) cin >> b[i], b[i] += b[i - 1];
 
        int ans = *max_element(r, r + n + 1) + *max_element(b, b + m + 1);
 
        cout << ans << '\n';
    }
}

---

C - Building a Fence

Problem - C - Codeforces

\(n\)길이를 가지는 울타리를 만드려고 한다.

울타리의 각 섹션은 \(k\)의 높이를 가진다.

 

이 울타리를 땅에 설치하려고 하는데, 다음을 만족해야 한다.

1. 맨 처음과 맨 끝 울타리는 땅과 높이가 같아야 한다.

2. 울타리는 땅과 높이가 같거나, 많아도 위로 \(k-1\)만큼만 떨어져 있어야 한다.

3. 인접한 두 울타리는 적어도 1높이의 공통된 면을 가져야 한다.

 

땅의 높이를 나타내는 배열 \(h\)가 주어졌을 때, 위의 조건을 만족하면서 울타리를 설치할 수 있는지 여부를 알아내야 한다.

 

 

각 울타리가 가질 수 있는 높이는 연속이다.

따라서 맨 왼쪽부터 차례대로 각 울타리의 가능한 최소 높이와 최대 높이를 갱신하며 가능 여부를 확인하면 된다.

 

#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 h[200001];
 
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 = 0; i < n; i++) cin >> h[i];
 
        bool ans = true;
 
        ll mn = h[0], mx = h[0];
        for (int i = 1; i < n; i++)
        {
            mn = max(0ll, mn - (k - 1));
            mn = max(mn, h[i]);
            if (mn > h[i] + (k - 1)) ans = false;
 
            mx = min(h[i] + (k - 1), mx + (k - 1));
            if (mx < h[i]) ans = false;
        }
 
        if (mn != h[n - 1]) ans = false;
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

D - Ceil Divisions

Problem - D - Codeforces

1부터 \(n\)까지 수를 가진 배열 \(a\)가 있다.

한번의 연산으로 서로 다른 위치의 두 수 \(a_x, a_y\)를 골라, \(a_x\)를 \(\lceil \frac{a_x}{a_y} \rceil\) 로 바꿀 수 있다.

 

배열이 \(n-1\)개의 1과, 1개의 2로만 이루어지도록 해야 한다.

이 때, 위의 연산을 최대 \(n+5\)번까지 사용할 수 있다.

 

 

다음을 반복하면 된다.

\(sq = \lfloor \sqrt n \rfloor\)이라고 하자.

\(sq\)이상 \(n\)미만인 모든 수들을 1로 바꾼다.

\(n\)을 \(sq\)로 나눈다.

 

그러면 3이상 \(n-1\)이하의 모든 수들은 단 1번의 연산으로 1이 되고,

\(n\)은 1이 될 때까지 제곱근을 씌운다는 사실을 알 수 있다.

\(n\)이 최대 200000이고, 제곱근을 5번 씌우면 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;
vector <pii> ans;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        ans.clear();
 
        int cur = n;
        int ptr = n - 1;
        while (ptr > 2)
        {
            int sq = max(2.0, sqrt(cur));
            for (int i = sq + 1; i <= ptr; i++)
            {
                ans.push_back({ i, n });
            }
 
            ans.push_back({ n, sq });
            cur = cur / sq + (cur % sq ? 1 : 0);
 
            ptr = sq;
        }
 
        while (cur > 1)
        {
            ans.push_back({ n, 2 });
            cur = cur / 2 + (cur % 2 ? 1 : 0);
        }
 
        cout << ans.size() << '\n';
        for (auto it : ans)
            cout << it.first << ' ' << it.second << '\n';
    }
}

---

E - A Bit Similar

Problem - E - Codeforces

어떤 \(k\)길이의 문자열 \(a, b\)가 문자가 같은 인덱스가 하나라도 있다면, 이 두 문자열을 비슷하다고 한다.

 

\(n\)길이의 이진 문자열 \(s\)가 주어졌을 때, 이 문자열의 모든 \(k\)길이의 부분 문자열과 비슷한 \(k\)길이의 문자열 \(t\)가 존재하는지 알아내야 한다.

존재한다면, 그 중 사전순으로 가장 작은 \(t\)를 출력해야 한다.

 

 

먼저, \(s\)의 \(k\)길이의 부분 문자열은 \(O(n)\)개이므로,

답이 존재한다면 그 이진 문자열을 정수로 변환했을 때 답이 무조건 \(n\)이하라는 사실을 알 수 있다.

\(n\)이 \(10^6\)이하이므로, 맨 뒤 \(\min(20, k) = len\)자리만 확인하면 되고 그 앞은 전부 0으로 채운 게 답이 될 것이다.

 

\(s\)의 모든 \(k\)길이의 부분 문자열을 확인해보자.

맨 앞 \(k-len\)자리를 0으로 채웠을 때 비슷한 부분 문자열은 일단 제외하고, 그렇지 않은 문자열의 뒤 \(len\)자리를 정수로 변환해서 set 등에 저장하자.

 

이렇게 저장한 정수들은 \([0, 2^len)\)의 범위를 가질 것이다.

이 범위의 정수들 중 위에서 저장되지 않은(존재하지 않는) 정수가 있다고 하자.

이 정수의 모든 비트를 반전 시키면, 저장한(존재하는) 모든 정수와 비슷할 것이다.

 

이 중 반전시켰을 때 가장 작은 것을 찾는게 문제이므로, 반전시키지 않았을 때 set에 존재하지 않는 가장 큰 수를 찾으면 된다.

그런 수가 없다면 조건을 만족하는 문자열은 존재하지 않는다.

 

 

#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, k, len;
string s;
 
vector <int> vec;
int cache[1 << 21];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int q; cin >> q;
    while (q--)
    {
        cin >> n >> k;
        cin >> s;
 
        int cur = 0;
        len = min(20, k);
        for (int i = k - len; i < k; i++)
        {
            cur *= 2;
            cur += s[i] - '0';
        }
 
        int cnt = 0;
        for (int i = 0; i < k - len; i++)
            if (s[i] == '0') cnt++;
 
        if (!cnt)
        {
            vec.push_back(cur);
            cache[cur]++;
        }
 
        for (int i = k; i < n; i++)
        {
            if (s[i - len] == '0') cnt++;
            if (s[i - k] == '0') cnt--;
 
            cur *= 2;
            cur += s[i] - '0';
            cur -= ((s[i - len] - '0') << len);
 
            if (!cnt)
            {
                vec.push_back(cur);
                cache[cur]++;
            }
        }
 
        int ans;
        for (ans = (1 << len) - 1; ans >= 0; ans--)
        {
            if (!cache[ans]) break;
        }
 
        while (!vec.empty())
        {
            int x = vec.back(); vec.pop_back();
            cache[x]--;
        }
 
        if (ans == -1)
        {
            cout << "NO\n";
            continue;
        }
 
        cout << "YES\n";
        for (int i = 0; i < k - len; i++) cout << '0';
        for (int i = len - 1; i >= 0; i--) cout << 1 - !!(ans & (1 << i));
        cout << '\n';
    }
}

---

F - Power Sockets

Problem - F - Codeforces

추가 예정