Codeforces Round #662 (Div. 2)

A - Rainbow Dash, Fluttershy and Chess Coloring

Problem - A - Codeforces

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

이 격자를 한 사람은 파란색으로, 나머지 사람은 노란색으로 번갈아가며 칠해서 격자를 체스판 무늬로 만드려고 한다.

 

단 격자를 칠할 때, 새로 칠하는 칸들은 모두 이전에 칠해진 칸들과 인접해 있어야 한다.

초기에 격자 바깥에 있는 칸들이 이전에 칠해져있었다고 가정한다.

 

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

 

관찰을 통해, \(\lfloor \frac n2 \rfloor + 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--)
    {
        int n; cin >> n;
        cout << n / 2 + 1 << '\n';
    }
}

---

B - Applejack and Storages

Problem - B - Codeforces

\(n\)개의 나무판자가 주어진다. 각각의 나무판자는 \(a_i\)의 길이를 가진다.

 

\(q\)개의 쿼리가 주어지고, 각 쿼리마다 \(x\)길이의 나무판자를 추가하거나 제거할 수 있다.

나무판자를 추가/제거한 후에, 남아있는 나무판자로 1개의 정사각형과 1개의 직사각형을 만들 수 있는지 여부를 알아내야 한다.

 

각 길이의 나무판자가 현재 몇개 남아있는지 저장함과 동시에, 같은 길이의 나무판자 4개 세트의 개수, 2개 세트의 개수를 저장하자.

현재 4개 세트의 개수가 1개 이상이면서, 2개 세트의 개수가 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 len[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    int four = 0, two = 0;
 
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        len[a]++;
 
        if (len[a] % 2 == 0) two++;
        if (len[a] % 4 == 0) four++;
    }
 
    int q; cin >> q;
    while (q--)
    {
        char c; int a;
        cin >> c >> a;
 
        if (c == '+')
        {
            len[a]++;
 
            if (len[a] % 2 == 0) two++;
            if (len[a] % 4 == 0) four++;
        }
        else
        {
            if (len[a] % 2 == 0) two--;
            if (len[a] % 4 == 0) four--;
            
            len[a]--;
        }
 
        if (four > 0 && two - 2 >= 2) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

C - Pinkie Pie Eats Patty-cakes

Problem - C - Codeforces

\(n\)개의 케이크가 있다. 각 케이크는 종류 \(a_i\)를 가진다.

 

이 케이크들을 재배열해서, 같은 종류의 두 케이크 사이의 거리를 최대화 하려고 한다. 이 때 그 값을 구해야 한다.

 

 

같은종류가 가장 많은 케이크의 개수(\(mx\))와, 그 개수를 가지는 케이크의 종류의 수(\(mx_{cnt}\))를 알아내자.

\(n\)개의 칸에 \(mx_{cnt}\)개의 케이크를 맨 오른쪽에 몰아넣고, 남은 칸을 \(mx-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;
int cnt[100001];
 
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;
        for (int i = 0; i < n; i++)
        {
            int a; cin >> a;
            cnt[a]++;
        }
 
        int mx = *max_element(cnt + 1, cnt + n + 1);
 
        int mx_cnt = 0;
        for (int i = 1; i <= n; i++) if (cnt[i] == mx) mx_cnt++;
 
        int res = (n - mx_cnt) / (mx - 1) - 1;
        cout << res << '\n';
    }
}

---

D - Rarity and New Dress

Problem - D - Codeforces

\(n \times m\)크기의 격자가 주어진다. 각 격자에는 옷감의 종류를 나타내는 영어 소문자가 적혀 있다.

이 격자에서 옷감을 잘라내려고 하는데, 다음 조건을 만족해야 한다.

 

1. 모두 같은 옷감으로 이루어져 있어야 한다.

2. 45도 기울어진 정사각형 모양이어야 한다.

 

위의 조건을 만족하면서 잘라낼 수 있는 옷감의 경우의 수를 구해야 한다.

 

각 칸에 대해, 같은 옷감에 좌우로 연속되어 이루어져 있는 최대 길이를 \(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; }
 
int n, m;
string board[2001];
ll same[2001][2001];
ll from_up[2001][2001];
ll from_down[2001][2001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> board[i];
        int st = 0;
        int cnt = 1;
        for (int j = 1; j < m; j++)
        {
            if (board[i][j] != board[i][j - 1])
            {
                for (int k = st; k < j; k++)
                    same[i][k] = min(k - st, j - 1 - k) + 1;
 
                st = j;
                cnt = 1;
            }
            else cnt++;
        }
 
        for (int k = st; k < m; k++)
            same[i][k] = min(k - st, m - 1 - k) + 1;
    }
 
    for (int j = 0; j < m; j++) from_up[0][j] = 1;
    for (int i = 1; i < n; i++) for (int j = 0; j < m; j++)
    {
        if (board[i][j] == board[i - 1][j])
            from_up[i][j] = min(same[i][j], from_up[i - 1][j] + 1);
        else
            from_up[i][j] = 1;
    }
 
    for (int j = 0; j < m; j++) from_down[n - 1][j] = 1;
    for (int i = n - 2; i >= 0; i--) for (int j = 0; j < m; j++)
    {
        if (board[i][j] == board[i + 1][j])
            from_down[i][j] = min(same[i][j], from_down[i + 1][j] + 1);
        else
            from_down[i][j] = 1;
    }
 
    ll ans = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        ans += min(from_up[i][j], from_down[i][j]);
 
    cout << ans;
}

---

E - Twilight and Ancient Scroll (harder version)

Problem - E2 - Codeforces

추가 예정