Codeforces Round #686 (Div. 3)

A - Special Permutation

Problem - A - Codeforces

\(n\)길이의 순열 \(a\)를 출력해야 하는데, 모든 인덱스에 대해 \(a_i \ne 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        for (int i = 0; i < n; i++) cout << (i + 1) % n + 1 << ' ';
        cout << '\n';
    }
}

---

B - Unique Bid Auction

Problem - B - Codeforces

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

어떤 \(a_i\)가 배열내에서 유일하고, 유일한 값중 가장 작은 값이라면 \(i\)를 출력한다.

그런 \(a_i\)가 없다면 -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;
map <int, int> mp;
int a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        mp.clear();
 
        int ans = -1;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            mp[a[i]]++;
        }
 
        for (auto it : mp)
        {
            if (it.second > 1) continue;
            for (int i = 0; i < n; i++)
            {
                if (a[i] == it.first) ans = i + 1;
            }
            break;
        }
 
        cout << ans << '\n';
    }
}

---

C - Sequence Transformation

Problem - C - Codeforces

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

이 배열에 있는 수 \(x\)를 하나 골라서, 배열에 \(x\)만 남아있도록 해야 한다.

그러기 위해서 연속된 인덱스의 원소를 삭제하는 연산을 할 수 있는데, 이 원소들 중 하나라도 \(x\)가 되어서는 안된다.

 

\(x\)를 적절히 골랐을 때, 위의 조건을 만족하도록 하는 연산의 최소횟수를 알아내야 한다.

 

배열에서 모든 연속된 수들을 압축해 1개의 수로 만들자.

이 작업 이후, \(x\)를 골랐을 때 필요한 연산 횟수는

\(x\)의 개수 +1 - (\(x\)가 첫 원소인가 ? 1 : 0) - (\(x\)가 마지막 원소인가? 1 : 0) 이다.

 

#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];
map <int, int> mp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        mp.clear();
 
        int last = -1;
 
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (i == 0)
            {
                last = a[i];
                mp[a[i]]++;
            }
 
            if (a[i] != last)
            {
                last = a[i];
                mp[a[i]]++;
            }
        }
 
        mp[a[0]]--;
        mp[a[n - 1]]--;
 
        int ans = 987654321;
        for (int i = 0; i < n; i++)
        {
            int res = max(0, mp[a[i]] + 1);
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

D - Number into Sequence

Problem - D - Codeforces

\(n\)이 주어지고, 다음을 만족하는 \(k\)길이의 수열 \(a\)를 찾아야 한다.

 

1. 각 \(a_i\)는 1보다 크다.

2. 수열의 모든 원소의 곱은 \(n\)이다.

3. \(a_{i+1}\)은 \(a_i\)로 나누어 떨어진다.

4. \(k\)는 가능한 최대값이다.

 

 

\(n\)을 소인수분해 하자.

가장 많이 포함된 소인수가 \(x\)이고, \(y\)번 포함되어 있다고 하면

\(k\)의 최대값은 \(y\)이고, 해당하는 수열은

\(x, x, \cdots, x, \frac{n}{x^{y-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; }
 
ll n;
map <ll, ll> mp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
        cin >> n;
 
        ll tn = n;
        for (ll i = 2; i * i <= n; i++)
        {
            while (tn % i == 0)
            {
                mp[i]++;
                tn /= i;
            }
        }
 
        if (tn != 1) mp[tn]++;
 
        ll d = -1, cnt = 0;
        for (auto it : mp)
        {
            if (it.second > cnt)
            {
                d = it.first;
                cnt = it.second;
            }
        }
 
        tn = n;
 
        cout << cnt << '\n';
        for (int i = 0; i < cnt - 1; i++)
        {
            cout << d << ' ';
            tn /= d;
        }
 
        cout << tn << '\n';
    }
}

---

E - Number of Simple Paths

Problem - E - Codeforces

\(n\)개의 정점과 \(n\)개의 간선으로 이루어진 그래프가 주어진다.

이 그래프에서 서로 다른 단순 경로의 개수를 구해야 한다.

 

 

이 그래프는 1개의 사이클을 가진다.

이 그래프가 사이클을 가지지 않는 트리였다고 하면,

가능한 단순 경로를 (시작점, 끝점)으로 표현할 수 있기 때문에 개수가 \(\frac{n(n-1)}{2}\)개임을 쉽게 알 수 있다.

하지만 이 그래프가 사이클을 가지기 때문에, (시작점, 끝점)으로 나타내어지는 경로가 2개일 수 있다.

 

따라서 \(n(n-1)\)에서 경로가 2개가 아닌 (시작점, 끝점) 쌍의 개수를 빼면 답이 됨을 알 수 있다.

이 그래프는 사이클을 하나 가지고, 그 사이클에 포함되는 정점을 루트로 하여 뻗어나가는 트리의 형태로 이루어져 있다.

이 각각의 트리에 해당되는 정점들 사이에서는 경로가 1개만 존재하므로, 트리의 크기가 \(s\)라면 \(\frac{s(s-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; }
 
ll n;
vector <int> graph[200001];
 
int cache[200001];
int isCircle[200001];
 
void DFS(int v, int p)
{
    cache[v] = 1;
 
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        if (cache[nv])
        {
            if (cache[nv] == 1)
            {
                isCircle[nv] = 2;
                isCircle[v] = 1;
            }
        }
        else DFS(nv, v);
 
        if (isCircle[nv] == 1 && isCircle[v] != 2)
            isCircle[v] = 1;
    }
 
    cache[v] = 2;
}
 
int DFS2(int v, int p)
{
    int res = 1;
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        if (isCircle[nv]) continue;
 
        res += DFS2(nv, v);
    }
 
    return res;
}
 
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++)
        {
            graph[i].clear();
            cache[i] = 0;
            isCircle[i] = 0; 
        }
 
        for (int i = 0; i < n; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        ll ans = n * (n - 1);
 
        DFS(1, 0);
        for (int i = 1; i <= n; i++)
        {
            if (isCircle[i])
            {
                ll res = DFS2(i, 0);
                ans -= res * (res - 1) / 2;
            }
        }
 
        cout << ans << '\n';
    }
}

---

F - Array Partition

Problem - F - Codeforces

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

이 배열을 세 부분으로 나눠서 각각의 크기를 \(x,y,z\)라고 하자.

\(\max(1,x) = \min(x+1,x+y) = \max(x+y+1,n)\)이 되도록 할 수 있는지 알아내고, 가능하면 그 해를 출력해야 한다.

 

 

배열의 각 원소 \(a_i\)에 대하여, \(a_i\)가 \(y\)부분의 최소값에 해당된다고 가정하자.

그러면 \(x\)부분과 \(z\)부분의 최대값이 \(a_i\)가 되어야 하고, 가능하면 \(x\)와 \(z\)의 크기가 클 수록 이득이라는 사실을 알 수 있다.

이는 \(a\)에서 왼쪽에서부터의 누적 최대값과, 오른쪽에서부터의 누적 최대값을 미리 계산해놓은 다음, 이분탐색으로 각각 알아낼 수 있다.

마지막으로 \(y\)에 해당되는 부분의 최소값이 실제로 \(a_i\)인지 확인해야 하는데, 최소값 세그먼트 트리를 하나 만들면 쉽게 확인할 수 있다.

위를 모두 만족하면 해를 찾은 것이다.

 

이분탐색, 세그먼트 트리 모두 \(O(\log n)\)이고, 이를 \(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; }
 
const int N = 200010;
 
int n;
int a[N];
int lmax[N];
int rmax[N];
int segTree[N * 4];
void update(int ptr, int l, int r, int i, int val)
{
    if (i < l || r < i) return;
    if (l == r)
    {
        segTree[ptr] = val;
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
 
    segTree[ptr] = min(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
int getVal(int ptr, int l, int r, int i, int j)
{
    if (j < l || r < i) return 1e9 + 1;
    if (i <= l && r <= j) return segTree[ptr];
 
    return min(getVal(ptr * 2, l, (l + r) / 2, i, j),
        getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j));
}
 
vector <int> x;
vector <int> idx[N];
 
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 + 1; i++)
        {
            lmax[i] = rmax[i] = 0;
            idx[i].clear();
        }
 
        for (int i = 1; i <= n * 4; i++) segTree[i] = 1e9 + 1;
        x.clear();
 
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            x.push_back(a[i]);
        }
 
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
 
        for (int i = 1; i <= n; i++)
        {
            a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin() + 1;
            idx[a[i]].push_back(i);
            update(1, 1, n, i, a[i]);
        }
 
        for (int i = 1; i <= n; i++)
            lmax[i] = max(lmax[i - 1], a[i]);
 
        for (int i = n; i >= 1; i--)
            rmax[i] = max(rmax[i + 1], a[i]);
 
        bool hasAns = false;
        int ans[3];
 
        for (int i = 1; i <= n; i++)
        {
            if (idx[i].size() < 3) continue;
            for (int j = 1; j + 1 < idx[i].size(); j++)
            {
                int cidx = idx[i][j];
 
                int cl = 0;
                int cr = n + 1;
 
                int l, r;
                l = 0, r = cidx;
                while (l + 1 < r)
                {
                    int m = (l + r) / 2;
                    if (lmax[m] <= i) l = m;
                    else r = m;
                }
                cl = l;
 
                l = cidx, r = n + 1;
                while (l + 1 < r)
                {
                    int m = (l + r) / 2;
                    if (rmax[m] <= i) r = m;
                    else l = m;
                }
                cr = r;
 
                if (cl == 0 || cr == n + 1) continue;
                if (lmax[cl] != i || rmax[cr] != i) continue;
 
                int res = getVal(1, 1, n, cl + 1, cr - 1);
                if (res == i)
                {
                    hasAns = true;
                    ans[0] = cl;
                    ans[1] = cr - cl - 1;
                    ans[2] = n - cr + 1;
                }
            }
        }
 
        if (!hasAns)
        {
            cout << "NO\n";
            continue;
        }
 
        cout << "YES\n";
        cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << '\n';
    }
}