Codeforces Round 882 (Div. 2)
어거지로 4솔해서 그냥 퍼플퍼포는 낸 대회였다.
A. The Man who became a God
가능한 $\vert a_i-a_{i-1} \vert$값 $n-1$개 중에 작은것 순으로 $n-k$ 개를 뽑으면 된다.
그룹을 분리한다는 것은 $\vert a_i-a_{i-1} \vert$ 을 원래 정답에서 제거할 수 있다는 뜻이기 때문이다.
B. Hamon Odyssey
$n$개의 수를 모두 $\&$해서 $0$이 나오지 않는다면 모두 하나로 합쳐주는게 항상 최적이기 때문에 정답은 $1$이다.
그렇지 않다면 각 그룹이 $0$이 되게끔 최대한 많이 묶어주면 된다.
void solveb() {
int n;
cin >> n;
vi a(n);
fv(a);
int sum = 0, ans = 0;
vi cnt(30);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 30; j++) {
if ((1 << j) & a[i]) {
cnt[j]++;
}
}
}
int bit = 0;
for (int i = 0; i < 30; i++) {
if (cnt[i] == n) bit |= (1 << i);
}
if (bit != 0) {
cout << 1 << endl;
return;
}
for (int i = 0; i < n;) {
int b = a[i];
int j = i + 1;
while (j < n && b != bit) {
b &= a[j++];
}
ans++;
i = j;
if (i == n && b != 0) {
ans--;
}
}
cout << ans << endl;
}
C. Vampiric Powers, anyone?
결론적으로 구간 $\oplus$ 최댓값을 구하는 문제였다.
엄밀한 증명하지 않고 적절히 관찰해서 풀어야 하는 문제였던것같다.
결국 어떤 $i$부터 $m$까지 모두 $xor$한 값을 새롭게 추가하든 어떻게하든 계속 제일 뒤부터 연속적으로 $xor$한 값이 나오고 제일 마지막엔 $i \sim n$까지는 필요없는 부분은 잘라내줄 수 있기 때문이다.
트라이를 구현할 필요는 없고 $a_i < 2^8$ 이라는 점을 이용해 $O(2^8 \cdot n)$ 으로 풀 수 있다.
void solvec() {
int n;
cin >> n;
vi a(n);
fv(a);
debug();
vi can(256);
int ans = 0;
for (int i = n - 1, x = 0; i >= 0; i--) {
x ^= a[i];
can[x] = 1;
maxa(ans, x);
maxa(ans, a[i]);
}
for (int i = 0; i < 256; i++) {
if (can[i]) {
for (int j = n - 1, x = 0; j >= 0; j--) {
x ^= a[j];
maxa(ans, i ^ x);
}
}
}
cout << ans << endl;
}
D. Professor Higashikata
$t_j$ 를 순회하며 $s$에서 어떤 인덱스 $i$가 가장 먼저 발견되는 시점을 기록한다.
그럼 $s$의 모든 $i$에 대해 먼저 발견되는 순서대로 재배치하여 새로운 문자열 $s'$ 를 만들 수 있다.
물론 한 번도 $t_j$ 에서 포함되지 않은 $i$도 있는데, 그건 따로 관리하자.
왜 $s'$ 를 만드냐면, 결과적으로 lexicographically largest를 만드려면 앞에 인덱스부터 $1$이 최대한 채워져야 이득이고 그건 $s$에서 $i$중 $t(s)$에서 처음 나오는 위치들로 표현했을 때 그것이 작을수록 $1$을 먼저 채워주는 것이 최적의 답이 나오기 때문이다.
어쨌든 $s'$ 에서 $1$의 개수를 $a$ 라고 할 때, $s'$의 길이 $a$의 prefix에 있는 $0$의 개수가 각 쿼리의 정답이 된다.
여기서 신경써줘야 할건 앞서 언급한 $t_j$ 에 포함되지 않은 $i$중 $1$ 들은 $s$ 에서 swap을 앞으로 해줄 수 있기 때문에 배제하고 생각하면 안된다는 점이다.
따라서 $a$ 에 그것들을 포함시켜주고, 쿼리에서도 $t_j$ 에 포함되지 않은 $i$는 $a$의 개수를 변동시키도록 해준다.
$t_j$ 에 포함되는 $i$들은 펜윅트리나 세그먼트트리같은 걸 이용해서 $\vert s' \vert$ 길이에서 $0$이 특정 구간에 얼마나 존재하는지 $O(\log \vert s' \vert)$에 쿼리할 수 있도록 전처리해두면 된다.
$s'$ 를 만드는 과정은 Disjoint set union으로 해주면 되고 이 테크닉은 BOJ 26087 문제로 연습할 수 있다.
template<class T>
struct fenwick {
int n;
vector<T> tree;
fenwick(int n) : n(n) { tree.resize(n + 1); }
T sum(int i) {
T ret = 0;
for (; i; i -= i & -i) ret += tree[i];
return ret;
}
void update(int i, T x) { for (i++; i <= n; i += i & -i) tree[i] += x; }
T query(int l, int r) { return l > r ? 0 : sum(r + 1) - sum(l); }
};
// endregion
struct DSU {
vector<int> p;
DSU(int n) : p(n, -1) {
}
int gp(int n) {
if (p[n] < 0) return n;
return p[n] = gp(p[n]);
}
void merge(int a, int b, int to_b = 1) {
a = gp(a), b = gp(b);
if (a == b) return;
if (!to_b && size(a) > size(b)) swap(a, b);
p[b] += p[a];
p[a] = b;
}
bool is_merged(int a, int b) { return gp(a) == gp(b); }
int size(int n) { return -p[gp(n)]; }
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
string s;
cin >> s;
vector<pi> range(m);
vi idx(n, -1), idx_rev(n, -1);
int nxt_num = 0;
DSU dsu(n + 5);
for (auto &[l, r]: range) {
cin >> l >> r, l--, r--;
for (int i = l; i <= r;) {
while (i <= r && idx[i] != -1) {
i = dsu.gp(i);
}
if (i <= r) {
idx_rev[nxt_num] = i;
idx[i] = nxt_num++;
dsu.merge(i, i + 1);
}
}
}
string t;
for (int i = 0; i < n; i++) {
if (idx_rev[i] != -1) {
t.pb(s[idx_rev[i]]);
} else break;
}
int one = cntt(t, '1');
fenwick<int> fenw(n);
for (int i = 0; i < sz(t); i++)
if (t[i] == '0') {
fenw.update(i, 1);
}
for (int i = 0; i < n; i++) {
if (idx[i] == -1 && s[i] == '1') {
one++;
}
}
debug(t);
while (q--) {
int x;
cin >> x, x--;
if (idx[x] == -1) {
if (s[x] == '0') {
one++;
} else {
one--;
}
} else {
if (s[x] == '0') {
one++;
fenw.update(idx[x], -1);
} else {
one--;
fenw.update(idx[x], 1);
}
}
s[x] = s[x] == '0' ? '1' : '0';
cout << fenw.query(0, one - 1) << endl;
}
}
E. Triangle Platinum?
F. The Boss’s Identity
에디토리얼의 설명을 참고한다.
$n=5$ 라고 하고 $[a,b,c,d,e]$ 라고 하자.
$a$를 제거하고 나머지 것들을 재배치해보면 다음과 같은 순서가 된다(규칙이 나온다).
항상 $n-1$ 주기마다 하나씩 길이가 늘어나며 바로 다음 row의 원소는 현재 그룹의 원소의 첫 원소의 바로 이전 원소가 붙는다.
비트 하나만 고려한다고 생각한다.
어떤 원소가 그 비트가 $0$이면 무시한다.
위 행렬에서 어떤 원소가 퍼져나가는 모습을 관찰하면 아래로 쭉 이동하고 오른쪽으로 한칸씩 더 전파된다.
이 $1$을 전파하는 과정을 빠르게 하는 방법은 결국 $n$개의 원소 중 해당 자리가 $0$인건 최대 $O(n)$에 국한된다는 것에 기반하는 것이다. ($0 \to 1$연산 횟수의 상한)
row가 증가할때마다 현재 수를 한칸 오른쪽으로 이동시키며 or 연산을 해준다.
예를 들어, $c$에서 시작한다고 하면 $c \to cd \to cde \to \cdots$ 같이 이동한다.
그러다가 현재 보고있는 비트에 대해서 이 그룹이 이미 $1$을 포함하고 있을 경우 전파를 중단한다.
이제 원래의 문제로 돌아와서 이것을 모든 비트 $31$ 개 정도에 대해서 모두 해주자.
그러면 $n$개의 자리마다 각 $0$이 $1$로 변했던 순서와 그 때의 값이 담기고 모든 자리의 이러한 수들을 모두 합치면 총 $O(n \log n)$ 개가 된다.
왜냐면 앞서 봤듯이 특정 자리의 특정 비트가 $0 \to 1$ 이 될 수 있는 가지수가 결국 $O(n \log n)$ 에 상한되기 때문이다.
이제 이걸 잘 구현해서 쿼리는 $O(n \log n)$ 개의 수들을 정렬해서 이분탐색이나 투포인터 등으로 구해줄 수 있다.
구현도 까다로운 편이다.
void solve() {
int n, q;
cin >> n >> q;
vi a(n);
fv(a);
vvi gain(n, vi(30, -1));
for (int k = 0; k < 30; k++) {
int b = 1 << k;
vector<pi> cand;
for (int i = 0; i < n; i++) if (b & a[i]) cand.pb({i, i});
while (sz(cand)) {
vector<pi> new_cand;
for (auto &[si, idx]: cand) {
if (~gain[si][k]) continue;
gain[si][k] = idx;
idx += n;
new_cand.pb({si == n - 1 ? 1 : si + 1, idx});
}
cand = new_cand;
}
}
vector<pi> values;
values.pb({0, a[0]});
for (int i = 1; i < n; i++) {
vi idx(30);
iota(all(idx), 0);
sort(all(idx), [&](int x, int y) { return gain[i][x] < gain[i][y]; });
int val = 0;
for (int k = 0; k < 30; k++) {
if (gain[i][idx[k]] == -1) continue;
val |= (1 << idx[k]);
values.pb({gain[i][idx[k]], val});
}
}
sort(all(values));
vector<pi> ret;
for (auto &[i, v]: values) {
if (!sz(ret) || ret.back().se < v) ret.pb({i, v});
}
vector<pi> qry(q);
vi ans(q, -1);
for (int i = 0; i < q; i++) cin >> qry[i].fi, qry[i].se = i;
sort(all(qry));
for (int i = 0, j = 0; i < q; i++) {
while (j < sz(ret) && ret[j].se <= qry[i].fi)j++;
if (j < sz(ret)) ans[qry[i].se] = ret[j].fi + 1;
else break;
}
for (int i = 0; i < q; i++) cout << ans[i] << endl;
}
Comments