Codeforces Round 1135 (Div. 2)
A-D 풀이
ICPC도 끝난 겸 개인 역량을 좀 강화하고자 하는 마음에 오랜만에 참가해 보았습니다.
A. Composite Permutation
인 경우 자명하게 해가 없음을 알 수 있습니다.
만약 이 합성수인 경우 를 로 배치하면 이 되고 이거나 이면 다른 인수가 합성수이므로 조건을 만족합니다.
이 소수인 경우 위 규칙을 응용해서 처럼 배치하면 됩니다.
코드 (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의 개수를 , 1의 개수를 라 하면 diversity는 입니다.
을 정리하면 이 됩니다.
이 최소가 되게 하려면 을 최대화하면 되므로 최대 번 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
의 위치관계는 관계없으므로 를 정렬하여 이라 합시다.
연산을 해서 바뀐 를 라 쓰겠습니다.
다른 수는 그대로고 만 으로 바뀐다고 생각해 봅시다. 은 의 값이 될 수 있으므로 경우의 수는 입니다.
이번에는 과 만 바뀐다고 생각해 봅시다. 이라면 을 대체하는 연산을 수행할 수 없으므로 두 수 모두 보다 작아야 합니다.
따라서 경우의 수는 입니다.
일반화해서 뒤쪽의 개, 즉 만 바뀐다고 생각해 봅시다. 모두 이하로 바뀌어야 하므로 경우의 수는 이 됩니다.
이 중복이 아닌 경우에 대해 를 구하면 답이 됩니다.
코드 (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
를 뒤집은 배열을 라고 하겠습니다.
먼저 그리디하게 인 를 모두 찾습니다.
이러한 마다 분할해주면 인 를 찾을 수 있습니다.
를 만족하는 는 모두 에서 인접한 두 블록을 병합하는 연산을 번 이상 해서 얻을 수 있습니다.
따라서 의 길이를 라 하면 가 조건을 만족하는 길이 의 분할의 개수가 됩니다.
라는 뜻은 임을 뜻합니다.
라 합시다. 그렇다면 번째 원소에 만큼 더하는 것은 의 특정 구간 에 를 더하거나 빼는 것으로 이해할 수 있습니다.
, 입니다.
이면 더하고 아니면 뺍니다. 이 변화량을 라 합시다.
인 의 개수를 라 하면 이 답임을 아까 확인했습니다. 따라서 구간 의 의 개수와 의 개수를 빠르게 세면 쿼리에 답할 수 있습니다.
이는 이분 탐색으로 해결할 수 있고, 따라서 시간 복잡도 에 해결할 수 있습니다.
코드 (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;
}댓글
이름과 이메일을 입력해 댓글을 남겨주세요.