SCPC 2023 Round 2

3, 4번은 맞왜틀을 외치며 머릿속을 정리하기 위해서 문제를 풀며 작성.

2, 3번에서 패널티 관리가 너무 안되었고, 개인적으로 4, 5의 subtask가 너무 쉽다 생각해서 이악물고 4를 풀었다.

N을 여러모로 빡빡하게 준 것 같다.

사실 나조차도 log가 붙은 풀이들을 먼저 냈었기에 이해는 가는 선택이다.

1차 예선은 잘 기억이 안나고, 2차 예선들도 나름 아이디어틱해서, 본선에서 IQ 테스트 당할 것 같다.

작년 본선에서 2시간인가 동안 구성적인 문제를 풀었던 기억이 난다.

 

문제 1. 타이젠 윷놀이

 

어차피 한 바퀴 도는데는 윷을 20번 이하로 던져도 충분하다.

따라서 모든 0 <= i < n에 대해서 윷놀이판 한 바퀴를 돌면 도달하는 to[i]를 구하는데에는 20*n 이하로 충분하다.

입력이 a[0], a[1], ... a[n - 1]이라고 생각한다면, 지름길을 타지 않을 경우 a[i] + a[i + 1] + ... + a[j - 1] > 20인 j가 to[i]다.

to[i]는 n을 넘을 수 있다.

 

to[i]라는 값을 이용해서 nxt[i] = pair(a, b)를 만들자. 

to^b[i] = to[ to[ ... to[i] ... ] ] = a >= n이 되는 최초의 a, b를 의미한다.

nxt는 i = n - 1부터 역방향 만들어나가면

-> to[i] >= n이면 그냥 nxt[i] = {to[i], 1}

-> to[i] < n이면 nxt[i] = {nxt[to[i]].first, nxt[to[i]].second + 1}

nxt를 구했다면, cur = 0부터, nxt[cur]을 k번 타고 가면 된다.

cf) 사실 nxt를 0부터 타고가면, 맨앞의 2~30개만 계속 나타나니 이들에 대해서만 nxt를 O(N)로 구해도 된다.

 

문제 2. 괄호문자열

 

문제를 잘못이해해서 조금 헤맸다.

기본 아이디어는 i번부터 j - 1번까지의 괄호 문자열이 가능하다면 i와 j를 DSU로 merge하는 것이다.

그렇다면, merge된 것의 크기가 x라면 x * (x - 1) / 2의 합을 구하면 된다.

i - j, j - k가 만일 연결이 가능하다면, 당연하게도 i - k까지도 당연히 괄호 문자열이 가능하기 때문이다.

 

아무튼 i - j가 연결이 되었다고 가정하자.

만약에 i - 1번 문자와 j번 문자가 매칭된다면 아주 기쁘게도 (i - 1)과 (j + 1)이 연결될 수 있는 가능성이 생긴다.

따라서 merge가 될 때마다 queue에 넣고, pop을 하면서 그 그룹의 양쪽 끝을 매칭시켜보는 작업을 하면 된다

const int MAXN = 1e6;
int p[MAXN + 10], L[MAXN + 10], R[MAXN + 10];
int find(int x){
    if(p[x] < 0) return x;
    return p[x] = find(p[x]);
}
int merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return 0;
    p[y] += p[x];
    L[y] = min(L[y], L[x]);
    R[y] = max(R[y], R[x]);
    p[x] = y;
    return 1;
}
 
bool match(char x, char y){
    if(x == '(' && y == ')') return true;
    if(x == '{' && y == '}') return true;
    return false;
}
 
int main(){
    IOS
 
    int T; cin >> T;
    for(int cnum = 1; cnum <= T; cnum++){
        int n; cin >> n;
        string S; cin >> S;
        ll ans = 0;
 
        memset(p, -1, sizeof(int) * (n + 1));
        queue<int> q; 
        for(int i = 0; i <= n; i++){
            L[i] = i;
            R[i] = i;
            q.push(i);
        }
        while(!q.empty()){
            int x = q.front(); q.pop();
            x = find(x);
            if(L[x] == 0 || R[x] == n) continue;
            if(!match(S[L[x] - 1], S[R[x]])) continue;
            if(merge(L[x] - 1, R[x] + 1)) q.push(L[x] - 1);
        }
        for(int i = 0; i <= n; i++){
            if(i == find(i)) ans += 1ll * (-p[i]) * (-p[i] - 1) / 2;
        }
        cout << "Case #" << cnum << endl;
        cout << ans << endl;
    }    
}

 

문제 3. 루머

 

dp[x][y] = (x번째 사람이 마지막으로 S0에 속하고, |S0| = y일 때의 최댓값)

그렇다면 dp[cur][y] = MAX(dp[x][y - 1] + more(x, cur))이 된다. (단, x < cur)

이 식을 보면 알겠지만, more(x, cur)은 y와 무관하여, dp를 생각하는게 그렇게까지 복잡하지 않다.

내 계획은 dp[*][y]를 각 y에 대해 O(N)으로 채워서 총 O(N * N)으로 끝내는 것이다.

 

우선 다음과 같이 array L, R, Lc, Rc를 정의하자.

L, R = 자신의 각각 왼쪽, 오른쪽에 있는 귀가 두꺼운 사람의 위치. 단, 자신은 포함하지 않는다.

Lc[i] = max(L[i] + 1, i - t) 

Rc[i] = min(R[i] - 1, i + t)

-> 예를 들어 만약에 i 혼자 S0에 포함된다면 St는 [Lc[i], Rc[i]]가 될 것이다.

-> 따라서 dp의 초기값 dp[x][1]을 모두 Lc[x] - Rc[x] + 1로 설정해두자.

 

우리는 다음과 같이 (x < cur)인 x들을 나눌 수 있다.

1) Rc[x] < Lc[cur]

-> 이 경우 단순하게 [Lc[cur], Rc[cur]]가 추가된다고 여겨도 된다. (조금 문제가 있지만 2)에서 다룸)

-> 즉 dp[cur][y] = dp[x][y - 1] + (Rc[cur] - Lc[cur] + 1)

-> Lc, Rc는 모두 증가수열이기 때문에 단순하게 이런 dp[x][y - 1]의 최대값 Max1을 관리해주면 된다.

2) Rc[x] < Lc[cur]이지만, 그 경계에 귀가 두꺼운 사람이 있는 경우

-> 위의 부등호를 만족하지만 x + t >= R[x] = L[cur] >= cur - t라면 두꺼운 사람이 루머를 믿게 된다.

-> 따라서 이 경우에는 dp[cur][y] = dp[x][y - 1] + (Rc[cur] - L[cur] + 1)이 된다.

-> 이러한 dp[x][y - 1]의 최댓값 Max2를 관리해주자.

-> 어차피 한 x는 R[x]에만 관여할 수도 있기 때문에 오직 한 번만 나타나기에 평균 O(1), 총 O(N)이다.

3) Rc[x] >= Lc[cur]인 경우

-> 일반적으로 이럴 경우에는 굳이 cur에 꽂을 필요 없이 cur + 1에 꽂는 것이 더 이득이다.

-> 따라서 cur + 1에 꽂을 수 없는 경우만 고려해주면 된다.

-> 이러한 경우는 cur 자체가 귀가 두꺼운 사람이거나, cur = n - 1일 때이다.

-> 물론 이렇게 하면 dp에 정확한 숫자가 꽃히지는 않지만, 답에 관여하지 않는 값이라 상관 없다.

const int MAXN = 5000 + 10;
int dp[MAXN][MAXN];
int L[MAXN], R[MAXN], Lc[MAXN], Rc[MAXN], ear[MAXN];
 
signed main(){
    IOS
    
 
    int T; cin >> T;
    for(int cnum = 1; cnum <= T; cnum++){
        int n; cin >> n;
        for(int i = 0; i < n; i++){
            cin >> ear[i];
        }
        int m, t; cin >> m >> t;
        for(int i = 0, j = -1; i < n; i++){
            L[i] = j;
            Lc[i] = max(L[i] + 1, i - t);
            if(ear[i] == 2) j = i;
        }
        for(int i = n - 1, j = n; i >= 0; i--){
            R[i] = j;
            Rc[i] = min(R[i] - 1, i + t);
            if(ear[i] == 2) j = i;
        }
        for(int i = 0; i < n; i++) dp[i][1] = (Rc[i] - Lc[i] + 1);
        
        for(int j = 2; j <= n; j++){
            int g1 = 0, max1 = 0, max2 = -1e9;
            dp[0][j] = dp[0][1];
            for(int i = 1; i < n; i++){
                dp[i][j] = dp[i][j - 1];
 
 
                while(Rc[g1] < Lc[i]){
                    max1 = max(max1, dp[g1++][j - 1]);
                }
                dp[i][j] = max(dp[i][j], max1 + Rc[i] - Lc[i] + 1);
 
 
                if(L[i] >= i - t) dp[i][j] = max(dp[i][j], max2 + Rc[i] - L[i] + 1);
                if(ear[i] == 2){
                    max2 = -1e9;
                    for(int k = i - 1; k >= i - t && k >= 0; k--){
                        max2 = max(max2, dp[k][j - 1]);
                        if(ear[k] == 2) break;
                    }
                }
 
                if(i == n - 1 || ear[i] == 2){
                    for(int k = i - 1; k >= g1; k--){
                        dp[i][j] = max(dp[i][j], dp[k][j - 1] + Rc[i] - Rc[k]);
                        if(ear[k] == 2) break;
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++) for(int j = 0; j <= m; j++) ans = max(ans, dp[i][j]);
        cout << "Case #" << cnum << '\n' << ans << endl;
    }
 
}

 

문제 4. 막대기 연결

 

O(NQ)의 풀이는 다음과 같다.

a번부터 b번까지의 모든 막대기를 살펴보며 stack을 다음과 같이 관리하자.

stack에 y가 x보다 위에 있다면 (x < y), 반드시 h[x] < h[y]가 성립하도록 pop을 하면서 push를 하자.

이렇게 하는 이유는 만일 h[x] > h[y]라면, y보다 큰 z에 대해서 반드시 (y, z)로 사각형을 만들지, 절대로 (x, z)를 안 만든다.

따라서 top이 나보다 작아질 때까지 pop하면서 top과 사각형을 만들어주면서 답과 비교해주면 된다.

모든 쿼리에 대해서 a부터 b까지 돌면서 스택을 만들어주면 답을 구할 수 있다.

 

왜인지 모르겠지만, 전체 구간에 대한 쿼리를 관리해도 문제가 없을 것 같다.

즉 전체 구간에 대해서 보면서 스택을 만들자.

x번 막대기와 y번 막대기를 이용해서 사각형을 만들어 보는 순간이 온다고 가정하자.

그러면 x와 y를 보유하는 모든 쿼리에 대해서 그 쿼리의 답과 비교해준다.

signed main(){
    IOS
    
    int T; cin >> T;
    for(int cnum = 1; cnum <= T; cnum++){
        cout << "Case #" << cnum << endl;
        cin >> n;
        for(int i = 0; i < n; i++) cin >> x[i] >> h[i];
 
        int q; cin >> q;
        vi ans(q, INF), a(q), b(q);
        for(int i = 0; i < q; i++){
            cin >> a[i] >> b[i]; a[i]--, b[i]--;
        }   
        
        stack<int> st; st.push(0);
        for(int i = 1; i < n; i++){
            while(!st.empty()){
                int cur = (x[i] - x[st.top()]) * (h[i] + h[st.top()]);
                for(int j = 0; j < q; j++){
                    if(a[j] <= st.top() && i <= b[j]) ans[j] = min(ans[j], cur);
                }
                if(h[st.top()] < h[i]) break;
                st.pop();
            }
            st.push(i);
        }
        for(int i = 0; i < q; i++) cout << ans[i] << endl;
    }
}

위의 풀이를 보면 for(j = 0; j < q; j++)를 돌면서 ans를 갱신하는데, 저 작업을 자료구조로 잘 해주면 된다.

 

위의 풀이가 만일 틀렸다면, 어떤 x번째 쿼리에 대해서, 실제로 답이되는 사각형을 고려하지 않은 것이다.

그러면 i번, j번 막대기를 통해 만든 사각형이 최솟값이고, 이를 고려하지 않았다고 가정하자.

1) j번 막대기를 볼 때 stack에 i가 존재한다면

-> 만일 i가 top이라면 당연히 i, j로 사각형을 만들어 봤을 것이다. (고려되지 않음에 모순)

-> 만일 top이 아니라면, 어떤 k (h[i] < h[k] < h[j])가 top으로 있을 것인데, (i, k)가 (i, j)보다 작으니 최소임에 모순

2) j번 막대기를 볼 때 stack에 i가 존재하지 않는다면

-> i를 pop 시켜버린 k가 존재한다. (k, j)가 (i, j)보다 더 작으니 마찬가지로 모순

 

5. 스마트 아파트 건설

 

단순한 N! 브루트포스 돌려보고 끝냈다.

솔브드 디코를 눈팅하다가 대충 해설을 보아서 써본다. (짜보지 않아서 확실치 않음)

 

bitmask[ x ] = (x에서 비트가 1이면 비어있는 것이라고 생각했을 때, 여기까지 점들에 숫자를 부여하는 경우의 수)

즉, 만약에 y번째 배치를 한다면, 켜진 비트가 (N - y + 1)개인 상태들에서 (N - y)인 비트들로 전달해주면 된다.

1) 만일 k >= N + 1이라면

-> 이 경우 1은 아무 위치에 배정되어도 전혀 상관이 없다.

-> 1을 아무곳에 배치한다. (현재 상태가 x라면, N - y + 1개의 다른 상태로 옮겨갈 것이다)

-> 앞으로의 숫자들은 모두 2 이상이므로, 앞으로의 숫자 배정은 (N - 1,  k - 2)와 동일하다.

2) 만일 k <= N이라면

-> N은 이웃한 점이 있는 점에는 배정될 수 없다.

-> N이 독립적인 점에 배정된다면, 아무 위치에 배정되어도 전혀 상관이 없다.

-> N을 가능한 곳들 중 아무 곳에 배치한다.

-> 앞으로의 숫자들은 모두 N - 1 이하이므로, 앞으로의 숫자 배정은 (N - 1, k)와 동일하다.