ALOHA 여름방학 고급반 3주차

2주차는 귀찮아서 안 썼읍니다

아직 문제 안 읽은 걸 보니 4주차도 안 쓸 것 같음 ㅎㅎ..

 

A. https://www.acmicpc.net/problem/14229

 

이 문제에서 포함되어 있는 문자열은 부분 문자열을 의미한다. $4^5 > 2000$이니 정답의 길이는 5 이하이다. 따라서 그냥 완탐 돌리면 된다. 

 

처음에는 부분 수열로 생각하고 풀이 냈는데 틀리더라..

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    
    string s, t = "ATCG";
    cin >> s;
    vector<string> v{""}, tmp;
    while (1){
        tmp.clear();
        for (string x : v){
            for (char c : t){
                string y = x + c;
                int chk = 0;
                for (int i = 0; i+y.size() <= s.size(); i++){
                    int now = 1;
                    for (int j = 0; j < y.size(); j++)
                        now &= y[j] == s[i+j];
                    chk |= now;
                }
                if (!chk) {
                    cout << y;
                    return 0;
                }
                tmp.push_back(y);
            }
        }
        v = tmp;
    }
}

 

B. https://www.acmicpc.net/problem/32189

 

LCS를 직접 구하는 방향으로만 생각하다 도저히 모르겠어서 풀이 깠다. 

 

$\min(|A|, |B|) - LCS(A, B)$의 최댓값을 구해야 하는데, 문자열을 나누는 기준선을 길이가 짧은 쪽으로 한 칸 옮기면 $\min(|A|, |B|)$는 1 감소하고 $LCS(A, B)$는 최대 1 증가한다. 따라서 $\min(|A|, |B|)$가 최대이도록 분할하는 것이 최적이므로 가능한 한두가지 분할에 대해 LCS를 직접 구해주면 된다. 

 

C. https://www.acmicpc.net/problem/27548

 

수열이 두 개 있고 각각 길이가 5000 이하이니 먼가 수열 각각에서 $a$개, $b$개 쓴 상황으로 2차원 DP를 돌리고 싶게 생겼다.

 

각 숫자를 한 번씩만 쓸 수 있으며, 두 수열은 각각 순증가하는 수열이니 병합 정렬 하듯 합치면 순증가하는 수열이 될 것이다. 따라서 문제의 목표는 합쳐진 수열의 최댓값을 최소화하는 것이다. 병합 정렬 과정에서 수열의 원소를 뽑은 뒤 이전에 뽑힌 수와 홀짝을 비교해 어떤 수를 넣을지 확정지을 수 있다. 이런 마인드로 위에서 설명한 dp에 이전 수의 홀짝성까지 상태로 넣으면 dp로 문제를 풀 수 있다. 갑자기자세히쓰기귀찮다

 

먼가 dp를 하고 싶긴 한데 어떻게 돌릴지 몰라서 그리디니 이분탐색이니 안 되는 풀이 한참 고민하느라 시간 날렸다. 무슨 작전 하느라 초소에서 30분쯤 서 있을 시간이 있었는데, 그때 풀이 가닥이 떠올라서 개인정비때 급하게 짰다. 

 

#include <bits/stdc++.h>
using namespace std;
 
int n, m, A[5050], B[5050], dp[5050][5050][2];
 
int f(int ai, int bi, int c){
    if (ai > n and bi > m) return 0;
    int& ret = dp[ai][bi][c];
    if (ret != -1) return ret;
    ret = 1e9;
    if (ai <= n) ret = f(ai+1, bi, A[ai]) + (A[ai] == c ? 2 : 1);
    if (bi <= m) ret = min(ret, f(ai, bi+1, B[bi]) + (B[bi] == c ? 2 : 1));
    return ret;
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> B[i];
    cout << f(1, 1, 0);
}

 

D. https://www.acmicpc.net/problem/32658

 

일단 바로 떠오르는 풀이는 DP이다. $d(K, X)$를 보급을 $X$만큼 보내야 하고 $K$번 차단될 수 있을 때 비용의 최솟값으로 정의하자. 보급은 $1$ 이상 $X$ 이하로 보낼 수 있다. 보급을 $t$만큼 시도했을 때 $d(K-1, X) > d(K, X-t)$라면 보급이 차단될 것이고, 아니라면 보급이 성공할 것이다. 따라서 보급을 $t$만큼 시도했을 때 비용은 $\max(d(K-1, X), d(K, X-t)) + t + C$이며, $d(K, X) = \min_{1 \le t \le X}(\max(d(K-1, X), d(K, X-t)) + t) + C$이다. 

 

모든 $t$를 일일이 다 검사하는 시간복잡도는 $O(KX^2)$이니 최적화가 필요하다. 점화식에서 $t$가 바뀌어도 보급이 차단되었을 때의 비용은 동일하다는 점을 생각하자. $X$는 보내야 하는 비용이므로 $X$가 줄어들면 $d(K, X)$ 또한 줄어든다. 즉, $d(K, 0), d(K, 1), \cdots, d(K, X)$는 오름차순 수열이다. 

 

$d(K, 0), d(K, 1), \cdots, d(K, X-1)$에서 max의 고정된 인자인 $d(K-1, X)$ 이상인 수가 처음 등장하는 위치를 찾아보자. 해당 위치 이전에서 max의 결과는 모두 $d(K-1, X)$이며, 이후에서는 모두 $d(K, X-t)$이다. $d(K, X-t)$는 $t$가 클수록 값이 작으니 찾은 위치를 $i$라고 하면 $dp(K, X) = min(d(K-1, X) + i-1, d(K, X-i) + i) + C$이다. $K$가 작은 순서대로 dp 테이블을 채워 가며 위치를 이분탐색으로 찾으면 $O(KX\log X)$ 시간복잡도에 문제를 풀 수 있다. 아마 투포인터로 구하면 로그 뗄 수 있는 듯 한데 귀찮다

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll X, K, C, dp[303][10101];
 
int main() {
    cin >> X >> K >> C;
    
    for (int i = 1; i <= X; i++) dp[0][i] = i+C;
    for (int k = 1; k <= K; k++){
        vector<ll> v{0};
        for (int x = 1; x <= X; x++){
            int i = lower_bound(v.begin(), v.end(), dp[k-1][x]) - v.begin();
            dp[k][x] = dp[k-1][x] + x-i+1;
            if (i != v.size()) dp[k][x] = min(dp[k][x], v[i] + x-i);
            dp[k][x] += C;
            v.push_back(dp[k][x]);
        }
    }
    cout << dp[K][X];
}

 

E. https://www.acmicpc.net/problem/33138

 

문제를 해석하면 클리크로만 이루어져 있으며 각 정점이 정확히 2개의 클리크에 속하는 그래프에서 최소 버텍스 커버를 구해야 하는데.. 모르겟당