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

A - Prison Break

Problem - A - Codeforces

\(n \times m\)크기의 감옥이 있고, 각 \(nm\)개의 정수 좌표에 죄수들이 있다.

이 감옥의 \((r,c)\) 위치에 탈출구가 있고, 각 죄수는 1초에 상하좌우 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, m, r, c; cin >> n >> m >> r >> c;
        cout << max(r - 1, n - r) + max(c - 1, m - c) << '\n';
    }
}

---

B - Repainting Street

Problem - B - Codeforces

\(n\)개의 집으로 이루어진 거리가 있다.

\(i\)번째 집은 현재 \(c_i\)색깔로 칠해져 있다.

 

이 집들을 모두 한가지 색으로 통일하려고 하는데, 한번의 색칠로 연속된 \(k\)개의 집을 색칠할 수 있다.

 

이 때 필요한 최소 색칠 횟수를 구해야 한다.

 

색이 많아도 100가지이기 때문에, 모든 색에 대해서 색칠 횟수를 구한다음 그중 최소값이 답이다.

 

#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 k, n;
int c[100001];
 
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 >> c[i];
 
        int ans = 987654321;
        for (int cl = 1; cl <= 100; cl++)
        {
            int res = 0;
 
            int idx = 0;
            while (idx < n)
            {
                if (c[idx] == cl)
                {
                    idx++;
                    continue;
                }
                else
                {
                    idx += k;
                    res++;
                }
            }
 
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

A - Bouncing Ball

Problem - A - Codeforces

공튀기기 게임을 하려고 한다.

이 게임을 통과하기 위해서는 공이 첫 \(p\)번째 칸에 있는 블록을 밟은 다음, \(k\)칸씩 떨어져 있는 블록을 모두 밟고 맵 밖으로 나가야 한다.

현재 맵의 각 칸에는 블록이 있을수도 있고, 없을 수도 있다.

 

맵을 통과하기 위해 다음과 같은 변화를 줄 수 있다.

1. \(x\)의 비용으로 첫 칸을 없앤다. 원래 두번째 칸이었던 칸이 첫 칸이 된다. 남은 칸이 \(p\)개 이하일 때는 사용할 수 없다.

2. \(y\)의 비용으로 블록이 없는 칸에 블록을 만든다.

 

맵을 통과하기 위해 필요한 최소 비용을 구해야 한다.

 

1부터 \(k-1\)까지의 모든 수 \(r\)에 대해, 각 칸의 번호를 \(k\)로 나눴을 때 나머지가 \(r\)인 모든 칸 중 블록이 없는 칸의 개수를 저장하자.

 

그러면 현재까지 지운 칸의 개수가 주어졌을 때 블록 추가만 이용해 게임을 통과할 수 있게 하는 비용을 \(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 n, p, k;
string s;
int x, y;
 
int cnt[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> p >> k; p--;
        cin >> s;
        cin >> x >> y;
 
        for (int i = 0; i < k; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '0') cnt[i % k]++;
        }
 
        int ans = numeric_limits<int>::max();
 
        for (int i = 0; i < p; i++)
        {
            if (s[i] == '0') cnt[i % k]--;
        }
 
        int add = 0;
        for (int i = p; i < n; i++)
        {
            int res = cnt[i % k] * x + add;
            ans = min(ans, res);
 
            add += y;
            if (s[i] == '0') cnt[i % k]--;
        }
 
        cout << ans << '\n';
    }
}

---

B - XOR-gun

Problem - B - Codeforces

비내림차순 수열 \(a\)가 주어지고, 이 수열에 다음과 같은 연산을 사용할 수 있다.

- 연속한 두 원소를 골라 삭제하고, 그 자리에 두 원소를 XOR한 값을 추가한다.

 

이 연산을 사용해 이 수열을 비내림차순이 아니도록 바꾸려고 할 때, 필요한 최소 연산 횟수를 알아내야 한다.

 

어떤 연속된 3개의 수의 최대 비트가 같다고 하자. 그러면 우리는 뒤 2개의 수를 XOR함으로써 수열을 비내림차순으로 만들 수 있다.

그런 수가 없다면, 이 수열의 길이는 60 이하이다. \(O(N^3)\) 또는 \(O(N^4)\) 완전탐색으로 답을 알아내면 된다.

 

#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[100001];
int mb[100001];
int pxor[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pxor[i] = pxor[i - 1] ^ a[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 30; j >= 0; j--)
        {
            if (a[i] & (1 << j))
            {
                mb[i] = j;
                break;
            }
        }
 
        if (i >= 3)
        {
            if (mb[i - 2] == mb[i - 1] && mb[i - 1] == mb[i])
            {
                cout << 1;
                return 0;
            }
        }
    }
 
    int ans = 987654321;
 
    for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++)
    {
        for (int k = j + 1; k <= n; k++) for (int l = k; l <= n; l++)
        {
            int lval = pxor[j] ^ pxor[i - 1];
            int rval = pxor[l] ^ pxor[k - 1];
 
            if (lval > rval)
            {
                int res = (j - i) + (l - k);
                ans = min(ans, res);
            }
        }
    }
 
    if (ans == 987654321) ans = -1;
    cout << ans;
}

---

C - New Game Plus!

Problem - C - Codeforces

\(n\)마리의 보스를 죽이는 게임을 하려고 한다. 보스를 죽이는 순서는 상관이 없다.

\(i\)번째 보스를 죽이면, 현재 가지고 있는 보스 보너스 만큼의 점수를 얻은 다음, 보스 보너스에 \(c_i\)가 추가된다.

또, 최대 \(k\)번 현재 보스 보너스를 0으로 바꿀 수 있다고 할 때, 얻을 수 있는 최대 점수를 구해야 한다.

 

문제를 다음과 같이 생각할 수 있다.

보스를 \(k+1\)개의 그룹으로 나누었을 때, 얻을 수 있는 최대 점수.

 

각 그룹의 보스들에 대해 생각해 보면, \(c_i\)가 큰 보스부터 죽이는것이 무조건 이득임을 알 수 있다.

따라서 보스의 \(c_i\)가 큰 순으로 정렬한 다음, 차례대로 보스들을 최대 \(k+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, k;
ll c[500001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> c[i];
    sort(c, c + n);
    reverse(c, c + n);
 
    priority_queue<ll> pq;
    for (int i = 0; i < k + 1; i++) pq.push(0);
 
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll cur = pq.top(); pq.pop();
        ans += cur;
        pq.push(cur + c[i]);
    }
 
    cout << ans;
}

---

D - Cakes for Clones

Problem - D - Codeforces

추가 예정

---

E - XOR-ranges

Problem - E - Codeforces

추가 예정