Educational Codeforces Round 149 (Rated for Div. 2)

대체적으로 쉬웠지만 E를 입력을 잘못봐서 못풀었다는게 아쉽다.

A. Grasshopper on a LinePermalink

A. Grasshopper on a Line

$k \nmid x$ 라면 $1$번으로 $x$로 가면 되고, $k \mid x$라면 $x-1$ 로 먼저 이동한다음에 $k \ge 2$ 이므로 $1$ 이동하면 된다.

B. Comparison StringPermalink

B. Comparison String

대회중에 문제푸는데 출력이 이상하긴 했는데 그냥 3분만에 풀긴했더니 막 공지가 올라오며 뭐 예제 잘못됐다고 다시 채점한다고 난리부르스였다.

그냥 > 나 < 중 연속된 길이중 가장 큰 것이 정답이다.

void solveB() {
   int n;
   string s;
   cin >> n >> s;
   int ans = 1;
   for (int i = 0; i < n; i++) {
      int j = i;
      while (j < n && s[i] == s[j])j++;
      maxa(ans, j - i);
      i = j - 1;
   }
   cout << ans + 1 << endl;
}
 

C. Best Binary StringPermalink

C. Best Binary String

? 이 없다고 할 때 뒤집어야 하는 횟수는 오른쪽부터 봤을 때 첫 번째 1 이나오기 전까지 0 으로 이어진 구간의 개수이다.

그리디하게 ? 옆에 하나라도 1 이 있다면 그냥 1 로 바꿔줘서 1 로 된 구간을 merge 시켜주는게 최적이다.

따라서 s[i-1] 이나 s[i+1] 이 1 인지를 검사하면 되는데,

문제는 ? 를 채울때도 s[i-1] 이 ? 에서 1 이 될 수 있기 때문에 그걸 적절히 처리해줘야 한다.

이걸 처리 안해줘서 두 번 틀렸다.

void solveC() {
   string s;
   cin >> s;
   int n = sz(s);
   vi psum(n + 1);
 
   int one = sz(s);
   string t = s;
   for (int i = 0; i < n; i++) {
      if (s[i] == '?') {
         if (i && t[i - 1] == '1' || i < n - 1 && s[i + 1] == '1') t[i] = '1';
         else t[i] = '0';
      }
   }
   cout << t << endl;
}

D. Bracket ColoringPermalink

D. Bracket Coloring

정답은 최대 2 이다. 누적 balance 값이 0 이 되는 부분들을 기준으로 구간으로 쪼갰을 때, 특정 구간은 항상 그 내부의 수들이 음수이고 특정 구간은 양수이기 때문이다.

따라서 음수인 구간과 양수인 구간을 각각 모두 합쳐주면 최대 $k \le 2$ 이다.

귀찮아서 세그먼트 트리로 풀었다.

void solve() {
   int n;
   string s;
   cin >> n >> s;
   // 홀수면 불가
   if (n % 2) {
      cout << -1 << endl;
      return;
   }
   vi a(n);
   seg_tree<int> seg(n);
   vi zeros{-1};
   int o = 0;
   for (int i = 0; i < n; i++) {
      if (s[i] == '(') o++;
      else o--;
      if (o == 0) zeros.pb(i);
      a[i] = o;
      seg.update(i, o);
   }
   if (o != 0) {
      cout << -1 << endl;
      return;
   }
   vi ans(n);
   debug(a);
   vi used(2);
   for (int i = 0; i < sz(zeros) - 1; i++) {
      int l = zeros[i] + 1;
      int r = zeros[i + 1];
 
      if (seg.query(l, r).min < 0) {
         for (int x = l; x <= r; x++) {
            ans[x] = 1;
            used[0] = 1;
         }
      } else {
         for (int x = l; x <= r; x++) {
            ans[x] = 2;
            used[1] = 1;
         }
      }
      // max
 
   }
 
   cout << acc(used) << endl;
   if (acc(used) == 1) {
      for (int &i: ans) i = 1;
   }
   for (int i: ans) cout << i << ' ';
   cout << endl;
}

E. Playoff FixingPermalink

E. Playoff Fixing

1시간 동안 고민해서 코드를 올바르게 짰지만 입력을 잘못봐서 $a_i$ 번째 팀이 $i$ 번째 시드를 받는게 아닌 $i$번째 팀이 $a_i$ 시드를 받는걸로 착각했다.

대회 끝나고 고쳤더니 바로 맞았다.

$2^k$ 명의 사람이 있을 때 $2^{k-1}$ 명의 $[2^{k-1}+1, 2^k]$ 팀들은 항상 바로 붙어있으면 안된다는 아이디어부터 풀어나가기 시작했다.

그렇다면 $[2^{k-2}+1, 2^{k+1}]$ 의 사람들은 $4$ 칸 안에 같이 있으면 안되고 등등이다.

전역적으로 $n$ 길이의 가능한 자리를 계속 관리한다. 코드의 available 변수

현재 보고있는 구간이 $[2^{x-1}+1, 2^{x}]$ 이라고 하자.

이 구간에 있는 사람들은 첫 칸부터 봤을 때 한 사람이 $2^{k-x}$ 칸을 차지해야한다.

$x=k-1$ 를 대입해보면 가장 먼저 떨어지는 사람들이 $2$칸씩 차지한다는 것을 생각하면 올바르다.
이 글에서 차지한다는 것은, 한 팀당 그 만큼 구간을 가지고 동일하게 떨어져야 할 다른 팀은 각 구간당 하나씩만 존재해야 하는 것을 의미한다.

어떤 $x$에서 시드가 고정된 사람들과 $-1$ 인 사람들을 보자.

그럼 길이 $\dfrac{n}{2^{k-x}}$ 짜리 cnt 라는 배열을 만들고 고정된 사람들이 각 구간에 몇명이 들어있는지 확인한다.

$n=2^k$

만약 어떤 곳에 $2$명 이상이 들어있다면 정답은 없다. 모두 $1$명이나 $0$명이 있어야 한다.

우린 그럼 $0$명인 곳에 시드가 고정되지 않은 사람들을 넣어줘야 한다.

이 사람들의 명수를 $f$ 라고 한다면 정답에 일단 $f!$ 를 곱해준다.

이후에 $\dfrac{n}{2^{k-x}}$ 개의 구간을 각각 검사하며 각 구간마다 available 변수를 이용해 몇 자리가 남았는지 파악한다.

여기서 한 자리도 남지 않았다면 정답은 없다.

어떤 구간에 $m$ 개의 자리가 남았을 때, 정답에 $m$ 을 곱해주면 된다.

그럼 $m$개의 자리 중 시드가 없는 사람을 어디에 넣을 수 있을까?

결론적으로 어디에 넣어도 정답에 영향을 끼치지 않는다이다.

왜냐면 $x$가 감소하는 순으로 순회하고 있기 때문에 그 다음 $x$에서 구간의 길이가 두 배 넓어지며, 이 구간과 옆 구간 하나에 남은 사람의 수만 중요하지 어디에 차있는지가 중요하지 않게 되기 때문이다.

이런식으로 $x \coloneqq k-1 \to 0$ 까지 순회하며 정답을 구할 수 있다.

시간복잡도 $O(k \cdot 2^k)$

const int MAX = 1'000'000;  
const ll mod = 998244353;  
inline ll md(ll x) { return md(mod, x); }  
vector<ll> fac(MAX + 1, 1LL);  
vi two(21, 1);  
void pre_calc() {  
   for (int i = 2; i <= MAX; i++) fac[i] = md(fac[i - 1] * i);  
   for (int i = 1; i <= 20; i++) two[i] = md(two[i - 1] * 2);  
}  
  
void solve() {  
   pre_calc();  
  
   int k;  
   cin >> k;  
   int n = 1 << k;  
   vi _a(n);  
   for (int i = 0; i < n; i++) {  
      cin >> _a[i];  
      //a[i] = -1;  
   }  
   for (int &i: _a) if (i != -1) i--;  
   vi a(n, -1);  
   for (int i = 0; i < n; i++) if (_a[i] != -1) a[_a[i]] = i;  
  
   int ans = 1;  
   vi available(n, 1);  
   for (int i: a) if (i != -1) available[i] = 0;  
  
   for (int x = k - 1; x >= 0; x--) {  
      int people = two[x], fixed = 0;  
      vi indice;  
      for (int j = two[x]; j < two[x + 1]; j++) if (a[j] != -1) fixed++, indice.pb(a[j]);  
      int free = people - fixed;  
      int d = two[k - x];  
  
      ans = md(ans * fac[free]);  
      vi cnt(n / d);  
      for (int x: indice) cnt[x / d]++;  
      for (int i: cnt) {  
         if (i > 1) {  
            cout << 0;  
            return;  
         }  
      }  
  
      int yes = 0;  
      for (int x = 0, y = 0; x < n; x += d, y++) {  
         if (cnt[y] == 1) continue;  
         yes++;  
         int l = x, r = x + d - 1, ac = 0, idx = -1;  
         for (int j = l; j <= r; j++) {  
            if (available[j]) {  
               idx = j;  
               ac++;  
            }  
         }  
         if (!ac) {  
            cout << 0;  
            return;  
         }  
         ans = md(ans * ac);  
         available[idx] = 0;  
      }  
      if (yes != free) {  
         cout << 0;  
         return;  
      }  
   }  
   cout << ans;  
}

F. Editorial for TwoPermalink

F. Editorial for Two

대회중에 보긴 했는데 세그먼트 트리로 왼쪽 오른쪽을 잘 스위핑하면 될 것 같긴 했는데,

다른사람 코드를 보니 binary search + priority queue로 풀어서 에디토리얼이 올라오면 한 번 풀어볼 예정이다.