Codeforces Round 855 (Div. 3)

Codeforces Round 855 (Div. 3)

버츄얼을 돌렸다.

상당히 빨리풀어서 꽤 잘푼편인데 현재 한시간 정도 남았는데 여기서 종료하고 마지막 문제는 에디토리얼을 보려 한다.

D는 문자열 해시밖에 안떠올라서 그걸로 냈더니 틀려서 이중해시로 AC를 받긴 했지만 정해가 아닌거같아서 에디토리얼을 봐야겠다.

---

A. Is It a Cat? (800)

A. Is It a Cat?

그냥 구현을 해줘도 되지만 regex 를 써서 냈더니 2000ms 제한에 1996ms이 찍히며 통과가 되었다.

역시 regex 는 느린거같다.

void solve() {
   int n;
   cin >> n;
   string s;
   cin >> s;
   if(re_include(s, "^[mM]+[eE]+[oO]+[wW]+$")) cout << "YES\n";
   else cout << "NO\n";
}

B. Count the Number of Pairs (1000)

B. Count the Number of Pairs

각 알파벳별로 대소문자 개수를 기록한다.

그걸 $s_i, b_i$ 라 하자.

$\text{Min}(s_i,b_i)$만큼 정답에 더해주고 $s_i$와 $b_i$ 각각 그만큼 뺀다.

이제 나머지 $\text{Max}(s_i,b_i)$를 최대 $k$ 가 될때까지 더해주고 정답에 더하면 된다.

void solve() {
   int n, k;
   cin >> n >> k;
   string s;
   cin >> s;
   vi cnt_small(26), cnt_big(26);
   for (char c: s) {
      if (c >= 'a' && c <= 'z') cnt_small[c - 'a']++;
      else cnt_big[c - 'A']++;
   }
   int ans = 0;
   int add = 0;
   for (int i = 0; i < 26; i++) {
      int mn = min(cnt_small[i], cnt_big[i]);
      ans += mn;
      cnt_small[i] -= mn;
      cnt_big[i] -= mn;
      int remain = max(cnt_small[i], cnt_big[i]);
      add += remain / 2;
   }
   cout << ans + min(add, k) << endl;
}
 

C1. Powering the Hero (easy version) (1000)

C1. Powering the Hero (easy version)

C2. Powering the Hero (hard version) (1100)

C2. Powering the Hero (hard version)

priority queue에 $0$이 아닌 수가 나올 때마다 쌓고 $0$이 나오면 개중 가장 큰 것을 정답에 더학 지워주는 것이 최적이다.

void solve() {
   int n;
   cin >> n;
   vi s(n);
   fv(s);
   ll ans = 0;
   priority_queue<int> pq;
   for (int i = 0; i < n; i++) {
      if (s[i] != 0) {
         pq.push(s[i]);
      } else {
 
         if (sz(pq)) {
            ans += pq.top();
            pq.pop();
         }
      }
   }
   cout << ans << endl;
}
 

D. Remove Two Letters (1200)

D. Remove Two Letters

내 풀이 - 해싱

구간합으로 이중해시 돌려서 풀었다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
const int MAX = 2e5;
int p1 = 2521, p2 = 31;
int POW1[MAX + 1], POW2[MAX + 1];
void pre_calc() {
   POW1[0] = 1;
   for (int i = 1; i <= MAX; i++) POW1[i] = md(POW1[i - 1] * p1);
   POW2[0] = 1;
   for (int i = 1; i <= MAX; i++) POW2[i] = md(POW2[i - 1] * p2);
 
}
inline ll poww(ll a, ll b) {
   ll ret = 1;
   while (b) {
      if (b & 1) {
         ret *= a;
         if (~mod) ret %= mod;
      }
      a *= a;
      if (~mod) a %= mod;
      b >>= 1;
   }
   return ret;
}
inline int inv(int x) { return poww(x, mod - 2); }
void solve() {
   int n;
   cin >> n;
   string s;
   cin >> s;
 
   vi psum1(n + 1), psum2(n + 1);
   for (int i = 0; i < n; i++) {
      int t = s[i] - 'a' + 1;
      psum1[i + 1] = md(psum1[i] + t * POW1[i]);
      psum2[i + 1] = md(psum2[i] + t * POW2[i]);
   }
   set<pi> hash;
   for (int i = 0; i < n - 1; i++) {
      int l = 0, r = i - 1;
      int H1 = 0, H2 = 0;
      if (l <= r) {
         H1 += psum1[r + 1];
         H2 += psum2[r + 1];
      }
      l = i + 2, r = n - 1;
      if (l <= r) {
         H1 += md(md(psum1[n] - psum1[l]) * inv(POW1[2]));
         H2 += md(md(psum2[n] - psum2[l]) * inv(POW2[2]));
      }
      H1 = md(H1);
      H2 = md(H2);
      hash.insert({H1, H2});
   }
   cout << sz(hash) << endl;
}
 

에디토리얼 풀이

$i, i+1$ 를 지우는 경우와 $i+1, i+2$를 지우는 경우를 고려한다.

전자는 $i+2$가 남고 후자는 $i$가 남는다.

$i$ 이전과 $i+2$ 이후는 두 경우 동일하게 남는다.

따라서 $s_i=s_{i+2}$ 인 경우를 세서 $n-1$ 에서 빼주는 것이 정답이다.

조금 더 생각해보자면 푸는 방법은 unique한 것을 세는 것이 아닌, 모든 가능한 경우의 수인 $n-1$ 개에서 불가능한 것들을 지우는 방식이다.

인접하지 않은 $i, j$ 에 대해 $i, i+1$ 과 $j, j+1$ 을 지워도 동일한 문자열이 나올 수는 있겠지만, 지울 때 동일한 문자열이 나오는 것이 있다면 항상 인접한 것 중에도 동일한 문자열이 나올 수 있다는 것에 기반한다.

위와 같은 경우 $A, B$ 를 각각 지워도 동일한 문자열이 얻어질 수 있지만, 그럼 위의 두 구간이 일치해야 한다는 것이고, $11, 13$ 번 문자가 하나만 일치하는 것이 저 구간이 모두 일치하는 것의 필요조건이라서 이것이 성립한다.

E1. Unforgivable Curse (easy version) (1400)

E1. Unforgivable Curse (easy version)

E2. Unforgivable Curse (hard version) (1500)

E2. Unforgivable Curse (hard version)

그냥 어디선가 $k+1$ 말고 $k$ 만 해서 주기를 어쩌구 하는 문제를 코포에서 본적이 있어서 보자마자 DSU로 인덱스들을 묶어 풀었다.

동일한 집합내에 존재하는 $s$와 $t$의 원소들이 모두 개수가 일치하면 가능하다.

void solve() {
   int n, k;
   cin >> n >> k;
   string s, t;
   cin >> s >> t;
   DSU dsu(n);
   for (int i = 0; i < min(n, k); i++) {
      for (int j = i; j < n; j += k) dsu.merge(i, j);
   }
   for (int i = 0; i < min(n, k + 1); i++) {
      for (int j = i; j < n; j += k + 1) dsu.merge(i, j);
   }
   vector<vector<char>> a(n), b(n);
   for (int i = 0; i < n; i++) {
      int p = dsu.gp(i);
      a[p].pb(s[i]);
      b[p].pb(t[i]);
   }
   for (int i = 0; i < n; i++) {
      sort(all(a[i]));
      sort(all(b[i]));
      if (a[i] != b[i]) {
         cout << "no\n";
         return;
      }
   }
   cout << "Yes\n";
}
 

에디토리얼 풀이

어차피 $k+1$ 와 $k$ 를 swap할 수 있다는 것은 boundary만 충분하다면 인접한것과 교체가 가능하다는 것을 의미한다.

따라서 이렇게 swap이 가능한 중앙 부분은 그저 알파벳 숫자를 세주고

그렇지 않은 부분들은 $s_i=t_i$ 인지 봐줘야 한다.

F. Dasha and Nightmares (1900)

F. Dasha and Nightmares

Trie를 이용해 풀었는데 정해가 비트마스크이다.

다음은 내 트라이 풀이이다.

이건 시간복잡도에 하자가 있지만 데이터셋이 약한건지 그냥 2700ms에 통과된다.

int n;
vs word;
vvi is_odd;
struct trie {
   int cnt = 0, depth;
 
   trie *t_odd = 0, *t_even = 0, *t_zero = 0;
 
   trie(int depth, int yes_cnt = 0) : depth(depth) {
 
   }
   void add(int i) {
      if (depth == 26) {
         cnt++;
         return;
      }
      int odd = is_odd[i][depth] % 2 == 1;
      int even = !odd && is_odd[i][depth] > 0;
      int zero = is_odd[i][depth] == 0;
 
      if (odd) {
         if (!t_odd) t_odd = new trie(depth + 1);
         t_odd->add(i);
      } else if (even) {
         if (!t_even) t_even = new trie(depth + 1);
         t_even->add(i);
      } else {
         if (!t_zero) t_zero = new trie(depth + 1);
         t_zero->add(i);
      }
   }
   int query(int i, int no_depth) {
      if (depth == 26) {
         return cnt;
      }
 
      int odd = is_odd[i][depth] % 2 == 1;
      int even = !odd && is_odd[i][depth] > 0;
      int zero = is_odd[i][depth] == 0;
 
      if (odd ^ even ^ zero != 1) {
         debug(i, depth, odd, even, zero);
      }
      assert(odd ^ even ^ zero == 1);
      if (depth == no_depth) {
         if (!t_zero) return 0;
         return t_zero->query(i, no_depth);
      } else if (zero) {
         if (!t_odd) return 0;
         return t_odd->query(i, no_depth);
      } else {
 
         if (odd) {
            // zero나 even
            int ret = 0;
            if (t_even) ret += t_even->query(i, no_depth);
            if (t_zero) ret += t_zero->query(i, no_depth);
            return ret;
         } else {
            if (!t_odd) return 0;
            return t_odd->query(i, no_depth);
         }
 
      }
   }
};
 
void solve() {
   cin >> n;
   word.resize(n);
   fv(word);
   is_odd = vvi(n, vi(26));
   for (int i = 0; i < n; i++) {
      for (char c: word[i]) {
         is_odd[i][c - 'a']++;
      }
   }
   trie *root = new trie(0);
   for (int i = 0; i < n; i++) {
      if (sz(word[i]) % 2 == 1) {
         root->add(i);
      }
   }
   debug(is_odd);
   ll ans = 0;
   for (int i = 0; i < n; i++) {
      if (sz(word[i]) % 2 == 0) {
         // 모든 알파벳을 다쓴 문자열이면 불가능
         // 안 쓴 알파벳중 제외할 것 하나만 고르고 나머지를 모두 가지게 해보자.
         // 쓴거라면 항상 even, odd를 결정할 수 있고
         // 안쓸 것이라면 항상 odd만 고르고
         // 안쓴 것인데 써야한다면 odd 를 고른다.
         for (int j = 0; j < 26; j++) {
            if (is_odd[i][j] == 0) {
               ans += root->query(i, j);
            }
         }
      }
   }
   cout << ans;
}
 

에디토리얼 풀이

생각을 해보면 이상하게 홀수가 있어야 된다는 조건이 많은것이 결국 $\oplus$해서 $1$ 인 것을 의미하는 것이였는데 생각을 못한것이 아쉽다.

$f(x)$가 $x$의 비트 수라고 한다면,

$f(a_i \vert a_j)=f(a_i \oplus a_j)=25$ 여야 한다는 것이 조건이다.

어떤 $a_i$에 대해 $26$개의 문자 중 쓰이지 않은 것들 중에 최종 문자열에도 안 쓰일 것을 정하면

항상 어떠한 counter bit를 결정할 수 있기 때문에 그것의 개수를 세면 된다.

G. Symmetree (2200)

G. Symmetree

그냥 트리 해싱이 정해이다.

Tree Isomorphism은 이전에 공부해서 몇개 문제를 푼 적이 있긴 한데 당장 필요한 내용이 아니라 넘기자.