CF_Round 991 (Div. 3)

김현재·2024년 12월 5일
codeforcescp알고리즘

알고리즘

목록 보기
89/291

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

출력:

1
2
2
1
0

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는 다음과 같이 생성되었습니다:
1. 각 단계마다 a나 b를 무작위로 선택하여 첫 글자를 제거하고 c의 끝에 추가
2. 한 문자열이 비면 나머지 문자열의 모든 문자를 c의 끝에 추가
3. 그 후 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;
}
profile
김현재
Studying Everyday
이전 포스트

BOJ_1090_체커(Java, C++)

다음 포스트

BOJ_9471_피사노 주기 (C++)

0개의 댓글