[BOJ 24978] Subset Equality

https://www.acmicpc.net/problem/24978

24978번: Subset Equality

Sol 1) 메모이제이션 잘한 완탐

 

문자 집합 A에 대해 정답이 Y라면 A의 부분집합 B는 모두 Y다.

N이라면 A를 부분집합으로 갖는 집합 C는 모두 N이다. 

문자가 18개로 제한되어있으니 문자 집합의 종류는 \(2^{18} - 1\)개가 있을 수 있는데 정수 하나로 찌그려서 아래처럼 표현할 수 있다.

 

string tmp; cin >> tmp;
for(auto &i : tmp) x |= 1 << (i - 'a');

 

어떠한 과정을 통해서 상태 x에서 Y/N임을 알게 되었다면 x의 부분집합 또는 x를 부분집합으로 하는 집합을 모두 순회하며 아래와 같이 dp[i] = 1로 처리할 수 있다.

 

if(dp[x] == 1) for(int i = x; i > 0; i = ((i - 1) & x)) dp[i] = 1;
else for(int i = x + 1; i < 262144; i++) if((i & x) == x) dp[i] = 0;

 

그런데 이렇게 처리한다면 한번 계산한 dp[i]들을 다시 갱신하기 때문에 커팅이 좀 덜 될 것같다.

켜진 비트를 순서대로 하나씩 보는 것은 LSB를 꺼가면서 계속 \(O(1)\)에 체크할 수 있으니 재귀적으로 비트 하나씩을 끄거나 켜면 체크가 적은 시간을 먹을 것 같다.

 

void aa(int x) {
    dp[x] = 1;
    for(int t = x; t > 0; t -= t & -t) {
        if(dp[x ^ (t & -t)] == -1) aa(x ^ (t & -t));
    }
}

void bb(int x) {
    dp[x] = 0;
    for(int t = ~x & 262143; t > 0; t -= t & -t) {
        if(dp[x | (t & -t)] == -1) bb(x | (t & -t));
    }
}

 

aa는 x의 부분집합을, bb는 x를 부분집합으로 하는 집합을 재귀적으로 방문하는 함수다. 

~x & 262143에서 LSB를 쭉 뽑으면 x에서 꺼져있는 비트만 켤 수 있다. 

그러니 아래 코드보다는 빠를 것이다.

 

for(int i = 0; i < 18; i++) if(~x >> i & 1 and dp[x | (1 << i)]) bb(x | (1 << i));

 

출제자가 이런 어이없는 \(O(10^{10})\)짜리 풀이를 열심히 막지 않았을거라 기도하고 쿼리마다 x가 아직 계산되어있지 않을 때 aa 또는 bb를 실행시켜주며 갱신하면 460ms에 통과한다.....

S = T이고 쿼리 문자를 정수로 어그려뜨렸을 때 수인 x가 오름차순이 되도록 주어지면 항상 답이 Y일 것이고 aa는 x보다 작은 수만 갱신하기 때문에 나이브한것을 계속 새로 계산하고 최악이 될 것이다. 요건 데이터 뽑아서 데추주 올렸다.

 

PS) 문자 c를 c - 'a'로 보지 말고 문자마다 숫자를 0부터 17까지 랜덤하게 주면 오름차순이 깨져서 이 데이터에서도 다시 통과할거같은데, TLE가 잘 뜨네요 뭘까요..

+ 랜덤하게 주면 완전 오름차순은 아니어도 어쨌든 bitwise or하면 커지니 커지는 경향 자체는 유지되네요

 

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int n, m, q;
int dp[262144];
string s, t;

int f(int x) {
    int &ret = dp[x];
    if(~ret) return ret;
    int lo = 1, hi = 1;
    while(1) {
        while(lo <= n and ~x >> (s[lo] - 'a') & 1) lo++;
        while(hi <= m and ~x >> (t[hi] - 'a') & 1) hi++;
        if(lo == n + 1 and hi == m + 1) return ret = 1;
        if(lo == n + 1 or hi == m + 1) break;
        if(s[lo++] != t[hi++]) return ret = 0;
    }
    while(lo <= n and ~x >> (s[lo] - 'a') & 1) lo++;
    while(hi <= m and ~x >> (t[hi] - 'a') & 1) hi++;
    return ret = (lo == n + 1 and hi == m + 1);
}

void aa(int x) {
    dp[x] = 1;
    for(int t = x; t > 0; t -= t & -t) {
        if(dp[x ^ (t & -t)] == -1) aa(x ^ (t & -t));
    }
}

void bb(int x) {
    dp[x] = 0;
    for(int t = ~x & 262143; t > 0; t -= t & -t) {
        if(dp[x | (t & -t)] == -1) bb(x | (t & -t));
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    
    cin >> s >> t;
    n = s.size(); m = t.size();
    s = '#' + s; t = '#' + t;
    memset(dp, -1, sizeof dp);
    cin >> q;
    while(q--) {
        int x = 0;
        string tmp; cin >> tmp;
        for(auto &i : tmp) x |= 1 << (i - 'a');
        if(dp[x] == -1) {
            if(f(x)) aa(x);
            else bb(x);
        }
        if(dp[x]) cout << "Y";
        else cout << "N";
    }
    cout << endl;
}

 

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int n, m, q;
int HASH[256];
int dp[262144];
string s, t;

int f(int x) {
    int &ret = dp[x];
    if(~ret) return ret;
    int lo = 1, hi = 1;
    while(1) {
        while(lo <= n and ~x >> HASH[s[lo]] & 1) lo++;
        while(hi <= m and ~x >> HASH[t[hi]] & 1) hi++;
        if(lo == n + 1 and hi == m + 1) return ret = 1;
        if(lo == n + 1 or hi == m + 1) break;
        if(s[lo++] != t[hi++]) return ret = 0;
    }
    while(lo <= n and ~x >> HASH[s[lo]] & 1) lo++;
    while(hi <= m and ~x >> HASH[t[hi]] & 1) hi++;
    return ret = (lo == n + 1 and hi == m + 1);
}

void aa(int x) {
    dp[x] = 1;
    for(int t = x; t > 0; t -= t & -t) {
        if(dp[x ^ (t & -t)] == -1) aa(x ^ (t & -t));
    }
}

void bb(int x) {
    dp[x] = 0;
    for(int t = ~x & 262143; t > 0; t -= t & -t) {
        if(dp[x | (t & -t)] == -1) bb(x | (t & -t));
    }
}

struct RANDOM {
    random_device rg;
    mt19937 rd;
    RANDOM() { rd.seed(rg()); }
    int nxt(int l = 0, int r = 32767) { return uniform_int_distribution<int>(l, r)(rd); }
} rnd;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    
    vector<char> asdf(18);
    iota(asdf.begin(), asdf.end(), 'a');
    shuffle(asdf.begin(), asdf.end(), rnd.rd);
    for(int i = 0; i < 18; i++) HASH[asdf[i]] = i;
    cin >> s >> t;
    n = s.size(); m = t.size();
    s = '#' + s; t = '#' + t;
    memset(dp, -1, sizeof dp);
    cin >> q;
    while(q--) {
        int x = 0;
        string tmp; cin >> tmp;
        for(auto &i : tmp) x |= 1 << HASH[i];
        if(dp[x] == -1) {
            if(f(x)) aa(x);
            else bb(x);
        }
        if(dp[x]) cout << "Y";
        else cout << "N";
    }
    cout << endl;
}

---

Sol 2) 애드혹

 

P = 문자 집합 A에 대해 답이 Y임

Q = 크기가 2인 A의 모든 부분집합에 대해 답이 Y임

P->Q는 당연하게도 성립하고

Q->P의 대우명제인 ~P->~Q (문자 집합 A에 대해 답이 N임 -> 크기가 2인 A의 부분집합 중 하나 이상에 대해 답이 N임)이 성립하기 때문에

Q->P도 성립한다. 이제 Q를 검사해서 Y/N을 판단할 수 있다.

 

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int n, m, q;
int chk[18][18];
string s, t;

int f(int x) {
    int lo = 1, hi = 1;
    while(1) {
        while(lo <= n and ~x >> (s[lo] - 'a') & 1) lo++;
        while(hi <= m and ~x >> (t[hi] - 'a') & 1) hi++;
        if(lo == n + 1 and hi == m + 1) return 1;
        if(lo == n + 1 or hi == m + 1) break;
        if(s[lo++] != t[hi++]) return 0;
    }
    while(lo <= n and ~x >> (s[lo] - 'a') & 1) lo++;
    while(hi <= m and ~x >> (t[hi] - 'a') & 1) hi++;
    return lo == n + 1 and hi == m + 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    
    cin >> s >> t;
    n = s.size(); m = t.size();
    s = '#' + s; t = '#' + t;
    for(int i = 0; i < 18; i++) {
        for(int j = 0; j < 18; j++) {
            if(f((1 << i) | (1 << j))) chk[i][j] = 1;
        }
    }
    cin >> q;
    while(q--) {
        string tmp; cin >> tmp;
        int f = 1;
        for(auto &i : tmp) for(auto &j : tmp) f &= chk[i - 'a'][j - 'a'];
        if(f) cout << "Y";
        else cout << "N";
    }
}