Educational Codeforces Round 150 (Rated for Div. 2)

June 13, 2023

뭐지 요즘 코포를 좀 풀었더니 코포 문제랑 친해졌는지 부계를 바로 퍼플보내버렸다.

사실 진짜 그런듯한 느낌이 들기도 한다.

unofficial로 180등이라 꽤나 높은 등수이다.

앞으로도 코포를 더 열심히 풀어야겠다.

더럽게 푼게 많아서 업솔빙은 내일 하도록 하자.

A. Game with BoardPermalink

A. Game with Board

$n=2,3,4$ 인 경우 어떤 경우로 해도 Alice가 진다는 것을 직접 확인했다.

$n \ge 5$ 인 경우, $1,1,1,1,1$ 에서 $n-2, 1, 1$ 을 만들면 $n-2 > 1$ 이기 때문에 Bob은 무조건 $n-2, 2$ 를 만들어야 하고 그럼 Alice는 할게 없어서 이기게된다.

즉 $n \ge 5$ 인 경우에는 Alice가, 그렇지 않으면 Bob이 이긴다.

B. Keep it BeautifulPermalink

B. Keep it Beautiful

모든 $i \coloneqq 0 \to n-2$ 에 대해 $a_i \le a_{i+1}$ 라면 항상 가능하다.

그렇지 않은 $i$ 가 하나 있다고 하자. 그런 $i$ 가 하나라면 가능할 수도 있다.

$a_i > a_{i+1}$ 라 할 때 $a_{i+1}$ 이 처음으로 되게 cyclic shift시켜야 하고 이 때 $a_{i+1} \le a_0$ 이여야 가능하다.

그러한 $i$ 가 두 개 이상이 되면 항상 불가능하다.

따라서 $a_i > a_{i+1}$ 인 것의 개수를 관리하며 새로운 숫자를 $a$ 제일 뒤에 붙여보고 이런 $i$ 가 $0$ 개면 가능, $1$ 개면 방금 붙인게 $a_0$ 이하일 때만 가능하다

$2$ 개 이상이면 불가능하다.

불가능한 경우 다시 원소를 떼준다.

void solve() {
   int n;
   cin >> n;
   vi a;
   vi x(n);
   fv(x);
   string ans;
   int dec = 0;
   for (int i = 0; i < n; i++) {
      if (i == 0) {
         ans += '1';
         a.pb(x[i]);
      } else {
         if (a.back() > x[i]) dec++;
         if (dec == 0) {
            a.pb(x[i]);
            ans += '1';
         } else if (dec == 1) {
            if (x[i] <= a[0]) {
               a.pb(x[i]);
               ans += '1';
            } else {
               ans += '0';
               if (a.back() > x[i]) dec--;
            }
         } else {
            ans += '0';
            if (a.back() > x[i]) dec--;
         }
 
      }
   }
   cout << ans << endl;
}

C. Ranom NumbersPermalink

C. Ranom Numbers

C번치고 좀 어려운 문제였다 실제로 중간까지 스코어 보드에 몇십명밖에 못풀정도였다.

난 구간합으로 열심히 풀었는데 DP(구간합)이나 그리디로 에디토리얼엔 나와있다.

DPPermalink

문자열을 뒤집고 왼쪽에 자신보다 큰 것이 있으면 sign을 바꾸는 것으로 재정의한다.

$dp[i][j][k]=i$ 번째 문자까지 봤을 때 변경을 사용했는지 여부 $k(=0 \ \text{or}\ 1)$ , 그리고 지금까지 만난 가장 큰 수가 $j(A \le j \le E)$ 일 때 최대값

으로 정의한다.

현재 $dp[i][j][k]$ 일 때, 현재 문자를 그대로 냅둘 수 있고, 혹은 $k=0$ 이라면 바꿀 수도 있다.

GreedyPermalink

놀랍게도 각 $A \sim E$ 에 대해 처음 나오는 위치와 끝나는 위치 최대 $10$ 개에 대해서만 다른 문자로 바꿀지 말지를 고려해주면 된다.

총 50가지 경우가 되고 $O(50n)$ 으로 풀 수 있다고 한다.

만약 문자를 더 크게 만드는 경우라면 이게 커져서 + 였다가 - 가 되는 문자들이 생긴다.

이런 문자는 최대한 적게 생기는게 좋기 때문에 가장 빨리 있는것을 바꾸는게 최적이 될 것이다.

문자를 더 작게 만드는 경우도 동일하다.

Prefix sumPermalink

내가 푼 방법인데, 난 실제 모든 자리의 모든 문자들을 바꿔 직접 값을 계산했다.

예를들어 문자를 더 크게 만드는 경우엔 + 였다가 - 가 되는 문자의 개수를 셌다.

각 문자가 나오는 인덱스를 관리하면 이것이 가능한데 복잡해서 코드만 투척한다.

int val(int i) {
   if (i == 0) return 1;
   if (i == 1) return 10;
   if (i == 2) return 100;
   if (i == 3) return 1000;
   if (i == 4) return 10000;
}
void solve() {
   string s;
   cin >> s;
   int n = sz(s);
   vvi psum(5, vi(n + 1));
   vi osum(n + 1);
   vvi idx(5);
   for (int i = 0; i < n; i++) idx[s[i] - 'A'].pb(i);
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 5; j++) {
         psum[j][i + 1] = psum[j][i] + (s[i] - 'A' == j);
      }
      osum[i + 1] = osum[i] + val(s[i] - 'A');
   }
   auto qry = [&](int k, int l, int r) {
      if (l > r) return 0ll;
      return psum[k][r + 1] - psum[k][l];
   };
   int cur_max = -1;
   int ans = 0;
   for (int i = n - 1; i >= 0; i--) {
      if (s[i] - 'A' < cur_max) ans -= val(s[i] - 'A');
      else ans += val(s[i] - 'A');
      maxa(cur_max, int(s[i] -'A'));
   }
   debug(ans);
   cur_max = -1;
   int oans = ans;
 
   // CDDE
   for (int i = n - 1; i >= 0; i--) {
 
      int cur = s[i] - 'A';
      idx[cur].pop_back();
      for (int to = 4; to >= 0; to--) {
         int tmp = oans;
 
         if (cur == to) continue;
         tmp -= val(cur) * (cur_max > cur ? -1 : 1);
         tmp += val(to) * (cur_max > to ? -1 : 1);
         if (to < cur) {
            // 더 작아진다면
            // 4 -> 3 이 된다면
 
            // 2 3 3 4
            int lidx = 0;
            if (sz(idx[cur])) lidx = idx[cur].back();
            for (int k = cur - 1; k >= to; k--) {
               if (cur_max > k) {
 
               } else {
                  // 원래 - 였다가 + 가 되는 것의 수
                  int bigger = 0;
                  bigger = qry(k, lidx, i - 1);
                  tmp += bigger * val(k) * 2;
               }
               if (sz(idx[k]))
                  maxa(lidx, idx[k].back());
            }
         } else {
            // 더 커진다면
            // 2 -> 4 가 된다고 하자.
            // 4 2 3 4
            int lidx = 0;
            if (sz(idx[to])) lidx = idx[to].back();
            //if (sz(idx[cur])) lidx = idx[cur].back();
            for (int k = to - 1; k >= cur; k--) {
               if (cur_max > k) {
 
               } else {
                  // 원래 + 였다가 - 가 되는 것의 수
                  int smaller = 0;
                  smaller = qry(k, lidx, i - 1);
                  tmp -= smaller * val(k) * 2;
               }
               if (sz(idx[k]))
                  maxa(lidx, idx[k].back());
            }
 
         }
         maxa(ans, tmp);
      }
      maxa(cur_max, cur);
   }
   cout << ans << endl;
}

D. Pairs of SegmentsPermalink

D. Pairs of Segments

$N$ 이 작은거보고 $O(N^2)$ 으로 어떻게 풀 생각을 했다.

내 풀이보단 에디토리얼 풀이를 정리한다.

사실 이 문제는 회의실 배정 문제로 치환될 수 있다.

모든 겹치는 segment $(i, j)$ 를 고려하고, 그것으로 새로운 segment $[\text{Min}(l_i, l_j), \text{Max}(r_i, r_j)]$ 를 형성한다.

이러한 새로운 segment는 최대 $O(n^2)$ 개이고 이것들로 회의실 배정 문제를 하면 된다.

회의실 배정문제는 끝점을 기준으로 정렬해야 하므로 $O(n^2 \log n^2)$ 정도로 풀 수 있다.

E. Fill the MatrixPermalink

E. Fill the Matrix

DSU + 적절한 처리로 풀었다.

문제는 우리에게 사용되는 segment의 개수를 최대한 작게 하라는 것을 요구한다.

왜냐면 segment가 하나 사용될 때마다 그것의 길이가 $L$ 이라면 $L-1$ 의 정답을 얻기 때문이다.

최악의 경우 최대 $O(n^2)$ 개의 segment가 생기기 때문에 압축된 형태로 저장하며 값을 계산해야 한다.

matrix를 위에서 아래로 보면 검은색이 끝날 때마다 segment들이 merge된다.

그런데 이걸 계속 모두 관리하는건 결국 $O(n^2)$ 라서 불가능하다.

현재 row가 $y$ 라고 하면 $a_i=y$ 인 $i$ 들만 고려한다.

어떠한 segment의 시작과 끝이 $l, r$ 이라면 현재 matrix에서의 row를 $y$ 라고 할 때 $ey=\text{Min}(a_{l-1}, a_{r+1})$ 이 그 다음 구간으로 확장되는 시점이다. 따라서 그걸 $r-l+1$ 길이의 segment를 $ey-y$ 개 얻었다고 볼 수 있다.

이런식으로 얻게되는 길이를 모두 카운트해둔다음에 큰 길이의 segment부터 $m$ 이 다 없어지거나 segment를 다 쓸 때 까지 정답에 더해주면 된다.

struct DSU {
   vector<int> p, l, r;
   DSU(int n) : p(n, -1), l(n), r(n) {
      iota(all(l), 0);
      iota(all(r), 0);
   }
   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];
      mina(l[b], l[a]);
      maxa(r[b], r[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 solvee() {
   int n;
   ll m;
   cin >> n;
   // column 에서 0 ~ a[i]-1 은 검은색 a[i] ~ n -1 은 흰색
   // 하나의 row에서 white로만 이루어진 연속된 구간들의 길이를 모두 구해야한다.
   // 연속된 구간의 길이가 k면 k - 1 개의 점수를 획득하고 k 개의 숫자를 소모한다.
   // 만약 k = 1 라면 행동을 취하지 않는다.
   vi a(n);
   fv(a);
   cin >> m;
   vi idx(n);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) {
      return a[i] < a[j];
   });
   ll ans = 0;
   vi alive(n);
   DSU dsu(n);
   vi seg_cnt(n + 1);
   for (int y = 0, j = 0; y < n; y++) {
      vi used;
      while (j < n && a[idx[j]] <= y) {
         alive[idx[j]] = 1;
         if (idx[j] != 0 && alive[idx[j] - 1]) {
            dsu.merge(idx[j] - 1, idx[j]);
         }
         if (idx[j] != n - 1 && alive[idx[j] + 1]) {
            dsu.merge(idx[j] + 1, idx[j]);
         }
         used.pb(idx[j]);
         j++;
      }
      vi nxt;
      for (int j: used) {
         if (j == dsu.gp(j)) {
            nxt.pb(j);
 
            int len = dsu.r[j] - dsu.l[j] + 1;
            int nxt_merge = n;
            int L = dsu.l[j], R = dsu.r[j];
            if (L != 0) mina(nxt_merge, a[L - 1]);
            if (R != n - 1) mina(nxt_merge, a[R + 1]);
 
            int added = nxt_merge - y;
            seg_cnt[len] += added;
         }
      }
   }
   debug(seg_cnt);
   for (int i = n; i >= 2; i--) {
      ll len = i;
 
      ll q = min<ll>(seg_cnt[i], m / len);
      seg_cnt[i] -= q;
      m -= q * len;
      ans += (len - 1) * q;
 
      while (m > 1 && seg_cnt[i]--) {
         ll added = min<ll>(m, len);
         m -= added;
         ans += max(0ll, added - 1);
      }
   }
   cout << ans << endl;
}
 

F. Monocarp and a Strategic GamePermalink

F. Monocarp and a Strategic Game

Educational Codeforces Round 150 (Rated for Div. 2)

A. Game with BoardPermalink

B. Keep it BeautifulPermalink

C. Ranom NumbersPermalink

DPPermalink

GreedyPermalink

Prefix sumPermalink

D. Pairs of SegmentsPermalink

E. Fill the MatrixPermalink

F. Monocarp and a Strategic GamePermalink

Comments

You may also enjoy

250626 일상과 나의 군생활

Swift Meta Type & .Self, & AnyClass

Any, AnyObject in Swift

iOS Hot-Reloading with Inject