Codeforces Round #642 (Div. 3)

A - Most Unstable Array

Problem - A - Codeforces

정수 \(n\)과 \(m\)이 주어진다.

 

길이가 \(n\)이고 원소들의 합이 \(m\)인 수열을 만들려고 한다. 각 원소는 모두 0 이상인 정수이다.

이때 각각의 인접한 원소의 차의 합이 최대값을 알아내야 한다.

 

먼저 \(n\)이 1일 때 답은 0이고, \(n\)이 2일 때 답이 \(m\)임은 쉽게 알 수 있다.

\(n\)이 3 이상일 때는 \(\{0,m,0,0,\cdots\}\) 와 같이 수열을 만들었을 때 \(2m\)이 답이 되고,

이보다 값이 큰 경우는 존재하지 않는다.

 

#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, m; cin >> n >> m;
        if (n == 1) cout << "0\n";
        else if (n == 2) cout << m << '\n';
        else cout << m * 2 << '\n';
    }
}

---

B - Two Arrays And Swaps

Problem - B - Codeforces

수열 \(a\)와 \(b\)가 주어진다.

 

\(a\)와 \(b\)의 원소를 서로 바꾸는 연산을 최대 \(k\)번 해서 얻을 수 있는 \(a\)의 원소의 합의 최대값을 알아내야 한다.

 

그리디하게, \(a\)의 가장 작은 원소와 \(b\)의 가장 큰 원소를 \(k\)번 바꾸면 된다.

\(a\)의 가장 작은 원소가 \(b\)의 가장 큰 원소보다 크다면 바꾸지 않는다.

 

\(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, k;
int a[31], b[31];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        priority_queue <int> qa, qb;
        cin >> n >> k;
 
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            qa.push(-x);
        }
 
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x;
            qb.push(x);
        }
 
        for (int i = 0; i < k; i++)
        {
            int ta = -qa.top();
            int tb = qb.top();
 
            if (ta >= tb) break;
            
            qa.pop(); qb.pop();
 
            qa.push(-tb);
            qb.push(ta);
        }
 
        int ans = 0;
        while (!qa.empty())
        {
            ans -= qa.top();
            qa.pop();
        }
 
        cout << ans << '\n';
    }
}

---

C - Board Moves

Problem - C - Codeforces

\(n \times n\)크기의 격자가 있고, 격자의 각 칸에 말이 하나씩 있다.

한 번의 연산으로 하나의 말을 8방향 (상하좌우, 대각선)으로 움직일 수 있다고 할 때,

모든 말을 하나의 칸에 모으는 최소 연산 횟수를 구해야 한다.

 

\(n\)이 홀수이므로 말을 모두 정 가운데 칸에 모으는 것이 최적임을 알 수 있다.

\(O(n) 또는 O(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--)
    {
        ll n; cin >> n;
        ll ans = 0;
        for (ll i = 1; i <= n / 2; i++)
        {
            ans += i * ((2 * i + 1) * (2 * i + 1) - (2 * i - 1) * (2 * i - 1));
        }
        cout << ans << '\n';
    }
}

---

D - Constructing the Array

Problem - D - Codeforces

\(n\)길이의 배열 \(a\)를 다음과 같은 규칙으로 만들어야 한다.

초기에 배열은 모두 비어있다.

 

1. 배열의 가장 긴 비어있는 부분 배열을 고른다. 가장 긴 비어있는 부분 배열이 여러개라면 가장 왼쪽을 고른다.

2. 고른 부분 배열의 가운데에 지금까지 배열에 넣지 않았던 가장 작은 자연수를 넣는다.

 

\(n\)이 주어지면 만들어지는 배열을 출력해야 한다.

 

set이나 pq에 {비어있는 부분 배열의 길이, 인덱스}를 전자는 큰 순으로, 후자는 작은 순으로 저장한다.

가장 앞에 있는 원소를 골라 중앙에 수를 넣으면 빈 공간이 둘로 나눠지는데, 각각 자료구조에 넣는걸 반복하면 된다.

 

#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 ans[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        priority_queue<pii> pq;
        pq.push({ n, 0 });
 
        for (int i = 1; i <= n; i++)
        {
            pii tmp = pq.top(); pq.pop();
            int sz = tmp.first;
            int idx = -tmp.second;
 
            ans[idx + (sz - 1) / 2] = i;
            if (sz > 2) pq.push({ (sz - 1) / 2, -idx });
            if (sz > 1) pq.push({ sz / 2, -(idx + (sz - 1) / 2 + 1) });
        }
 
        for (int i = 0; i < n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

E - K-periodic Garland

Problem - E - Codeforces

\(n\)개의 램프가 주어진다. 램프는 초기에 꺼져있거나 켜져있다.

 

이 램프들을 \(k\)-periodic 상태로 만드려고 하는데,

\(k\)-periodic 상태는 모든 인접한 켜진 램프 사이의 거리가 \(k\)가 된 상태를 말한다.

 

초기 램프의 상태가 주어졌을 때, \(k\)-periodic 상태로 만들기 위해 상태를 바꿔야 하는 램프의 개수의 최소값을 알아내야 한다.

 

먼저 거리가 \(k\)인 램프들로 이루어진 \(k\)개의 묶음을 만들자.

각각의 묶음에서 켜진 램프들이 존재할 때의 답의 최소값을 계산하면 될 것이다.

 

각 묶음에서의 답은 (연속된 꺼진 램프), (연속된 켜진 램프), (연속된 꺼진 램프) (000...111...000...) 과 같은 상태로 만들기 위해 바꿔야 하는 램프의 최소값이 되는데,

 

간단히 세그먼트 트리와 같은 자료구조로 \(O(n\log n)\)에 해결하거나, DP로 \(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; }
 
const int N = 1000001;
const int INF = 987654321;
int n, k;
string s;
 
int segTree[N * 4];
void update(int ptr, int l, int r, int i, int val)
{
    if (l > i || 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 (l > j || r < i) return INF;
    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)
    );
}
 
int calc(vector <int>& v)
{
    for (int i = 0; i < v.size() * 4; i++) segTree[i] = INF;
    for (int i = 0; i < v.size(); i++)
    {
        int val = (i + 1) - v[i] + v.back() - v[i];
        // v[i]까지 0의 개수 + v[i+1]이후의 1의 개수
        update(1, 0, v.size() - 1, i, val);
    }
 
    int ans = INF;
    for (int i = 1; i < v.size(); i++)
    {
        int res = getVal(1, 0, v.size() - 1, i, v.size() - 1);
 
        res += v[i - 1] - (i - v[i - 1]);
        ans = min(ans, res);
    }
 
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cin >> s;
 
        int acnt[2] = { 0,0 };
        for (char c : s)
            acnt[c - '0']++;
 
        int ans = acnt[1];
        for (int i = 0; i < k; i++)
        {
            int cnt[2] = { 0,0 };
 
            vector <int> vec;
            vec.push_back(0);
 
            for (int j = i; j < s.size(); j += k)
            {
                int num = s[j] - '0';
                cnt[num]++;
                vec.push_back(num + vec.back());
                // 1의 개수에 대한 psum
            }
 
            int tmp = calc(vec);
            int res = acnt[1] - cnt[1] + tmp;
 
            ans = min(ans, res);
        }
        cout << ans << '\n';
    }
}

---

F - Decreasing Heights

Problem - F - Codeforces

\(n \times m\) 크기로 이루어진 판이 있고, 각 격자마다 현재 높이가 주어진다.

현재 칸에서 오른쪽 또는 아래쪽으로만 이동할 수 있고, 현재 칸의 높이가 \(x\)라면, 다음 칸의 높이가 \(x+1\)어야 이동할 수 있다.

 

\((1,1)\)에서 \((n,m)\)까지 이동하려고 하는데, 위와 같은 규칙으로 이동할 수 있도록 각 칸의 높이를 원하는 만큼 미리 줄여 놓을 수 있다.

 

\((n,m)\) 까지 이동하는데 줄여야 하는 높이의 최소값을 알아내야 한다.

 

시작부분의 높이를 미리 정해 놓는다면, \((n,m)\)까지 이동하는데 줄여야 하는 높이의 최소값은 간단한 \(O(nm)\) DP로 알 수 있게 된다.

 

가능한 시작부분의 높이의 경우의 수는 어떻게 될까?

문제의 답이 되는 어떤 경로가 칸 \((i,j)\)를 지나간다고 하자.

그러면 시작지점의 높이는 최소 (칸 \((i,j)\)의 높이 - \((i+j-2)\)) 가 되어야 함을 알 수 있다.

 

모든 칸에 대해, 시작지점의 높이를 위 식에 따라 설정한 뒤, 각각 DP로 답을 계산해 최소값을 구하면 답이다.

 

시간복잡도는 \(O(n^2m^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; }
 
const ll INF = 1e18;
int n, m;
ll a[101][101];
ll dp[101][101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
            cin >> a[i][j];
 
        ll ans = INF;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            ll s = a[i][j] - i - j;
            for (int x = 0; x < n; x++) for (int y = 0; y < m; y++)
            {
                ll h = s + x + y;
                if (a[x][y] < h)
                {
                    dp[x][y] = INF;
                    continue;
                }
 
                ll tmp = 0;
                if (x)
                {
                    if (y) tmp = min(dp[x - 1][y], dp[x][y - 1]);
                    else tmp = dp[x - 1][y];
                }
                else if (y) tmp = dp[x][y - 1];
 
                if (tmp == INF) dp[x][y] = INF;
                else dp[x][y] = a[x][y] - h + tmp;
            }
 
            ans = min(ans, dp[n - 1][m - 1]);
        }
        
        cout << ans << '\n';
    }
}