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

가능한 모든 방법으로 한번씩 틀린게 아닐까?

A - Orac and Factors

Problem - A - Codeforces

\(n \ge 2\)에 대해 \(f(n)\)을 \(n\)의 1이 아닌 가장 작은 약수로 정의하자.

어떤 수 \(n\)이 주어지고 이 수에 \(f(n)\)을 더하는 작업을 \(k\)번 반복했을 때, 결과값을 출력해야 한다.

 

\(n\)이 짝수라면, \(f(n)\)은 항상 2이다.

\(n\)이 홀수라면, \(f(n)\)은 항상 홀수인데, 홀수에 홀수를 더하므로 그 다음 값은 짝수가 된다.

 

따라서 맨 처음만 \(f(n)\)을 구해서 더해준 다음, \(2(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; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n, k; cin >> n >> k;
        if (n % 2)
        {
            bool flag = true;
            for (ll i = 2; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    flag = false;
                    n += i;
                    k--;
                    break;
                }
            }
 
            if (flag)
            {
                n += n;
                k--;
            }
        }
 
        cout << n + k * 2 << '\n';
    }
}

---

B - Orac and Models

Problem - B - Codeforces

\(n\)개의 정수가 주어진다.

\(n\)개의 인덱스 \((1, 2, \dots , n)\) 중에 몇 개를 차례대로 고른 수열을 \(i\)라고 하자.

 

이 수열의 인접한 두 원소 \(i_j, i_{j+1}\)에 대해, \(i_{j+1}\)이 \(i_j\)로 나눠떨어지고 \(s_{i_j} < s_{i_{j_1}}\)을 만족 해야 할 때,

수열 \(i\)의 최대 길이를 구해야 한다.

 

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

\(DP(i) : \) 인덱스 \(i\)를 골랐을 때, 가능한 수열의 최대 길이

 

그럼 다음과 같은 식을 이끌어 낼 수 있다.

\(DP(i) = 1 + max(DP(j))\) (\(j\)는 \(i\)보다 큰 \(i\)의 배수, \(s_i < s_j\))

 

그리고 각 \(DP(i)\)중 가장 큰 것이 답이다.

 

시간 복잡도는 \(O(\lfloor n \rfloor + \lfloor n/2 \rfloor + \lfloor n/3 \rfloor + \cdots + \lfloor n/n \rfloor)\) 인데,

\(n\)이 \(10^5\)일 때 위의 값은 \(1166750\)이므로, 충분히 시간안에 돌아감을 알 수 있다.

 

#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 s[100001];
 
int dp[100001];
int solve(int i)
{
    if (dp[i] != -1) return dp[i];
    dp[i] = 0;
    for (int j = 2; i * j <= n; j++)
    {
        if(s[i] < s[i*j])
            dp[i] = max(dp[i], solve(i * j));
    }
 
    return ++dp[i];
}
 
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 >> s[i];
            dp[i] = -1;
        }
 
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans = max(ans, solve(i));
 
        cout << ans << '\n';
    }
}

---

A - Orac and LCM

Problem - A - Codeforces

양의 정수로 이루어진 중복집합 \(s\)가 있을 때,

\(gcd(s)\) 를 집합의 모든 원소의 최대공약수,

\(lcm(s)\) 를 집합의 모든 원소의 최소공배수라고 하자.

 

크기 \(n\)인 중복집합 \(a\)가 있고,

중복 집합 \(t = \{lcm(\{a_i,a_j\})\text{ } |\text{ } i \lt j \}\) 라고 할때,

\(gcd(t)\)를 구해야 한다.

 

\(t\)의 모든 원소가 공통적으로 가지고 있는 인수에 대해 생각해보자.

집합 \(a\)의 임의의 한 원소 \(a_i\)를 제외한 나머지 원소들의 공통된 인수 \(g\)가 있다면,

서로 다른 인덱스의 두 원소 \(a_i, a_j\)의 최소공배수를 계산할 때 인수로 무조건 포함되게 된다.

따라서 \(t\)의 원소는 무조건 \(g\)를 공약수로 가지게 된다.

 

따라서 답은 \(lcm(\{a_1\)을 제외한 원소들의 gcd, \(a_2\)를 제외한 원소들의 gcd, \(\dots\), \(a_n\)을 제외한 원소들의 gcd \(\})\) 가 된다.

 

이를 구하는 방법에는 여러가지가 있는데, 본인은 코드의 간략화를 위해 구간 gcd 세그먼트 트리를 이용했다.

 

#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 = 100001;
 
int n;
int a[N];
 
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] = gcd(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        update(1, 0, n - 1, i, a[i]);
    }
 
    ll ans = 1;
    for (int i = 0; i < n; i++)
    {
        int tmp = a[i];
        update(1, 0, n - 1, i, 0);
        
        ll res = segTree[1];
        ans = ans * res / gcd(ans, res);
 
        update(1, 0, n - 1, i, tmp);
    }
 
    cout << ans;
}

---

B - Orac and Medians

Problem - B - Codeforces

길이 \(n\)인 수열 \(a\)가 있다.

이 수열에 구간 \([l\dots r]\)을 선택해서 구간 내의 모든 원소를 중앙값 하나로 바꾸는 연산을 할 수 있다.

중앙값은 구간에서 \(\lfloor \frac{s+1}2 \rfloor\)번째로 작은 원소로 정의한다. (\(s : \) 구간의 크기)

 

이 연산을 원하는 만큼 사용해서 이 수열의 원소를 모두 \(k\)로 바꾸는 것이 가능한지 여부를 알아내야 한다.

 

어떻게든 \(k\)로 이루어진 길이가 2인 구간을 만들어 낼 수 있다고 하자.

그러면 2개의 \(k\)와 임의의 한 수로 이루어진 길이 3의 구간의 중앙값은 무조건 \(k\)므로 답은 무조건 yes라는 사실을 알 수 있다.

 

\(k\)로 이루어진 길이가 2인 구간을 만들 수 있으려면 배열이 어떻게 이루어져야 할까?

 

먼저 \(a\)에 \(k\)가 존재해야 함은 자명하다.

또, 임의의 길이 2의 구간을 선택했을 때, 둘 다 \(k\)이상의 수거나,

길이 3의 구간을 선택했을 때, 원소 2개 이상이 \(k\)이상이면 가능하다.

 

배열이 위와 같은 조건을 만족한다면, 배열을 모두 \(k\)이상의 수로 채울 수 있게 되고,

\(k\)와 \(k\)이상의 수로 이루어진 길이 2인 구간의 중앙값은 \(k\)이므로, 결국 모든 수를 \(k\)로 만드는 것이 가능하다는 사실을 알 수 있다.

 

#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[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
 
        bool isValid = false;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (a[i] == k) isValid = true;
        }
        a[n] = 0;
 
        if (!isValid)
        {
            cout << "no\n";
            continue;
        }
 
        if (n == 1)
        {
            cout << "yes\n";
            continue;
        }
 
        bool ans = false;
        for (int i = 0; i < n - 1; i++)
        {
            int cnt = 0;
            for (int j = i; j < i + 3; j++)
            {
                if (a[j] >= k) cnt++;
            }
 
            if (cnt >= 2) ans = true;
        }
 
        if (ans) cout << "yes\n";
        else cout << "no\n";
    }
}

---

C - Orac and Game of Life

Problem - C - Codeforces

\(n\)열 \(m\)행으로 이루어진 격자가 주어진다.

 

초기에 이 격자는 흰색 또는 검은색으로 칠해져 있는데,

1초가 지날 때마다 각 격자는 다음과 같은 규칙에 의해 색이 바뀌게 된다.

 

1. 현재 격자의 색과 인접한 다른 격자의 색이 모두 다르다면, 색이 변하지 않는다.

2. 그렇지 않다면, 색이 반전된다.

 

격자의 초기상태가 주어지고, \(t\)개의 쿼리가 주어지는데,

각 쿼리마다 \(i\)행 \(j\)열의 격자가 \(p\)초 후에 어떤 색깔이 될지 알아내야 한다.

 

우선 격자에서 인접한 같은 색의 격자들을 같은 컴포넌트로 묶어보자.

이 컴포넌트가 격자 2개 이상으로 이루어져 있다면, 시작하자마자 깜빡이게 된다. (1초마다 색이 반전됨)

 

격자 1개만으로 이루어진 컴포넌트는 어떨까?

격자 2개 이상으로 이루어진 컴포넌트까지의 (맨하탄)거리가 \(d\)라고 하자.

\(d\)초가 되기 전까지는 현재 색깔을 유지하다가, 그 이후부터는 격자 2개 이상으로 된 컴포넌트와 합쳐지게 되므로 깜빡이게 된다.

 

따라서 크기가 2이상으로 이루어진 컴포넌트들에서 크기가 1인 컴포넌트까지의 거리를 BFS로 구해두면, 각각의 컴포넌트가 현재 색깔을 유지하다가 몇 초 이후부터 깜빡이는지 알 수 있게 되므로, 각각의 쿼리를 \(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, m, t;
string board[1001];
 
vector <int> graph[1000001];
 
int cnt = 0;
int num[1001][1001];
 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
 
int DFS(int x, int y)
{
    num[x][y] = cnt;
 
    int res = 1;
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (num[nx][ny] != -1) continue;
        if (board[x][y] != board[nx][ny]) continue;
 
        res += DFS(nx, ny);
    }
 
    return res;
}
 
int dist[1000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++) cin >> board[i];
 
    memset(num, -1, sizeof num);
    memset(dist, -1, sizeof dist);
 
    queue <int> q;
 
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        if (num[i][j] == -1)
        {
            int res = DFS(i, j);
 
            if (res > 1)
            {
                q.push(cnt);
                dist[cnt] = 0;
            }
            cnt++;
        }
    }
 
    for (int x = 0; x < n; x++) for (int y = 0; y < m; y++)
    {
        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (num[x][y] == num[nx][ny]) continue;
            graph[num[x][y]].push_back(num[nx][ny]);
            graph[num[nx][ny]].push_back(num[x][y]);
        }
    }
 
    for (int i = 0; i < cnt; i++)
    {
        sort(graph[i].begin(), graph[i].end());
        graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());
    }
 
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (auto nv : graph[v])
        {
            if (dist[nv] != -1) continue;
            dist[nv] = dist[v] + 1;
            q.push(nv);
        }
    }
 
    while (t--)
    {
        int i, j; ll p;
        cin >> i >> j >> p;
        i--; j--;
 
        if (dist[num[i][j]] == -1)
        {
            cout << board[i][j] << '\n';
            continue;
        }
 
        if (dist[num[i][j]] > p)
            cout << board[i][j] << '\n';
        else
            cout << ((board[i][j] - '0') ^ ((p - dist[num[i][j]]) % 2)) << '\n';
    }
}

---

D - Slime and Biscuits

Problem - D - Codeforces

추가 예정

---

E - Slime and Hats

Problem - E - Codeforces

추가 예정

---

F - Slime and Sequences (Hard Version)

Problem - F2 - Codeforces

추가 예정