Educational Codeforces Round 150 (Rated for Div. 2)

image.png

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

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

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

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

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

A. Game with Board

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 Beautiful

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 Numbers

C. Ranom Numbers

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

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

DP

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

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

으로 정의한다.

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

Greedy

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

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

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

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

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

Prefix sum

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

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

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

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 Segments

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 Matrix

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 Game

F. Monocarp and a Strategic Game

Comments

You may also enjoy