Codeforces Round #690 (Div. 3)

A - Favorite Sequence

Problem - A - Codeforces

생략

---

B - Last Year's Substring

Problem - B - Codeforces

\(n\)길이의 문자열 \(s\)가 들어온다.

이 문자열의 부분문자열을 삭제해서 "2020"을 만들 수 있는지 여부를 알아내면 된다.

 

\(s\)의 prefix와 suffix를 조합해 "2020"을 만들 수 있는지 확인하면 된다.

 

#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;
 
string x = "2020";
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> s;
 
        bool ans = false;
        for (int i = 0; i < 5; i++)
        {
            bool flag = true;
            for (int j = 0; j < 4 - i; j++)
            {
                if (s[j] != x[j]) flag = false;
            }
 
            for (int j = 0; j < i; j++)
            {
                if (s[n - 1 - j] != x[3 - j]) flag = false;
            }
 
            if (flag) ans = true;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

C - Unique Number

Problem - C - Codeforces

\(x\)가 주어진다.

 

자리수의 합이 \(x\)이고, 모든 자리수가 서로 다른 수 중 가장 작은 수를 출력해야 한다.

그런 수가 없다면 -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 ten[10] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
 
ll dp[1 << 9][51];
ll solve(int bs, int rm)
{
    ll& ret = dp[bs][rm];
    if (ret != -1) return ret;
    if (rm == 0) return ret = 0;
 
    ret = -2;
    for (int i = 9; i >= 1; i--)
    {
        if (bs & (1 << i - 1)) continue;
        if (rm < i) continue;
        ll res = solve(bs | (1 << i - 1), rm - i);
        if (res != -2)
        {
            res = res * 10 + i;
            if (ret == -2 || ret > res) ret = res;
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        memset(dp, -1, sizeof dp);
 
        int x; cin >> x;
        ll ans = solve(0, x);
        if (ans == -2) ans = -1;
        cout << ans << '\n';
    }
}

---

D - Add to Neighbour and Remove

Problem - D - Codeforces

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

이 배열의 임의의 원소 하나를 삭제한다음, 이웃한 원소 중 하나에 더하는 연산을 할 수 있다.

 

배열의 모든 값이 같게 되도록 해야하는 최소 연산 횟수를 알아내야 한다.

 

 

문제를 다음과 같이 바꿀 수 있다.

배열을 적당히 몇 개의 구간으로 나눠서, 구간의 원소의 합이 모두 같도록 할 수 있을 때 구간의 최대 수

 

맨 첫번째 구간에 대해 생각해보자.

이 구간은 맨 첫 원소를 무조건 포함해야 하므로, 첫 구간의 원소의 합이 될 수 있는 경우의 수는 \(n\)가지임을 알 수 있다.

 

따라서 이 \(n\)가지 모든 경우에 대해 \(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;
ll a[3001];
ll psum[3001];
 
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];
            psum[i] = psum[i - 1] + a[i];
        }
 
        int ans = 987654321;
 
        for (int k = 1; k <= n; k++)
        {
            bool flag = true;
 
            ll gsum = psum[k];
 
            int cnt = k - 1;
            ll csum = 0;
            for (int i = k + 1; i <= n; i++)
            {
                if (csum + a[i] > gsum)
                {
                    flag = false;
                    break;
                }
 
                if (csum) cnt++;
                csum += a[i];
 
                if (csum == gsum) csum = 0;
            }
 
            if (csum) flag = false;
            if (flag)
            {
                ans = min(ans, cnt);
            }
        }
 
        cout << ans << '\n';
    }
}

---

E - Close Tuples (hard version)

Problem - E2 - Codeforces

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

이 배열의 부분 집합인 모든 \(m\) 크기의 unordered tuple에 대하여, 최소값과 최대값의 차이가 \(k\)이하인 tuple의 수를 알아내면 된다.

 

일단 \(a\)를 정렬하자.

각 \(a_i\)에 대해, \(a_i\)를 무조건 고른다고 가정했을 때 (\(i\)가 고른 원소 중 최소 인덱스) 개수를 각각 구해보자.

먼저 \(a_i\)와의 차이가 \(k\)이하인 최대 인덱스 \(j\)를 \(O(\log n)\)에 구할 수 있다.

 

그러면 \(j-i\)개의 수 중 \(m-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 ll MOD = 1e9 + 7;
ll mpow(ll a, ll n)
{
    if (n == 0) return 1;
    ll res = mpow(a, n / 2);
    res = res * res % MOD;
    if (n % 2) res = res * a % MOD;
    return res;
}
 
ll fact[200001];
ll inv_fact[200001];
 
ll ncr(ll n, ll r)
{
    ll res = fact[n];
    res = res * inv_fact[r] % MOD;
    res = res * inv_fact[n - r] % MOD;
 
    return res;
}
 
int n, m, k;
int a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    fact[0] = 1;
    inv_fact[0] = 1;
 
    for (ll i = 1; i <= 200000; i++)
    {
        fact[i] = fact[i - 1] * i % MOD;
        inv_fact[i] = inv_fact[i - 1] * mpow(i, MOD - 2) % MOD;
    }
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
 
        ll ans = 0;
        for (ll i = 0; i < n; i++)
        {
            int ridx = upper_bound(a + i, a + n, a[i] + k) - a;
            if (i + m > ridx) continue;
            ll res = ncr(ridx - i - 1, m - 1);
            ans = (ans + res) % MOD;
        }
 
        cout << ans << '\n';
    }
}

---

F - The Treasure of The Segments

Problem - F - Codeforces

원소가 구간 \([l_i, r_i]\) \(n\)개인 집합이 주어진다.

어떤 \(k\)개의 구간 집합에 대해, 나머지 모든 구간과 겹치는 구간이 하나 이상 존재한다면 이 집합을 좋다고 한다.

 

이 집합이 좋은 집합이 되기 위해 삭제해야 하는 최소 구간의 수를 알아내야 한다.

 

\(i\)번째 구간과 겹치는 구간의 수를 \(x_i\)라고 하자.

문제의 답은 모든 구간에 대해 \(n-(x_i+1)\)중 가장 작은 값이 된다.

 

\(x_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; }
 
const int N = 200001;
 
int n;
int l[N], r[N];
 
int st[N];
int sum[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
 
        vector <pair<int, pii> > v;
 
        for (int i = 0; i < n; i++)
        {
            cin >> l[i] >> r[i];
            v.push_back({ l[i],{0, i} });
            v.push_back({ r[i],{1, i} });
        }
 
        sort(v.begin(), v.end());
 
        int cnt = 0;
        int cur = 0;
        for (auto it : v)
        {
            int num = it.first;
            int type = it.second.first;
            int idx = it.second.second;
 
            if (type == 0)
            {
                cnt++;
                cur++;
 
                st[idx] = cnt;
                sum[idx] = cur;
            }
            else
            {
                cur--;
                sum[idx] += cnt - st[idx];
            }
        }
 
        int res = *max_element(sum, sum + n);
 
        //cout << "ANS:";
        cout << n - res << '\n';
    }
}