Codeforces Round 1135 (Div. 2)

A-D 풀이

3 min readPSCodeforces

링크

ICPC도 끝난 겸 개인 역량을 좀 강화하고자 하는 마음에 오랜만에 참가해 보았습니다.

A. Composite Permutation

n≤3n \leq 3인 경우 자명하게 해가 없음을 알 수 있습니다.

만약 nn이 합성수인 경우 pp를 n,n−1,n−2,⋯ ,1n, n - 1, n - 2, \cdots, 1로 배치하면 i⋅pi=i⋅(n−i+1)i \cdot p_i = i \cdot (n - i + 1)이 되고 i=1i = 1이거나 n−i+1=1n - i + 1 = 1이면 다른 인수가 합성수이므로 조건을 만족합니다.

nn이 소수인 경우 위 규칙을 응용해서 n−1,n−2,⋯ ,1,nn - 1, n - 2, \cdots, 1, n 처럼 배치하면 됩니다.

코드 (C++)
#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
 
    if (n <= 3) {
        cout << -1 << '\n';
        return;
    }
 
 
    int st = n - n % 2;
    for (int i = st; i >= 1; i--) cout << i << ' ';
    if (n % 2 == 1) cout << n;
    cout << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

B. Diverse String

diversity를 계산하는 방법을 알아봅시다.

문자열에서 특정 구간의 0이 1로 바뀌는 경우를 생각해보면, 문자열에서 두 0을 고르는 경우의 수와 같음을 알 수 있습니다.

1이 0으로 바뀌는 경우도 마찬가지입니다.

0의 개수를 c0c_0, 1의 개수를 c1c_1라 하면 diversity는 1+c0(c0+1)2+c1(c1+1)21 + \dfrac{c_0(c_0 + 1)}{2} + \dfrac{c_1(c_1 + 1)}{2} 입니다.

c0(c0+1)+c1(c1+1)c_0(c_0 + 1) + c_1(c_1 + 1)을 정리하면 (c0+c1)2−c0c1(c_0 + c_1)^2 - c_0c_1이 됩니다.

c0c1c_0c_1이 최소가 되게 하려면 ∣c0−c1∣|c_0 - c_1|을 최대화하면 되므로 최대 kk번 toggle을 해서 개수를 한쪽으로 몰아주면 됩니다.

코드 (C++)
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
void solve() {
    ll n, k;
    cin >> n >> k;
 
    string s;
    cin >> s;
 
    ll cnt[2] = {};
    for (int i = 0; i < n; i++) { cnt[s[i] - '0']++; }
 
    if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]);
    ll toggle = min(cnt[0], k);
    cnt[0] -= toggle;
    cnt[1] += toggle;
 
    cout << cnt[0] * (cnt[0] + 1) / 2 + cnt[1] * (cnt[1] + 1) / 2 + 1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

C. Max Substitution

aa의 위치관계는 관계없으므로 aa를 정렬하여 ai≤ai+1a_i \leq a_{i + 1}이라 합시다.

연산을 해서 바뀐 aa를 a′a'라 쓰겠습니다.

다른 수는 그대로고 ana_n만 an′a'_n으로 바뀐다고 생각해 봅시다. ana_n은 [1,an)[1, a_n)의 값이 될 수 있으므로 경우의 수는 an−1a_n - 1입니다.

이번에는 an−1a_{n - 1}과 ana_n만 바뀐다고 생각해 봅시다. an′≥an−1a'_n \geq a_{n - 1}이라면 an−1a_{n - 1}을 대체하는 연산을 수행할 수 없으므로 두 수 모두 an−1a_{n - 1}보다 작아야 합니다.

따라서 경우의 수는 (an−1−1)2(a_{n - 1} - 1)^2입니다.

일반화해서 뒤쪽의 ii개, 즉 an−i+1,an−i+2,⋯ ,ana_{n - i + 1}, a_{n - i + 2}, \cdots, a_n만 바뀐다고 생각해 봅시다. 모두 an−i+1a_{n - i + 1} 이하로 바뀌어야 하므로 경우의 수는 (an−i+1−1)i(a_{n - i + 1} - 1)^i이 됩니다.

an−i+1a_{n - i + 1}이 중복이 아닌 경우에 대해 ∑(an−i+1−1)i\displaystyle\sum (a_{n - i + 1} - 1)^i를 구하면 답이 됩니다.

코드 (C++)
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr ll MOD = 1e9 + 7;
 
ll power(ll base, ll exp) {
    ll ret = 1;
 
    while (exp) {
        if (exp & 1) ret = ret * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
 
    return ret;
}
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin() + 1, a.end());
 
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        if (a[n - i] == a[n - i + 1]) break;
 
        ans += power(a[n - i + 1] - 1, i);
        ans %= MOD;
    }
 
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

D. Reverse Partition

aa를 뒤집은 배열을 bb라고 하겠습니다.

먼저 그리디하게 ∑k=1iak=∑k=1ibk\displaystyle\sum_{k = 1}^i a_k = \displaystyle\sum_{k = 1}^i b_k인 ii를 모두 찾습니다.

이러한 ii마다 분할해주면 f(a,p)=f(b,p)f(a, p) = f(b, p)인 pp를 찾을 수 있습니다.

f(a,p′)=f(b,p′)f(a, p') = f(b, p')를 만족하는 p′p'는 모두 pp에서 인접한 두 블록을 병합하는 연산을 00번 이상 해서 얻을 수 있습니다.

따라서 pp의 길이를 gg라 하면 (g−1m−1)\dbinom{g - 1}{m - 1}가 조건을 만족하는 길이 mm의 분할의 개수가 됩니다.

∑k=1iak=∑k=1ibk\displaystyle\sum_{k = 1}^i a_k = \displaystyle\sum_{k = 1}^i b_k라는 뜻은 ∑k=1i(ak−bk)=0\displaystyle\sum_{k = 1}^i (a_k - b_k) = 0임을 뜻합니다.

Si=∑k=1i(ak−bk)S_i = \displaystyle\sum_{k = 1}^i (a_k - b_k)라 합시다. 그렇다면 ii번째 원소에 vv만큼 더하는 것은 SS의 특정 구간 [l,r][l, r]에 vv를 더하거나 빼는 것으로 이해할 수 있습니다.

l=min⁡(i,n−i+1)l = \min(i, n - i + 1), r=max⁡(i,n−i+1)−1r = \max(i, n - i + 1) - 1입니다.

i=li = l이면 더하고 아니면 뺍니다. 이 변화량을 ww라 합시다.

Si=0S_i = 0인 ii의 개수를 gg라 하면 (g−1m−1)\dbinom{g - 1}{m - 1}이 답임을 아까 확인했습니다. 따라서 구간 [l,r][l, r]의 00의 개수와 −w-w의 개수를 빠르게 세면 쿼리에 답할 수 있습니다.

이는 이분 탐색으로 해결할 수 있고, 따라서 시간 복잡도 O((n+q)log⁡n)O((n + q)\log n)에 해결할 수 있습니다.

코드 (C++)
#include <bits/stdc++.h>
using namespace std;
 
#define all(v) v.begin(), v.end()
 
using ll = long long;
 
constexpr ll MOD = 1e9 + 7;
 
ll power(ll base, ll exp) {
    ll ret = 1;
 
    while (exp) {
        if (exp & 1) ret = ret * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
 
    return ret;
}
 
ll fact[202020];
ll ifact[202020];
ll comb(ll n, ll r) {
    if (n < r) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
 
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
 
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    ll zero = 0;
    vector<ll> pref(n + 1);
    map<ll, vector<int>> poss;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i] - a[n - i + 1];
        if (pref[i] == 0) zero++;
 
        poss[pref[i]].push_back(i);
    }
 
    while (q--) {
        int i;
        ll v;
        cin >> i >> v;
 
        int l = min(i, n - i + 1);
        int r = max(i, n - i + 1) - 1;
 
        ll w = (i == l ? v : -v);
        ll oldZero = upper_bound(all(poss[0]), r) - lower_bound(all(poss[0]), l);
        ll newZero = upper_bound(all(poss[-w]), r) - lower_bound(all(poss[-w]), l);
 
        cout << comb(zero - oldZero + newZero - 1, m - 1) << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < 202020; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        ifact[i] = power(fact[i], MOD - 2);
    }
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}

댓글

이름과 이메일을 입력해 댓글을 남겨주세요.