BOJ 24978 - Subset Equality

BOJ 24978 - Subset Equality

개인적으로 아이디어는 금방 보였다.

$a \sim r$은 $18$개밖에 안되기 때문에 $18^2(Q+N)$ 정도로 풀 수 있다.

가능한 모든 경우에 대해 미리 전처리를 해두는 것이다.

만약 $s$와 $t$에 각각 어떤 알파벳 $c$가 서로 다른 횟수가 나온다면 그 알파벳이 들어가면 항상 불가능하다.

그렇지 않고 $A, B$가 서로 다른 알파벳이라고 하자.

문자열에서 A의 개수와 B의 개수를 본다.

더 작은 것을 쭉 순회하며 나머지 인덱스들의 위치가 이분탐색을 해서 $s,t$ 모두 같게 나오면 그 문자 두개는 같이 나와도 문제가 없다.

이런 최적화는 필요가 없긴 하다.

여러 문자가 같이 set에 있을 때 아무 두 문자에 대해 모두 만족해야 하는것이 필요충분조건이라 $O(18^2)$에 검사해줄 수 있다.

$\vert s \vert \neq \vert t \vert$ 인 경우도 가능하다는 것을 주의한다.

int ok[18][18];
void solve() {
   for (int i = 0; i < 18; i++) for (int j = 0; j < 18; j++) ok[i][j] = 1;
   string s, t;
   cin >> s >> t;
   int q;
   cin >> q;
   vvi idxs(18), idxt(18);


   for (int i = 0; i < sz(s); i++) {
      idxs[s[i] - 'a'].pb(i);
   }
   for(int i = 0 ;i < sz(t); i++) {
      idxt[t[i] - 'a'].pb(i);
   }
   for (int i = 0; i < 18; i++) {
      if (sz(idxs[i]) != sz(idxt[i])) {
         for (int j = 0; j < 18; j++) ok[i][j] = ok[j][i] = 0;
      }
   }
   for (int i = 0; i < 18; i++) {
      for (int j = 0; j < 18; j++) {
         if (!ok[i][j]) continue;
         int I = i, J = j;
         if (sz(idxs[I]) > sz(idxs[J])) swap(I, J);
         for (int i1 = 0; i1 < sz(idxs[I]); i1++) {
            int chk1 = lbi(idxs[J], idxs[I][i1]);
            int chk2 = lbi(idxt[J], idxt[I][i1]);
            if (chk1 != chk2) {
               ok[i][j] = ok[j][i] = 0;
               break;
            }
         }
      }
   }

   for (int i = 0; i < q; i++) {
      vi idx;
      string s;
      cin >> s;
      for (char c: s) idx.pb(c - 'a');
      int yes = 1;
      for (int c1: idx) for (int c2: idx) if (!ok[c1][c2]) yes = 0;
      if (yes) cout << 'Y';
      else cout << 'N';
   }
}