Codeforces Round #655 (Div. 2)

"CodeForces"

A - Omkar and Completion

Problem - A - Codeforces

어떤 배열 \(a\)의 원소가 1000이하인 양수이고, 어떤 세 인덱스 \(x,y,z\)에 대해서도 \(a_x + a_y = a_z\)를 만족하지 않는다면, 이 배열을 complete하다고 한다.

 

주어진 \(n\)에 대해, complete한 \(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 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 << "1 ";
        cout << '\n';
    }
}

---

B - Omkar and Last Class of Math

Problem - B - Codeforces

정수 \(n\)이 주어지면, \(a+b=n\)을 만족하면서 \(LCM(a,b)\)가 가장 작은 \(a,b\)를 출력해야 한다.

 

\(n\)을 나누는 가장 작은 소수를 \(p\)라고 하자. (\(p \ne n\))

\(a = n/p, b = n - n/p\)로 설정하면 \(LCM(a,b) = b\)로 최적임을 알 수 있다.

그런 \(p\)가 존재하지 않는다면, \(a = 1, b = n-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 ett[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
 
        ll ans = n - 1;
        ll a = 1, b = n - 1;
 
        for (ll i = 2; i * i <= n; i++)
        {
            if (n % i) continue;
 
            ll ta = n / i, tb = n - ta;
            ll res = ta * tb / gcd(ta, tb);
 
            if (ans > res)
            {
                ans = res;
                a = ta, b = tb;
            }
        }
 
        cout << a << ' ' << b << '\n';
    }
}

---

C - Omkar and Baseball

Problem - C - Codeforces

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

이 순열의 부분배열 하나를 골라, 이 구간내에 있는 수를 서로 바꾸는 연산을 할 수 있다.

단, 고른 구간내에 연산 전후의 위치가 같은 수가 있어서는 안된다.

 

순열을 오름차순으로 정렬하기 위해 해야 하는 연산의 최소 횟수를 알아내야 한다.

 

먼저, 순열이 이미 정렬되어 있다면 답은 0이다.

그렇지 않다면, \(a_i \ne i\)인 가장 작은 \(i\)와 가장 큰 \(i\)를 골라, 각각 \(l,r\)이라고 하자.

구간 \([l,r]\)내에 \(a_i = i\)인 인덱스 \(i\)가 없다면, 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; }
 
int n;
int a[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];
 
        int r = n;
        for (; r >= 1; r--)
        {
            if (a[r] != r) break;
        }
 
        int l = 1;
        for (; l <= n; l++)
        {
            if (a[l] != l) break;
        }
 
        if (r < l)
        {
            cout << "0\n";
            continue;
        }
        
        bool flag = false;
        for (int i = l; i <= r; i++)
        {
            if (a[i] == i) flag = true;
        }
 
        if (flag) cout << "2\n";
        else cout << "1\n";
    }
}

---

D - Omkar and Circle

Problem - D - Codeforces

\(n\)개의 수가 원형으로 늘어져 있는 배열 \(a\)가 있다.

배열 내의 어떤 원소 \(a_i\)를 골라, 이웃한 두 원소의 합으로 대체한 다음, 이웃한 두 원소를 삭제하는 연산을 할 수 있다고 하자.

배열의 원소가 1개 남았을 때, 이 원소의 최대값을 알아내야 한다.

 

연산이 끝난 후 남은 하나의 원소는, 원래 \(a\)의 몇몇 원소의 합이 될 것이다.

관찰을 통해 최대 \(\lceil \frac n2 \rceil\)개의 원소의 합으로 이루어져 있을 수 있음을 알 수 있고, 여기에 연속된 세 원소가 포함될 수는 없다는 것을 알 수 있다.

 

연속된 세 원소를 포함하지 않는 \(\lceil \frac n2 \rceil\)개의 원소를 뽑는 경우의 수는 \(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[200001];
deque <ll> psum;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    ll sum = 0;
 
    for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
 
    if (n == 1)
    {
        cout << sum;
        return 0;
    }
 
    ll cur = 0;
    for (int i = 0; i < n / 2; i++)
    {
        psum.push_back(a[i * 2]);
        cur += a[i * 2];
    }
 
    ll ans = cur;
 
    for (int i = 0; i < n; i++)
    {
        cur -= psum.front(); psum.pop_front();
        psum.push_back(a[((n / 2 + i) * 2) % n]);
        cur += psum.back();
 
        ans = min(ans, cur);
    }
 
    cout << sum - ans;
}

---

E - Omkar and Last Floor

Problem - E - Codeforces

\(n \times m\)크기의 격자가 있다.

격자의 각 행은 \(k_i\)개의 구간으로 나누어져 있고, 각 구간에 최대 1개의 1을 써 넣을 수 있다. (나머지에는 0이 쓰인다)

 

이 때, 각 열에 쓰인 1의 개수의 제곱의 합의 최대값을 구해야 한다.

 

DP식을 다음과 같이 정의하자.

\(DP(l,r) :\) \([l,r]\)범위의 열에 대해, 위 문제의 답

 

그러면 다음과 같은 점화식을 얻을 수 있다.

\(DP(l,r) = \max_{k = l}^{r}(DP(l, k-1) + DP(k+1, r) + cnt^2)\)

(\(cnt\) : \([l,r]\)범위 내에 완전히 속하면서 \(k\)를 포함하는 구간의 수)

 

\(DP(1, m)\)을 계산하면 답이다.

 

#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;
vector <int> itv[101];
 
int dp[101][101];
int solve(int l, int r)
{
    if (l > r) return 0;
 
    int& ret = dp[l][r];
    if (ret != -1) return ret;
 
    ret = 0;
    for (int k = l; k <= r; k++)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int idx = lower_bound(itv[i].begin(), itv[i].end(), k) - itv[i].begin();
 
            int cl = itv[i][idx - 1] + 1, cr = itv[i][idx];
            if (l <= cl && cr <= r) cnt++;
        }
 
        int res = cnt * cnt + solve(l, k - 1) + solve(k + 1, r);
        ret = max(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        itv[i].push_back(0);
        int k; cin >> k;
        for (int j = 0; j < k; j++)
        {
            int l, r; cin >> l >> r;
            int sz = r - l + 1;
            itv[i].push_back(itv[i].back() + sz);
        }
    }
 
    memset(dp, -1, sizeof dp);
    cout << solve(1, m);
}

---

F - Omkar and Modes

Problem - F - Codeforces

추가 예정