Codeforces Round 867 (Div. 3)
A. TubeTube Feed (800)
지문이 좀 읽기 어려운데 결론적으로 $a_i \le t - i$ 인 것 중 가장 큰 $b_i$ 를 찾는 문제이다.
B. Karina and Array (800)
정렬하고 가장 작은 것 두개의 곱이나 가장 큰 것 두개의 곱이 정답이다.
음수 * 음수 = 가장큰 양수가 될 수 있기 때문이다.
C. Bun Lover (800)
에디토리얼은 다른 풀이를 갖지만, 내가 푼 풀이는 다음과 같다.
잘 살펴보면 $dp_{n}=dp_{n-1} + 1 + 2n$ 이라는 점화식을 세울 수 있다.
임을 알 수 있으므로 바로 계산해줄 수 있다.
D. Super-Permutation (1200)
$n=1$ 일땐 항상 가능하다.
$n$이 짝수일 때 항상 만들 수 있는 방법은 다음과 같다.
n 1 n-2 3 n-4 5 n-6 ... 2 n-1
와 같이 구성하면 된다.
$n$이 $1$이 아닌 홀수일 땐 불가능하다.
$k$가 $a$에서 $n$이 있는 자리라고 하자. $a_k=n$
$b_{k}=b_{k-1}+a_k=b_{k-1}+n \pmod n$ 이 되면
$b_k \equiv b_{k-1} \pmod n$ 이 되기 때문에 $n$은 $a$에서 항상 첫 자리를 가지고 있다. 즉, $b_1 \equiv 0 \pmod n$ 이다.
홀수일 때를 보자.
$\sum_{i=1}^n i = \dfrac {n(n+1)}2 \equiv 0 \pmod n$ 이다. $b_n = 0$ 이란 뜻이고 $b_1=b_n=0$ 이 되어버렸으므로 불가능하다.
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
} else if (n % 2 == 1) {
cout << -1 << endl;
} else {
vi ans(n + 1);
for (int i = 1; i <= n; i += 2) ans[i] = i;
for (int i = n; i >= 0; i -= 2) ans[n - i] = i;
for (int i = 0; i < n; i++) cout << ans[i] << ' ';
cout << endl;
}
}
E. Making Anti-Palindromes (1600)
일단 홀수면 불가능하다.
동일한 알파벳이 $n/2$ 개보다 많으면 항상 $s_i=s_{n-1-i}$ 인 부분이 생기므로 불가능하다.
그렇지 않다고 하자.
$s_i \ne s_{n-1-i}$ 인 쌍을 발견했을 때 $s_i$와 $s_{n-1-i}$ 중 작은 알파벳의 개수를 세주자.
모든 알파벳의 세진 개수를 배열에 넣고 정렬한다. 이 배열을 $x$ 라 한다.
$1$번의 교체로 항상 $s_i = s_{n-1-i}$ 인 쌍을 두 개나 한 개를 제거할 수 있다.
최대한 두 개를 제거하는걸 많이 쓴 다음 한 개로 제거해야 하는 것을 제거해야 한다.
다음과 같이 쌍이 있다고 하자.
s=cbaaaaaabc
a - a
a - a
a - a
b - b
c - c
이 경우 정답은 $3$ 인데 왜그런지 보자.
$x=\left[ 3,1,1 \right]$ 이 된다.
서로 다른 알파벳을 바꾸는 경우 항상 지워야 할 것이 $2$개씩 줄어든다. 가령 다음과 같다.
$\left[ 3,1,1 \right] \to \left[ 2,1,0 \right] \to \left[ 1,0,0 \right]$
이제 나머지 $a$ 는 한 개 혼자 남았으므로 항상 $1$번의 스왑으로 한개만 삭제해줄 수 있다.
이런식으로 $x$에서 가장 큰 수와 나머지 것들의 합을 비교하면 된다.
$\sum_{i=1}^{n-1} x_i < x_0$ 라면 정답은 $x_0$ 이고, 그렇지 않다면 정답은 $\left\lceil \dfrac {\sum_{i=0}^{n-1} x_i}2 \right\rceil$ 이다.
void solve() {
int n;
string s;
cin >> n >> s;
if (n % 2 == 1) {
cout << -1 << endl;
return;
}
vi cnt(26);
for (char c: s) cnt[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (cnt[i] > n / 2) {
cout << -1 << endl;
return;
}
}
vi c(26);
for (int i = 0; i < n / 2; i++) {
if (s[i] == s[n - 1 - i]) {
c[min(s[i], s[n - 1 - i]) - 'a']++;
}
}
vi x;
for (int i = 0; i < 26; i++) if (c[i]) x.pb(c[i]);
sort(all(x));
int sum = acc(x);
if (sum == 0) {
cout << 0 << endl;
return;
}
int other = sum - x.back();
if (x.back() > other) {
cout << x.back() << endl;
} else {
cout << (sum + 1) / 2 << endl;
}
}
F. Gardening Friends (1700)
전형적인 re-rooting 테크닉을 쓰는 문제여서 설명을 생략한다.
G1. Magic Triples (Easy Version) (1700)
G1. Magic Triples (Easy Version)
$1 \le a_i \le 10^6$ 이므로 $a_i \le a_j \le a_k$라 할 때, $a_k$ 은 $a_i \cdot b^2$ 이기 때문에 $b^2 \le 10^6$ 인 $b$ 까지만 검사를 해줄 수 있다.
수를 세는건 단순히 경우의 수를 세면 된다.
이는 시간복잡도 $O(10^3 \cdot \sum n)$ 이 걸릴 것이다. 시간내에 충분히 통과 가능하다.
const int MAX = 1e6;
const int SQ = 1e3 + 100;
int cnt[MAX + 1];
void solve() {
int n;
cin >> n;
vi a(n);
fv(a);
sort(all(a));
for (int i = 0; i < n; i++) cnt[a[i]]++;
ll ans = 0;
for (int b = 1; b <= SQ; b++) {
for (int i = 0; i < n; i++) {
if (a[i] % (b * b) == 0) {
if (i == n - 1 || a[i] != a[i + 1]) {
if (b >= 2) {
int X = a[i] / b / b;
int Y = a[i] / b;
ans += 1ll * cnt[a[i]] * cnt[X] * cnt[Y];
} else {
ans += 1ll * cnt[a[i]] * (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
}
}
}
}
}
cout << ans << endl;
for (int i: a) cnt[i] = 0;
}
G2. Magic Triples (Hard Version) (2200)
스킵하려다가 에디토리얼을 보고 어떻게 푸는지 공부했다.
경우를 구간으로 나눠서 세는 테크닉은 특이해서 기억할만 했다.
G2. Magic Triples (Hard Version)
다음과 같은 경우를 순서대로 각각 세준다.
- $b=1$
- $a_j \ge M^{2/3}$ $\Longrightarrow$ $a_j \cdot b = a_k \le M \Longrightarrow b \le M^{1/3}$
- $a_j < M^{2/3}$
각각 1,2,3 번이라고 하면
배열에 어떤 수가 몇개 있는지 판단하는 시간복잡도를 무시해서 $O(1)$ 이라 할 때,
1번은 $O(n)$에 가능하고,
2번은 $b \le M^{1/3}$ 이고 $a_j$ 의 후보가 최대 $n$개라서 $O(n \cdot M^{1/3})$ 이면 된다.
3번은 $a_i \cdot b = a_j$ 이기 때문에 $b$의 후보를 $1$이 아닌 $a_j$ 의 약수로 제한할 수 있기 때문에 $a_j \le M^{2/3}$ 이고 약수들은 $O(\sqrt{X})$ 로 찾을 수 있어서 결국 $a_j \le M^{2/3}$ 인 $a_j$는 많아봤자 $n$개이기 때문에 $O(n \cdot M^{1/3})$ 에 해결된다.
따라서 $O(n \cdot M^{1/3} \cdot \alpha)$ 에 모두 검사할 수 있고, 해결 가능하다.
$\alpha$는 배열에 어떤 수가 몇개있는지 세는 시간복잡도이다. $O(\log N)$이 될 것이다.
const int MAX = 1e9;
void solve() {
int n;
cin >> n;
vi a(n);
fv(a);
sort(all(a));
auto cnt = [&](int x) {
return ubi(a, x) - lbi(a, x);
};
ll ans = 0;
for (int i = 0; i < n; i++) {
if (i == n - 1 || a[i] != a[i + 1]) {
ll c = cnt(a[i]);
ans += c * (c - 1) * (c - 2);
}
}
auto count = [&](ll aj, int b) -> ll {
if (aj % b) return 0;
int x = aj / b;
ll z = aj * b;
if (z > MAX) return 0;
int xc = cnt(x);
if (!xc) return 0;
int zc = cnt(z);
return 1ll * xc * zc;
};
for (int i = 0; i < n; i++) {
if (a[i] >= 1e6) {
for (int b = 2; b <= 1e3; b++) {
ans += count(a[i], b);
}
} else {
for (int b = 1; b * b <= a[i]; b++) {
if (a[i] % b == 0) {
if (b != 1) {
ans += count(a[i], b);
}
int b2 = a[i] / b;
if (b2 != b && b2 != 1) {
ans += count(a[i], b2);
}
}
}
}
}
cout << ans << endl;
}
Comments