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

A - Nezzar and Colorful Balls

Problem - A - Codeforces

\(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;
 
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            ans = max(ans, ++cnt[x]);
        }
 
        cout << ans << '\n';
    }
}

---

B - Nezzar and Lucky Number

Problem - B - Codeforces

0을 제외한 숫자 \(d\)가 주어진다.

정수 \(a\)가 주어지면, 숫자에 적어도 \(d\)가 1번이상 포함된 수의 합으로 \(a\)를 나타낼 수 있는지 알아내야 한다.

 

먼저, \(a \ge 10d\)면 무조건 가능하다.

그렇지 않다면 완전탐색으로 가능여부를 판단하면 된다.

 

#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 q, d;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> q >> d;
 
        while (q--)
        {
            int a; cin >> a;
 
            if (a >= d * 10)
            {
                cout << "YES\n";
                continue;
            }
            
            bool ans = false;
            int c = d;
 
            while (c <= a)
            {
                if ((a - c) % 10 == 0)
                {
                    ans = true;
                    break;
                }
 
                c += d;
            }
 
            if (ans) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

---

C - Nezzar and Symmetric Array

Problem - C - Codeforces

\(2n\)길이의 배열 \(a\)가 있다.

이 배열은 모든 원소가 정수이며 서로 다르고, \(x\)가 존재하면 \(-x\)도 존재한다.

 

각각의 원소에서 다른 원소까지의 차의 합을 저장한 배열 \(d\)가 주어졌을 때,

\(d\)로 \(a\)를 복원할 수 있는지 여부를 알아내야 한다.

 

 

\(a\)의 원래 포함되어 있던 양수들에 대해, 이웃한 두 수들의 차를 이용해 연립방정식을 만들자.

방정식의 정수해가 존재하는지 여부를 확인하면 된다.

 

#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 d[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 = 0; i < 2 * n; i++)
            cin >> d[i];
 
        sort(d, d + 2 * n);
 
        bool ans = true;
 
        if (d[0] % 2) ans = false;
        if (d[0] != d[1]) ans = false;
 
        ll rm = d[0];
 
        for (int i = 1; i < n; i++)
        {
            if (d[2 * i] != d[2 * i + 1]) ans = false;
 
            ll cd = d[i * 2] - d[i * 2 - 2];
            if (cd == 0) ans = false;
            if (cd % (2 * i)) ans = false;
 
            ll num = cd / (2 * i);
            //cout << "NUM:" << num << '\n';
            rm -= 2ll * num * (n - i);
        }
 
        if (rm <= 0) ans = false;
        if (rm % n) ans = false;
        if (rm / n % 2) ans = false;
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

A - Nezzar and Board

Problem - A - Codeforces

\(n\)개의 정수로 이루어진 배열 \(x\)가 있다.

이 \(x\)의 두 원소 \(a, b\)를 선택해, 배열에 \(2a-b\)를 추가할 수 있다고 할 때,

\(k\)가 배열에 포함될 수 있게 할 수 있는지 여부를 알아내야 한다.

 

배열을 정렬한 다음, 이웃한 두 원소의 차들의 GCD를 구해 이를 \(g\)라고 하자.

배열의 임의의 원소와 \(k\)의 차이가 \(g\)의 배수이면 가능하다.

 

 

#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 x[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 >> x[i];
 
        if (k == 0)
        {
            cout << "YES\n";
            continue;
        }
 
        sort(x, x + n);
 
        ll g = 0;
        for (int i = 1; i < n; i++)
            g = gcd(g, x[i] - x[i - 1]);
 
        bool ans = false;
        for (int i = 0; i < n; i++)
        {
            if ((k % g + g) % g == (x[i] % g + g) % g) ans = true;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Nezzar and Binary String

Problem - B - Codeforces

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

이 문자열에 \(q\)개의 쿼리 \(l, r\)이 들어온다.

 

쿼리가 들어온 순간 \(s[l..r]\)은 모두 같은 문자여야 하고,

이 중 절반 미만의 문자를 다른 문자로 바꿀 수 있다고 할 때, 최종 문자열이 \(f\)가 될 수 있는지 여부를 알아내야 한다.

 

 

쿼리를 미리 받은다음, 거꾸로 \(f\)에서 \(s\)를 만들면 문제가 매우 쉬워진다.

적절한 자료구조를 이용하자.

 

#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, q;
string s, f;
 
int l[N], r[N];
 
int segTree[N * 4];
int lazy[N * 4];
 
void setLazy(int ptr, int l, int r)
{
    int val = lazy[ptr] - 1;
    lazy[ptr] = 0;
 
    segTree[ptr] = (r - l + 1) * val;
 
    if (l != r)
    {
        lazy[ptr * 2] = val + 1;
        lazy[ptr * 2 + 1] = val + 1;
    }
}
 
void update(int ptr, int l, int r, int i, int j, int val)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (r < i || j < l) return;
    if (i <= l && r <= j)
    {
        segTree[ptr] = (r - l + 1) * val;
 
        if (l != r)
        {
            lazy[ptr * 2] = val + 1;
            lazy[ptr * 2 + 1] = val + 1;
        }
 
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, j, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j, val);
 
    segTree[ptr] = segTree[ptr * 2] + segTree[ptr * 2 + 1];
}
 
int getVal(int ptr, int l, int r, int i, int j)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (r < i || j < l) return 0;
    if (i <= l && r <= j) return segTree[ptr];
 
    return getVal(ptr * 2, l, (l + r) / 2, i, j)
        + getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> q;
        cin >> s >> f;
 
        for (int i = 0; i <= n * 4; i++)
        {
            segTree[i] = lazy[i] = 0;
        }
 
        for (int i = 0; i < q; i++)
            cin >> l[i] >> r[i];
 
        bool ans = true;
 
        for (int i = 0; i < n; i++)
        {
            update(1, 1, n, i + 1, i + 1, f[i] - '0');
        }
 
        for (int i = q - 1; i >= 0; i--)
        {
            int cl = l[i], cr = r[i];
 
            int res = getVal(1, 1, n, cl, cr);
            if (res * 2 < (cr - cl + 1))
                update(1, 1, n, cl, cr, 0);
            else if (((cr - cl + 1) - res) * 2 < (cr - cl + 1))
                update(1, 1, n, cl, cr, 1);
            else ans = false;
        }
 
        for (int i = 0; i < n; i++)
        {
            int res = getVal(1, 1, n, i + 1, i + 1);
            if (res != s[i] - '0') ans = false;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

C - Nezzar and Nice Beatmap

Problem - C - Codeforces

\(n\)개의 서로 다른 점이 주어진다.

이 점들을 적절히 배열해서 차례대로 이었을 때, 두 선분의 각이 모두 예각이 될 수 있는지 여부를 알아내고,

가능하다면 잇는 순서를 출력해야 한다.

 

아무 점에서 시작해 가장 먼점을 잇는 것을 반복하면 된다.

점 A에서 가장 먼점을 B라고 하고, 점 B에서 (A를 제외한) 가장 먼점을 C라고 하자.

각 ABC가 예각이 아니라면, 점 A에서 B보다 C까지의 거리가 더 멀게 되므로, 모순이기 때문이다.

 

#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;
pll p[5001];
int cache[5001];
 
ll msq(int a, int b)
{
    return (p[a].first - p[b].first) * (p[a].first - p[b].first)
        + (p[a].second - p[b].second) * (p[a].second - p[b].second);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second;
 
    vector <int> ans;
 
    ans.push_back(1);
    cache[1] = 1;
 
    for (int i = 2; i <= n; i++)
    {
        ll d = 0;
        ll res = -1;
 
        for (int i = 1; i <= n; i++)
        {
            if (cache[i]) continue;
            ll cd = msq(ans.back(), i);
 
            if (d < cd)
            {
                d = cd;
                res = i;
            }
        }
 
        ans.push_back(res);
        cache[res] = 1;
    }
 
    for (int it : ans) cout << it << ' ';
}

---

D - Nezzar and Hidden Permutations

Problem - D - Codeforces

추가 예정

---

E - Nezzar and Tournaments

Problem - E - Codeforces

추가 예정

---

F - Nezzar and Chocolate Bars

Problem - F - Codeforces

추가 예정