Codeforces Round #634 (Div. 3)

A - Candies and Two Sisters

Problem - A - Codeforces

Alice, Betty 두 사람에게 \(n\)개의 사탕을 나눠주려고 한다.

Alice에게 \(a\)개의 사탕을, Betty에게 \(b\)개의 사탕을 나눠 주려고 할 때, 다음과 같은 조건을 만족해야 한다.

1. \(a \gt 0\)

2. \(b \gt 0\)

3. \(a \gt b\)

4. \(a+b=n\)

 

이 때, 사탕을 나눠주는 모든 경우의 수를 알아내야 한다.

Betty가 가질 수 있는 사탕의 수의 범위는 \(1 \le b \le (n-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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        cout << (n + 1) / 2 - 1 << '\n';
    }
}

---

B - Construct the String

Problem - B - Codeforces

3개의 양수 \(n, a, b\)가 주어진다.

길이 \(n\)인 문자열 하나를 만들어야 하는데,
이 문자열의 모든 길이 \(a\)의 부분문자열은 정확히 \(b\)개의 서로 다른 철자를 가져야 한다.

\(b\)개의 서로 다른 철자를 1번씩 사용한 문자열을 만들고,
이 문자열을 길이가 \(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, a, b;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> a >> b;
        for (int i = 0; i < n; i++)
            cout << (char)(i % b + 'a');
        cout << '\n';
    }
}

---

C - Two Teams Composing

Problem - C - Codeforces

\(n\)명의 학생이 있고, 이 학생들을 두 팀으로 나누려고 한다.

 

각 학생은 가지고 있는 능력을 나타내는 수 \(a_i\)가 주어지는데,

한 팀은 모두 같은 능력을, 다른 한팀은 서로 모두 다른 능력을 가져야 한다.

또, 두 팀이 같은 수의 학생을 가져야 한다.

 

위의 조건을 만족하면서 팀을 만들 때, 팀이 가질 수 있는 학생 수의 최대값을 구해야 한다.

 

각 \(a_i\)에 대해서, 서로 다른 \(a_i\)의 개수와 같은 \(a_i\)의 개수의 최대값을 각각 저장하자.

이를 각각 \(x, y\)라고 할 때, 답은 \(max(min(x-1,y),min(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; }
 
int n;
map <int, int> mp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int a; cin >> a;
            mp[a]++;
        }
 
        int mx = 0;
        for (auto it : mp) mx = max(mx, it.second);
 
        cout << max(min(mx, (int)mp.size() - 1),
            min(mx - 1, (int)mp.size())) << '\n';
    }
}

---

D - Anti-Sudoku

Problem - D - Codeforces

꽉 채워진 스도쿠가 주어진다.

 

이 스도쿠에서 최대 9개의 숫자를 변경해서 다음과 같은 조건을 만족하도록 하고 싶다.

 

1. 모든 행에 겹치는 수가 적어도 하나 있다.

2. 모든 열에 겹치는 수가 적어도 하나 있다.

3. 모든 3x3박스에 겹치는 수가 적어도 하나 있다.

 

조건에 맞는 변경된 스도쿠를 출력해야 한다.

 

스도쿠의 모든 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; }
 
string sdk[9];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        for (int i = 0; i < 9; i++)
            cin >> sdk[i];
 
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (sdk[i][j] == '1') cout << '2';
                else cout << sdk[i][j];
            }
            cout << '\n';
        }
    }
}

---

E - Three Blocks Palindrome

Problem - E2 - Codeforces

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

 

\(x\)개의 \(n\), \(y\)개의 \(m\), \(x\)개의 \(n\)을 순서대로 붙여 만들 수 있는 수열을 "3블록 팰린드롬"이라고 하자.

 

이 수열에서 가장 긴 3블록 팰린드롬의 길이를 구해야 한다.

 

각 수에 대해 나타나는 인덱스들을 저장해 놓고,

인덱스 \(1\)부터 \(i\)까지 각각의 수가 몇 번 등장하는지도 저장해놓자. 부분합을 이용하면 쉽게 할 수 있다.

 

팰린드롬의 양쪽에서 등장하는 수 (위 정의에서의 \(n\))와 왼쪽과 오른쪽에서 몇개의 수를 선택할지 정해 놓으면,

그 사이에 있는 구간에서 가장 많이 등장하는 수가 몇번 등장하는지 전처리한 부분합을 이용해 \(O(AL)\)에 알 수 있다.

(\(AL\) = 서로 다른 수의 개수)

 

인덱스를 모두 탐색하는데 \(O(n)\)의 시간이 걸리므로, 총 시간복잡도 \(O(n \cdot AL)\)에 문제를 해결할 수 있다.

 

#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 psum[201][200001];
vector <int> idx[201];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        for (int k = 1; k <= 200; k++) idx[k].clear();
 
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            idx[a[i]].push_back(i);
            for (int k = 1; k <= 200; k++)
            {
                if (a[i] == k) psum[k][i] = psum[k][i - 1] + 1;
                else psum[k][i] = psum[k][i - 1];
            }
        }
 
        int ans = 0;
        for (int k = 1; k <= 200; k++)
        {
            ans = max(ans, (int)idx[k].size());
            if (idx[k].size() < 2) continue;
 
            for (int i = 0; i < idx[k].size() / 2; i++)
            {
                int idx_front = idx[k][i];
                int idx_back = idx[k][idx[k].size() - 1 - i];
 
                int mid_max = 0;
                for (int j = 1; j <= 200; j++)
                {
                    int res = psum[j][idx_back - 1] - psum[j][idx_front];
                    mid_max = max(mid_max, res);
                }
 
                ans = max(ans, mid_max + (i + 1) * 2);
            }
        }
 
        cout << ans << '\n';
    }
}

---

F - Robots on a Grid

Problem - F - Codeforces

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

각 격자는 검은색 또는 흰색으로 칠해져 있고, 다음으로 이동할 방향이 적혀져 있다. (상하좌우)

 

이 격자에 로봇을 놓으려고 한다.

로봇은 1초에 한번씩 격자에 쓰여져있는 방향으로 이동하는데, 동시에 두 로봇이 같은 칸에 존재하는 경우가 있으면 안된다.

 

이 때, 놓을 수 있는 로봇의 최대 수와, 로봇을 최대로 놓았을 때 초기위치가 검은색 칸인 로봇의 최대 수를 구해야 한다.

 

먼저, 충분한 시간이 지나면 이 로봇들은 최종적으로 어떤 루프를 무한히 돈다는 사실을 알 수 있다.

따라서 최대 놓을 수 있는 로봇의 수는 이 루프들의 길이의 합임을 알 수 있다.

 

다음으로, 루프에 속하지 않지만 한 루프를 향하는 가지들에 속하는 칸들이 있다.

루프에 이미 로봇들이 배치되어 있다고 한다면, 이 칸에 놓은 로봇은 충분한 시간이 지난 후에 루프에 원래 있던 로봇들 중 하나와 겹치게 될 것이다. 어떤 로봇과 겹치게 되는지는 루프까지의 거리를 이용해 계산할 수 있다.

 

그렇게 로봇을 두었을 때 최종적으로 겹치게 되는 모든 칸에 대하여, 이 중 한칸이라도 검은색 칸이 있다면 이 곳에 로봇을 놓으면 검은색 칸에서 시작하는 로봇의 수를 최대화 할 수 있게 된다.

 

따라서 총 시간복잡도 \(O(NM)\)에 답을 구할 수 있다.

 

#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 <string> color;
vector <string> dir;
 
vector <int> loop_sz;
vector <vector<pii> > loops;
 
vector <vector<bool> > cache;
vector <vector<int> > loop_num;
vector <vector<int> > loop_section;
 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        loop_sz.clear();
        loops.clear();
 
        cin >> n >> m;
        color.resize(n);
        dir.resize(n);
 
        for (int i = 0; i < n; i++)
            cin >> color[i];
        for (int i = 0; i < n; i++)
            cin >> dir[i];
 
        cache.resize(n);
        for (int i = 0; i < n; i++)
            cache[i] = vector <bool>(m, false);
 
        loop_num.resize(n);
        for (int i = 0; i < n; i++)
            loop_num[i] = vector <int>(m, -1);
 
        loop_section.resize(n);
        for (int i = 0; i < n; i++)
            loop_section[i] = vector <int>(m, -1);
 
        int all = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            if (cache[i][j]) continue;
 
            vector <pii> stk;
            int x = i, y = j;
 
            while (true)
            {
                stk.push_back({ x,y });
                cache[x][y] = 1;
 
                int cdir;
                if (dir[x][y] == 'D') cdir = 0;
                else if (dir[x][y] == 'R') cdir = 1;
                else if (dir[x][y] == 'U') cdir = 2;
                else if (dir[x][y] == 'L') cdir = 3;
 
                int nx = x + dx[cdir];
                int ny = y + dy[cdir];
 
                if (!cache[nx][ny])
                {
                    x = nx, y = ny;
                    continue;
                }
 
                if (loop_num[nx][ny] == -1)
                {
                    int num = loops.size();
                    int cnt = 0;
                    auto it = prev(stk.end());
                    while (true)
                    {
                        int cx = it->first;
                        int cy = it->second;
 
                        if (cx == nx && cy == ny) break;
 
                        loop_num[cx][cy] = num;
                        loop_section[cx][cy] = cnt++;
                        it--;
                    }
 
                    int sz = cnt + 1;
                    loops.push_back(stk);
                    loop_sz.push_back(sz);
 
                    while (true)
                    {
                        int cx = it->first;
                        int cy = it->second;
 
                        loop_num[cx][cy] = num;
                        loop_section[cx][cy] = cnt++ % sz;
 
                        if (it == stk.begin()) break;
                        it--;
                    }
                }
                else
                {
                    int num = loop_num[nx][ny];
                    int sz = loop_sz[num];
                    int cnt = loop_section[nx][ny] + 1;
 
                    loops[num].insert(loops[num].end(), stk.begin(), stk.end());
                    auto it = prev(stk.end());
 
                    while (true)
                    {
                        int cx = it->first;
                        int cy = it->second;
 
                        loop_num[cx][cy] = num;
                        loop_section[cx][cy] = cnt++ % sz;
 
                        if (it == stk.begin()) break;
                        it--;
                    }
                }
 
                break;
            }
        }
 
        for (int i = 0; i < loops.size(); i++)
        {
            int sz = loop_sz[i];
            vector <int> cnt(sz);
 
            all += sz;
            for (pii it : loops[i])
            {
                int x = it.first;
                int y = it.second;
                int section = loop_section[x][y];
 
                if(color[x][y] == '0') cnt[section]++;
            }
 
            for (int it : cnt) if (it) ans++;
        }
 
        cout << all << ' ' << ans << '\n';
    }
}

 

이보다 시간은 조금 더 오래 걸리지만, 훨씬 간단한 풀이가 있다.

 

각 칸을 \(1\)부터 \(nm\)까지의 수로 대응하고 함수 \(f : X \rightarrow Y\)를 칸 X에서 Y로 이동하는 함수라고 하자.

물론 이 함수는 결합법칙이 성립하기 때문에, 스파스 테이블을 이용해 충분히 큰 수 a에 대해 \(f^a\)를 \(\log a\)에 구할 수 있게 된다.

 

\(a\)를 \(10^6\)이상의 큰 수로 잡으면, 정의역이 모든 칸일 때 \(f^a\)의 치역 개수가 로봇 수의 최대값이고,

정의역이 검은 칸일 때 \(f^a\)의 치역 개수가 검은 칸에서 시작하는 로봇의 최대값이다.

 

시간복잡도는 \(O(NM\log {NM})\)이다.

 

#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 <string> color;
vector <string> dir;
 
int par[1000001][21];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        color.resize(n);
        dir.resize(n);
 
        for (int i = 0; i < n; i++)
            cin >> color[i];
        for (int i = 0; i < n; i++)
            cin >> dir[i];
 
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            int num = i * m + j;
            if (dir[i][j] == 'U')
                par[num][0] = num - m;
            else if (dir[i][j] == 'D')
                par[num][0] = num + m;
            else if (dir[i][j] == 'L')
                par[num][0] = num - 1;
            else if (dir[i][j] == 'R')
                par[num][0] = num + 1;
        }
 
        for (int j = 1; j <= 20; j++)
        {
            for (int i = 0; i < n * m; i++)
                par[i][j] = par[par[i][j - 1]][j - 1];
        }
 
        set <int> all, black;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            int num = i * m + j;
            int p = par[num][20];
            all.insert(p);
            if (color[i][j] == '0') black.insert(p);
        }
 
        cout << all.size() << ' ' << black.size() << '\n';
    }
}