Codeforces Round 882 (Div. 2)

July 7, 2023

어거지로 4솔해서 그냥 퍼플퍼포는 낸 대회였다.

A. The Man who became a GodPermalink

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 OdysseyPermalink

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?Permalink

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 HigashikataPermalink

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?Permalink

E. Triangle Platinum?

F. The Boss’s IdentityPermalink

F. The Boss’s Identity

에디토리얼의 설명을 참고한다.

$n=5$ 라고 하고 $[a,b,c,d,e]$ 라고 하자.

$a$ 를 제거하고 나머지 것들을 재배치해보면 다음과 같은 순서가 된다(규칙이 나온다).

\begin{matrix} b & c & d & e \\ ab & bc & cd & de \\ eab & abc & bcd & cde \\ deab & eabc & abcd & bcde \end{matrix}

항상 $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;  
}

Codeforces Round 882 (Div. 2)

A. The Man who became a GodPermalink

B. Hamon OdysseyPermalink

C. Vampiric Powers, anyone?Permalink

D. Professor HigashikataPermalink

E. Triangle Platinum?Permalink

F. The Boss’s IdentityPermalink

Comments

You may also enjoy

네트워크 개론 3판을 읽으며

250227 후반기 교육이 끝나간다

Docker 공부

군대에서의 공부 방향을 생각해보기