Codeforces Round 880 (Div. 2)
B,C 도 그리 쉬운 편은 아니였는데 D부터 갑자기 미친놈처럼 어려워져서 스피드포스에 성공해 44분경 C를 풀었을 때 70 몇등이였는데 대회가 끝날때까지 두자리수 스탠딩을 유지할 수 있었다.
A. Destroyer (00:02 +)
각 수들의 개수를 세둔다. 그걸 $c_i$ 라 하자.
만약 $c_{i+1} > c_i$ 라면 불가능하다.
void solve() {
int n;
cin >> n;
vi a(n);
fv(a);
sort(all(a));
vi cnt(101);
for (int i: a) cnt[i]++;
for (int i = 1; i <= 100; i++) {
if (cnt[i]) {
if (cnt[i - 1] < cnt[i]) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
B. Astrophysicists (00:27 +)
이때부터 지문이 심상치 않았는데, 깡수학문제가 쳐나와서 곤혹스러웠다.
어떤 사람에게 최대로 코인을 많이 뺐을 수 있는 경우는 $Q \cdot g+\left\lfloor \dfrac{g-1}{2} \right\rfloor$ 처럼 주는 방법이다.
그럼 $\left\lfloor \dfrac{g-1}{2} \right\rfloor$ 만큼 이득을 볼 수 있기 때문이다.
따라서 일단 모든 사람에게 $n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor$ 을 준 다음 생각해보자.
만약 $kg < n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor$ 라면 정답은 항상 $kg$ 이다. 모든 사람에게 다 최대로 이득을 얻을 수 있기 때문이다.
그렇지 않다면 $\left\lfloor \dfrac{kg-n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor}{g} \right\rfloor \cdot g$ 만큼의 실버 코인은 원래 가지고 있던 코인에서 빼준다.
한명의 astrophysicist에게 모두 골드 코인을 하나 몰아준 셈이다.
이제 나머지 남은 코인 개수를 $k$ 라고 하면 한명한테 최대 $g$ 개를 줄 때 까지 골드 코인을 하나만 더 소모하면 되므로 $\left\lceil \dfrac{k}{g} \right\rceil$ 만큼 골드 코인을 더 소모하게 된다.
void solve() {
int n, k, g;
cin >> n >> k >> g;
int s = k * g;
int should = (g - 1) / 2;
if (should * n >= k * g) {
cout << k * g << endl;
} else {
s -= should * n;
int q = s / g;
s -= q * g;
int ans = q;
ans += (s + g - 1) / g;
cout << k * g - ans * g << endl;
}
}
C. k-th equality (00:41 +)
시간복잡도를 잘 파악하자. 오직 5개의 케이스만 $A,B,C$ 가 백만까지 나오므로 $O(N)$ 을 짜기만 하면 충분히 $O(5000000)$ 정도로 풀 수 있다는 셈이다.
$a,b,c$ 모두 가장 작은값과 큰값을 구한다. $A=5$ 라면 $a_s=10000, a_e=99999$ 같은 식이다.
$a$ 를 모두 순회하며 가능한 경우를 파악한다.
$c_s,c_e$ 를 기준으로 보면 $c_s$ 가 되기 위한 $b$의 값이 정해진다. 그건 $c_s-a$ 이다.
마찬가지로 $c_e-a$ 와 같이 $b$의 값의 범위가 나온다.
그걸 원래 $b_s, b_e$와 교차시켜서 중복되는 구간만큼 $k$ 를 빼줄 수 있다.
만약 $k$ 를 모두 뺄 수 없는 구간이 나온다면 $O(n)$으로 직접 그게 뭔지 구해줄 수 있다.
void solve() {
int A, B, C, k;
cin >> A >> B >> C >> k;
int astart = stoll("1" + string(A - 1, '0'));
int aend = stoll(string(A, '9'));
int bstart = stoll("1" + string(B - 1, '0'));
int bend = stoll(string(B, '9'));
int cstart = stoll("1" + string(C - 1, '0'));
int cend = stoll(string(C, '9'));
// b가 정해지면 c도 정해진다.
for (int a = astart; a <= aend; a++) {
int bs = cstart - a;
int be = cend - a;
maxa(bs, bstart);
mina(be, bend);
if (bs > be) continue;
int cnt = be - bs + 1;
if (k > cnt) k -= cnt;
else {
for (int b = bstart; b <= bend; b++) {
if (to_string(a + b).size() == C) {
k--;
if (k == 0) {
cout << a << " + " << b << " = " << a + b << endl;
return;
}
}
}
}
}
cout << -1 << endl;
}
D. Lottery
TBD…
E. Twin Clusters
에디토리얼 풀이
구간합 배열로 풀 수 있다. 그리고 비둘기 집의 의해 결론적으로 정답은 항상 존재하게 된다.
입력의 제한을 심도있게 고려한다.
$n=2^{k+1}$ 이고 $g_i < 2^{2k}$ 이다.
$n$이 $2^k$ 의 두배이고 모든 값은 $2^{2k}$ 미만이므로 뭔가 절반으로 나누는 테크닉이 쓰일 것 같다고 유추할 수 있다.
처음 $k$ 개의 비트만 이용해서 구간합 배열을 만든다고 해보자.
$\oplus_{i=0}^x g_i$ 가 이미 등장했었다면 그 인덱스가 $y$ 라면 $[y+1,x]$ 구간은 $\oplus$합이 $0$이다.
$n=2^{k+1}$ 이고 $2^{k}$ 개의 수만 존재하기 때문에 이러한 구간은 최소 $2^k+1$ 개가 나온다.
왜냐면 처음 빈 구간은 $\oplus$합이 $0$ 인걸로 포함해 줬기 때문이다.
앞에 $2^k$ 개 까지 모두 다르다고 해도 비둘기 집의 원리에 의해 뒤에 $2^k$ 는 항상 적어도 하나랑 얻어걸리고 앞에서 $2^k$ 개 중에 $0$ 인 것이 하나 있어야 해서 $2^k+1$ 개가 나오는 것이다.
그럼이제 이러한 구간들이 최소 $2^{k}+1$ 개이므로, 이 구간들을 가지고 처음 $k$ 개의 비트를 제외한 뒤에 $k$ 개의 비트만 고려한다.
이 구간들은 $xor$ 합이 앞에 $k$개는 $0$ 이 나오기 때문에 뒤만 고려하게 된 것이다.
그럼 이제 또 $2^{k}+1$ 개이기 때문에 비둘기집 원리로 또 뒤에 $k$개의 비트만 봤을 때도 동일한 것이 생긴다.
그 두 구간이 disjoint하면 그게 정답이고 그렇지 않다면 겹치는 부분을 두 구간에서 모두 제외한 것이 정답이다.
후자의 경우 항상 겹치는 구간을 제거해도 구간의 길이가 남냐가 의문일 수 있는데, 처음 $2^{k+1}$개의 구간을 구하는 과정을 보면 구간들의 $s, e$ 가 모두 다름을 알 수 있다.
$e$ 는 원래 하나의 인덱스당 하나의 구간만 만들어지기 때문에 모두 다르고 $s$ 는 구간을 만드는 과정에서 현재 $\oplus$ 구간합 값의 인덱스를 현재로 덮어씌워주는 방식으로 해결한다.
$s_1=s_2$ 인 구간이 되려면 $e_1 + 1 \sim e_2$ 까지의 $\oplus$이 모두 같다는건데, 그럼 $e_1 +1 \sim e_2$ 까지의 구간이 만들어졌어야 했으므로 모순이다.
void solve() {
int k;
cin >> k;
int n = 1 << (k + 1);
vi g(n + 1);
fv1(g);
vi bit_idx(1 << k, -1);
bit_idx[0] = 0;
vector<pi> bit_seg(1 << k, {-1, -1});
for (int i = 2; i <= n; i++) g[i] ^= g[i - 1];
for (int i = 1; i <= n; i++) {
if (bit_idx[g[i] >> k] != -1) {
// new segment
int s = bit_idx[g[i] >> k] + 1, e = i;
int other_bits = g[e] ^ g[s - 1];
if (bit_seg[other_bits].fi == -1) {
bit_seg[other_bits] = {s, e};
} else {
auto [s2, e2] = bit_seg[other_bits];
if (s2 > e || e2 < s) {
cout << s2 << ' ' << e2 << ' ' << s << ' ' << e << endl;
} else {
cout << min(s, s2) << ' ' << max(s2, s) - 1 << ' ' << e2 + 1 << ' ' << e << endl;
}
return;
}
}
bit_idx[g[i] >> k] = i;
}
}
Comments