Codeforces Round 848

결과

링크 2023.02.01 DIV2
3솔, 1684/15247 (11.0%) 1324 (+122) (퍼포1585)
 
확실히 velog를 통해 dp를 정리해준게 도움이 되었던 것 같다. dp를 이용했더니 A가 빠르게 풀렸고, 나머지는 테스트 케이스가 친절해서 3솔.

---

A Flip Flop Sum

개요

00:05:43
-1과 1로 이루어진 배열에서 인접한 두 원소를 바꾼 누적합의 최댓값

접근

1. dp문제를 최근에 많이 풀어서 보자마자 dp인 것 확인. 안바꾸면서 / 바꾸면서 n까지 온 경우의 최댓값을 저장한 dp[n][2]
2. 3번 테케같이 바꾸지 않는 것이 최적임에도 무조건 바꿔야 하는 경우 보고 출력은 dp[n][1]을 해야 함을 알게됨
3. 최댓값을 저장할거라서 초기화는 -2e9, 업데이트는 안바꾸는 경우는 단순 누적합, 바꾸는 경우 아래 두개의 최댓값
   1. n-1에서 바꾼경우+누적합
   2. n-2에서 안바꾼 경우+2개 바꿔서 누적합
      즉, dp[i][1] = max(dp[i-1][1]+a[i], dp[i-2][0]-a[i-1]-a[i])

Source code

#include <bits/stdc++.h>
using namespace std;

void get() {
    int n, i;
    cin >> n;
    int a[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];
    int dp[n+1][2];
    for (int i=0; i<=n; i++) {
        dp[i][0] = -2e9;
        dp[i][1] = -2e9;
    }
    dp[0][0] = 0;
    dp[1][0] = a[1];
    for (int i=2; i<=n; i++) {
        dp[i][0] = max(dp[i][0], dp[i-1][0]+a[i]);
        dp[i][1] = max(dp[i][1], dp[i-1][1]+a[i]);
        dp[i][1] = max(dp[i][1], dp[i-2][0]-a[i]-a[i-1]);
    }
    cout << dp[n][1] << "\n";
}

int main() {
    int T;
    cin >> T;
    while(T--) get();
    return 0;
}

---

B The Forbidden Permutation

개요

00:33:19
어떤 a[i+1]이 {a[i], a[i]+d} 사이에 있지 않도록 만드는 최소 swap수 구하기

접근

1. 일단 pos() 함수보고 뇌정지, N,M,D 모두 10만이라 무조건 O(n)에 해야겠구나.

2. 모든이 아닌 어떤임을 생각하기까지 시간이 꽤 걸림. 그럼 m번 순회하면서 최소 swap을 찾으면 정답이 되겠구나. 즉, 가장 최소한으로 swap해서 조건을 만족할 수 있는 swap만 찾아주면 끝남.

3. 그럼 최소 swap을 어떻게 구해주냐?
   아래와 같이 대소관계가 있으면

   |  <-      -> |
   a[i]  a[i+1]  a[i]+d

   화살표 방향대로 a[i+1]이 왼쪽 또는 오른쪽으로 가주면 됨
   그러면 min(왼쪽, 오른쪽) 해주면 되겠구나.

   a[i+1] <= a[i] || a[i]+d < a[i+1] 이면 만족하니까

   left = a[i+1]-a[i]
   right = (a[i]+d)-a[i+1]+1

4. 테케가 친절했던게 도움이 많이 됐음. 만약 오른쪽으로 가려는데 a[i]와의 차이가 n이상으로 벌어지면 a[i+1]이 배열 밖으로 뛰쳐나간거니까 무조건 왼쪽으로 가줘야함.

Pseudo code

for (i = 이동 가능한 범위 = a[1] ~ a[m-1])
    left = a[i+1]-a[i]
    right = (a[i]+d)-a[i+1]+1

    업데이트할 값 = min(left, right)
    if (뛰쳐나가면)
        업데이트할 값 = left
    answer = min(업데이트할 값)

Source code

#include <bits/stdc++.h>
using namespace std;

void get() {
    int n, m, d;
    cin >> n >> m >> d;
    int t;
    int p[n+1];
    for (int i=1; i<=n; i++) {
        cin >> t;
        p[t] = i;
    }
    int a[m+1];
    for (int i=1; i<=m; i++)
        cin >> a[i];
    int ans = 2e9, v;
    int left, right;

    for (int i=1; i<m; i++) {
        left = p[a[i+1]]-p[a[i]];
        right = p[a[i]]+d-p[a[i+1]]+1;

        left = left>0?left:0;
        right = right>0?right:0;

        v = min(left, right);
        if ((p[a[i+1]]+right)-p[a[i]] >= n)
            v = left;
        ans = min(ans, v);
    }
    cout << ans << "\n";
}

int main() {
    int T;
    cin >> T;
    while(T--) get();
    return 0;
}

---

C Flexible String

개요

01:18:20
최대 10가지 원소로 이루어진 문자열 a의 일부를 바꾼 뒤 b와 동일한 연속부분문자열의 최대개수 구하기

접근

1. 일단 10가지 중에서 k개를 뽑는 것인데 문제를 쭉 읽고 10C5부터 검색해봄, 252라서 아하 O(N*252) 안에는 해결이 되겠구나.

2. 구현은 문자열에 익숙하지 않아서 매우 더럽게 함.

   1. 우선 a의 서로 다른 원소를 저장한 배열을 구하고
   2. 거기서 k개 combination을 뽑고
   3. combination마다 값을 구해서 최댓값 업데이트 해주면 됨

3. 값을 구한다? 하는 것을 어떻게 하느냐가 문제의 핵심이라 생각하는데, 테케가 친절해서 도움이 됐음.

   lkwhbahuqa
   qoiujoncjb

   이게 왜 10이 아니고 11인가? 하고 생각해보니 아래처럼 됐음.

   // select = {h, b, a}
   lkwhbahuqa
   lkw0000uq0
   qoi0000cj0
   // 아래처럼 변환 가능
   0001111001
   // 길이4 => 4+3+2+1
   // 마지막길이1 => 1

   어차피 바꾸고 난 뒤에는 다 같으니까 그냥 0으로 두고, 연속 부분문자열이므로 연속된 1의 개수가 최대가 되어야 함. 그래서 최대4니까 4+3+2+1 = 10아닌가? 했는데 뒤의 1이 하나 있는 것까지 세주면 11이었음

4. 그래서 sum을 구할 때는 연속된 1의 개수 L마다 (L+1)×L/2를 더해주면 됨. 아쉬운 점은 integer overflow로 두 번을 WA받은 것.
   주의할 점은 k번을 다 못 쓸 수도 있으니까 k = min(k, 다른 원소의 종류의 개수)로 업데이트 해야 한다는 것.

Pseudo code

dist = set of a
for (comb = get_combination(dist))
    answer = max(answer, find_sum(comb))
find_sum(comb) {
    for (a를 돌면서)
        converted[comb에 포함된 원소] = 1
    for (i = converted)
        L = get_longest_one(i)
        ans += (L+1)*L/2
}

Source code

#include <bits/stdc++.h>
using namespace std;

typedef long long ld;
typedef vector <int> que;
int n, k;
ld ans;
string a, b;
que q;

que dist(string a) {
    que q, p;
    for (char i='a'; i<='z'; i++)
        q.push_back(0);
    for (int i=0; i<a.size(); i++)
        q[a[i]-'a'] = 1;
    for (int i='a'; i<='z'; i++)
        if (q[i-'a'])
            p.push_back(i-'a');
    return p;
}

ld sum(que q, int cnt) {
    int p[26];
    for (int i=0; i<26; i++)
        p[i] = 0;
    for (int i=0; i<cnt; i++)
        p[q[i]] = 1;

    int c[n];
    for (int i=0; i<n; i++)
        c[i] = 0;
    for (int i=0; i<n; i++)
        if (p[a[i]-'a'])
            c[i] = 1;
        else if (a[i]==b[i])
            c[i] = 1;

    ld ans = 0;
    for (ld i=0; i<n; i++) {
        if (c[i]) {
            ld j = i;
            while(c[j] && j < n) j++;
            ans += (j-i+1)*(j-i)/2;
            i = j;
        }
    }
    return ans;
}

void find(que p, int cnt, int e, int k) {
    if (cnt == k)
        ans = max(ans, sum(p, cnt));
    else {
        for (int i=e; i<q.size(); i++) {
            p[cnt] = q[i];
            find(p, cnt+1, i+1, k);
        }
    }
}

void get() {
    cin >> n >> k;
    cin >> a >> b;
    q = dist(a);

    int d[26];
    int diff = 0;
    for (int i=0; i<26; i++)
        d[i] = 0;
    for (int i=0; i<n; i++)
        if (a[i] != b[i])
            d[a[i]-'a'] = 1;
    for (int i=0; i<26; i++)
        if (d[i])
            diff++;

    que p;
    p.resize(11);
    ans = 0;
    find(p, 0, 0, min(diff, k));
    cout << ans << "\n";
}

int main() {
    int T;
    cin >> T;
    while(T--) get();
    return 0;
}