CF_Round 991 (Div. 3)

Posted Dec 6, 2024

By Hyeon Jae Kim

19 min read

Codeforces Round 991 (Div. 3)

Codeforces Round 991 (Div. 3)

A. Line Breaks

문제

Kostya는 라틴 알파벳으로 구성된 n개의 단어로 이루어진 텍스트를 가지고 있습니다. 그는 이 텍스트를 두 개의 띠에 써야 하는데:

첫 번째 띠는 m개의 문자만 수용할 수 있습니다
두 번째 띠는 제한 없이 문자를 수용할 수 있습니다
첫 번째 띠에 x개의 단어를 쓰고, 나머지는 두 번째 띠에 써야 합니다
단어들은 공백 없이 이어서 쓰며, 각 단어는 하나의 띠에 완전히 들어가야 합니다

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 1000)
각 테스트 케이스:
- 첫 줄: 단어 수 n (1 ≤ n ≤ 50)과 첫 번째 띠의 길이 m (1 ≤ m ≤ 500)
- 다음 n줄: 각 단어 (길이 ≤ 10)

출력

각 테스트 케이스마다 첫 번째 띠에 쓸 수 있는 최대 단어 수 x를 출력

예제

입력:

5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
codeforces
3 2
ab
c
d
3 2
abc
ab
a

출력:

B. Transfusion

문제

길이 n의 배열 a가 주어집니다. 아래 연산을 임의의 횟수만큼 수행할 수 있습니다:

2부터 n-1까지의 인덱스 i를 선택
두 가지 연산 중 하나를 선택:
1. ai-1을 1 감소시키고 ai+1을 1 증가
2. ai+1을 1 감소시키고 ai-1을 1 증가
모든 값이 음수가 되면 안됩니다

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^4)
각 테스트 케이스:
- 첫 줄: 배열의 길이 n (3 ≤ n ≤ 2×10^5)
- 두 번째 줄: n개의 정수 ai (1 ≤ ai ≤ 10^9)

출력

각 테스트 케이스마다 모든 원소를 같게 만들 수 있으면 “YES”, 아니면 “NO” 출력

C. Uninteresting Number

문제

10^5자리 이하의 숫자가 주어집니다. 아래 연산을 임의의 횟수만큼 수행할 수 있습니다:

임의의 자릿수를 선택하여 그 숫자를 제곱
제곱한 결과가 한 자릿수여야 함 (x^2 < 10)
원래 자릿수를 제곱한 결과로 교체

위 연산을 통해 9의 배수를 만들 수 있는지 판단하세요.

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^4)
각 테스트 케이스:
- 한 줄에 숫자 n (선행 0 없음)

출력

각 테스트 케이스마다 9의 배수를 만들 수 있으면 “YES”, 아니면 “NO” 출력

D. Digital String Maximization

문제

숫자로 이루어진 문자열 s가 주어집니다. 다음 연산을 임의의 횟수만큼 수행할 수 있습니다:

0이나 첫 자리를 제외한 임의의 숫자를 선택
선택한 숫자를 1 감소시키고
왼쪽 숫자와 교환

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^4)
각 테스트 케이스:
- 한 줄에 숫자로 이루어진 문자열 s (1 ≤ s ≤ 2×10^5)

출력

각 테스트 케이스마다 만들 수 있는 사전순으로 가장 큰 문자열 출력

E. Three Strings

문제

세 개의 문자열 a, b, c가 주어집니다. c는 다음과 같이 생성되었습니다:

각 단계마다 a나 b를 무작위로 선택하여 첫 글자를 제거하고 c의 끝에 추가
한 문자열이 비면 나머지 문자열의 모든 문자를 c의 끝에 추가
그 후 c의 일부 문자들이 임의로 변경됨

변경된 최소 문자 수를 찾으세요.

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^3)
각 테스트 케이스:
- 첫째 줄: 문자열 a (1 ≤ a ≤ 10^3)
- 둘째 줄: 문자열 b (1 ≤ b ≤ 10^3)
- 셋째 줄: 문자열 c ( c = a + b )

출력

각 테스트 케이스마다 c를 만들기 위해 필요한 최소 문자 변경 횟수를 출력

F. Maximum Modulo Equality

문제

길이 n의 배열과 q개의 쿼리가 주어집니다. 각 쿼리는 구간 [l,r]을 지정합니다. al, al+1, …, ar이 모두 같은 나머지를 갖게 하는 가장 큰 모듈러스 m을 찾으세요. m이 무한대가 될 수 있다면 0을 출력하세요.

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^4)
각 테스트 케이스:
- 첫 줄: n, q (1 ≤ n,q ≤ 2×10^5)
- 둘째 줄: n개의 정수 ai (1 ≤ ai ≤ 10^9)
- 다음 q줄: 두 정수 l, r (1 ≤ l ≤ r ≤ n)

출력

각 쿼리마다 최대 모듈러스 m을 출력

G. Tree Destruction

문제

n개의 정점을 가진 트리가 주어집니다. 한 번에 두 정점 a와 b를 선택하여 a에서 b까지의 경로 상의 모든 정점을 제거할 수 있습니다. 제거 후 생성될 수 있는 최대 연결 컴포넌트 수를 찾으세요.

입력

첫 줄: 테스트 케이스 수 t (1 ≤ t ≤ 10^4)
각 테스트 케이스:
- 첫 줄: 트리의 크기 n (2 ≤ n ≤ 2×10^5)
- 다음 n-1줄: 두 정수 u, v (간선 정보)

출력

각 테스트 케이스마다 가능한 최대 연결 컴포넌트 수를 출력

코드

A. Line Breaks

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int n, m;
    cin >> n >> m;

    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }

    int len = 0;
    int ans = 0;

    for (const string& word : words) {
        if (word.length() > m) break;
        if (len + word.length() > m) break;

        len += word.length();
        ans++;
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

B. Transfusion

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long even_sum = 0, odd_sum = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2)
            odd_sum += a[i];
        else
            even_sum += a[i];
    }

    int even_count = (n + 1) / 2;
    int odd_count = n / 2;

    if ((even_sum + odd_sum) % n != 0) {
        cout << "NO\n";
        return;
    }

    long long target = (even_sum + odd_sum) / n;
    if (even_sum % even_count != 0 || odd_sum % odd_count != 0 ||
        even_sum / even_count != target || odd_sum / odd_count != target) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

C. Uninteresting Number

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    string n;
    cin >> n;
    vector<int> digits;
    for (char c : n) digits.push_back(c - '0');

    int len = digits.size();
    vector<bool> possible(9, false);
    possible[0] = true;

    for (int digit : digits) {
        vector<bool> next(9, false);
        for (int mod = 0; mod < 9; mod++) {
            if (!possible[mod]) continue;
            next[(mod + digit) % 9] = true;
            if (digit * digit < 10) {
                next[(mod + digit * digit) % 9] = true;
            }
        }
        possible = next;
    }

    cout << (possible[0] ? "YES\n" : "NO\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

D. Digital string maximization

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    // 각 위치에서 가능한 최대값을 한 번에 계산
    for (int i = 0; i < n - 1; i++) {
        // 현재 위치에서 가능한 최대값과 그 위치 찾기
        int maxVal = s[i] - '0';
        int maxPos = i;

        // i+1부터 시작하여 현재 위치까지 가져올 수 있는 최대값 찾기
        for (int j = i + 1; j < min(n, i + 10); j++) {
            if (s[j] == '0') continue;
            int val = s[j] - '0' - (j - i);
            if (val > maxVal) {
                maxVal = val;
                maxPos = j;
            }
        }

        // 최대값을 찾았다면 문자열 업데이트
        if (maxPos != i) {
            char c = maxVal + '0';
            for (int j = maxPos; j > i; j--) {
                s[j] = s[j - 1];
            }
            s[i] = c;
        }
    }

    cout << s << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

E. Three Strings

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    string a, b, c;
    cin >> a >> b >> c;

    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, n + m));
    dp[0][0] = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i < n && dp[i][j] < n + m) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (a[i] != c[i + j]));
            }
            if (j < m && dp[i][j] < n + m) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (b[j] != c[i + j]));
            }
        }
    }

    cout << dp[n][m] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

F. Maximum modulo equality

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 세그먼트 트리를 사용하여 구간 GCD를 효율적으로 계산
    vector<long long> diff(n - 1);
    for (int i = 0; i < n - 1; i++) {
        diff[i] = abs(a[i + 1] - a[i]);
    }

    // 세그먼트 트리 구성
    int size = 1;
    while (size < n - 1) size *= 2;
    vector<long long> seg(2 * size);

    // 세그먼트 트리 초기화
    for (int i = 0; i < n - 1; i++) {
        seg[size + i] = diff[i];
    }
    for (int i = size - 1; i > 0; i--) {
        seg[i] = gcd(seg[2 * i], seg[2 * i + 1]);
    }

    // 구간 GCD 쿼리 함수
    auto query = [&](int l, int r) {
        l += size;
        r += size;
        long long result = 0;
        while (l < r) {
            if (l & 1) result = gcd(result, seg[l++]);
            if (r & 1) result = gcd(result, seg[--r]);
            l >>= 1;
            r >>= 1;
        }
        return result;
    };

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;

        if (l == r) {
            cout << "0 ";
            continue;
        }

        // 구간 내 모든 수가 같은지 빠르게 확인
        if (query(l, r) == 0) {
            cout << "0 ";
            continue;
        }

        cout << query(l, r) << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

G. Tree Destruction (Fail) -> tourist’s code

        
      
/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
        deg[i] = int(g[i].size());
    }
    int ans = -n;
    auto Dfs = [&](auto&& self, int v, int pr) -> int {
        int mx1 = 0;
        int mx2 = 0;
        for (int u : g[v]) {
            if (u == pr) {
                continue;
            }
            int got = self(self, u, v);
            if (got > mx1) {
                mx2 = mx1;
                mx1 = got;
            } else {
                mx2 = max(mx2, got);
            }
        }
        ans = max(ans, mx1 + mx2 + (deg[v] - 2));
        return mx1 + (deg[v] - 2);
    };
    Dfs(Dfs, 0, -1);
    cout << ans + 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

알고리즘

codeforces cp 알고리즘

This post is licensed under CC BY 4.0 by the author.

Codeforces Round 991 (Div. 3)

Codeforces Round 991 (Div. 3)

A. Line Breaks

문제

입력

출력

예제

B. Transfusion

문제

입력

출력

C. Uninteresting Number

문제

입력

출력

D. Digital String Maximization

문제

입력

출력

E. Three Strings

문제

입력

출력

F. Maximum Modulo Equality

문제

입력

출력

G. Tree Destruction

문제

입력

출력

코드

A. Line Breaks

B. Transfusion

C. Uninteresting Number

D. Digital string maximization

E. Three Strings

F. Maximum modulo equality

G. Tree Destruction (Fail) -> tourist’s code

Trending Tags