Codeforces Round #848 (Div. 2)

좋은 라운드는 아니었던 것 같습니다.

하지만 안 좋은 대회임에도 다행히 좋은 퍼포먼스를 내어서 Candidate Master로 올라갈 수 있었습니다 :)

 

타임 스탬프

00:04:34  A: Accepted

00:44:05  B: Accepted

01:19:37  C: Wrong answer on pretest 6

01:20:18  C: Accepted

01:49:20  D: Accepted

 

A. Flip Flop Sum

그냥 A번 문제입니다.

코드 보기

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int N = 1e5+3;
int n, a[N];

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        scanf("%d", &n);
        int s = 0;
        rep(i,1,n) {
            scanf("%d", &a[i]);
             s += a[i];
        }
        bool found = false;
        rep(i,1,n-1) {
            if (a[i] == -1 and a[i+1] == -1) {
                found = true;
            }
        }
        if (found) {
            printf("%d\n", s + 4);
            continue;
        }
        rep(i,1,n-1) {
            if (a[i] == -1 or a[i+1] == -1) {
                found = true;
            }
        }
        if (found) {
            printf("%d\n", s);
        } else {
            printf("%d\n", s - 4);
        }
    }
}

 

B. The Forbidden Permutation

문제를 조금 억지로 만들었다는 인상을 받았습니다.

모든 $1\le i < m$에 대해서 조건을 만족하는 것이 not good일 조건...

 

그래서 하나의 $i$에 대해서만 조건을 만족하지 않도록 만들면 됩니다.

$\operatorname {swap}(p_i,p_{i+1})$이라는 조건이 꽤 헷갈리니 직접 적어보세요.

 

여기서 하나 더 확인할 점은, $a_i$는 $\operatorname {pos}(a_i)=1$일 때까지만 움직일 수 있고, $a_{i+1}$은 $\operatorname {pos}(a_{i+1})=n$일 때까지만 움직일 수 있다는 것입니다.

코드 보기

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int N = 1e5+3, M = N;
int n, m, d;
int p[N], a[M], r[N];

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        scanf("%d %d %d", &n, &m, &d);
        rep(i,1,n) scanf("%d", &p[i]), r[p[i]] = i;
        rep(i,1,m) scanf("%d", &a[i]);
        bool for_all = true;
        rep(i,1,m-1) {
            if (not (r[a[i]] < r[a[i+1]] and r[a[i+1]] <= r[a[i]]+d)) {
                for_all = false;
            }
        }
        if (not for_all) puts("0");
        else {
            int ans = 1e9;
            rep(i,1,m-1) {
                mup(ans, r[a[i+1]]-r[a[i]]);
                if (r[a[i+1]] + r[a[i]]-1+n-r[a[i+1]] > r[a[i]]+d)
                    mup(ans, r[a[i]]+d+1-r[a[i+1]]);
            }
            printf("%d\n", ans);
        }
    }
}

 

C. Flexible String

그냥 $a$에서의 서로 다른 문자의 개수를 $c$라고 합시다. $Q$에 $\max\{c,k\}$개 이하의 문자를 관리하는 건 어차피 $\max\{c,k\}$개의 문자를 관리하면서 일부를 무시하는 경우이기 때문에 그냥 $\max\{c,k\}$개를 전부 다 쓰면 된다는 것은 자명합니다.

 

$\displaystyle \binom {c} { \max\{c,k\} }$가지 조합으로 문자들을 사용해서 해당 문자들이 존재하는 위치에서 $a_i\leftarrow b_i$로 고쳐주면 됩니다.

코드 보기

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int N = 1e5+3;
int n, k;
char a[N], b[N], c[N];
bool use[13];

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        scanf("%d %d %s %s", &n, &k, a+1, b+1);
        fill(use,use+13,0);
        copy(a+1,a+n+1,c+1);
        sort(c+1,c+n+1);
        int x = unique(c+1,c+n+1)-c-1;
        set<char> s;
        per(i,max(0,x-k)+1,x) {
            use[i] = true;
        }
        ll ans = 0;
        do {
            set<char> q;
            rep(i,1,x) if (use[i]) q.insert(c[i]);
            int p = 0;
            ll s = 0;
            rep(i,1,n) {
                if (a[i] != b[i]) {
                    if (q.count(a[i])) continue;
                    else {
                        s += ll(i-p)*(i-p-1)/2;
                        p = i;
                    }
                }
            }
            s += ll(n-p+1)*(n-p)/2;
            Mup(ans,s);
        } while (next_permutation(use+1,use+x+1));
        printf("%lld\n", ans);
    }
}

 

D. Flexible String Revisit

그냥 두 문자열의 구체적인 정보는 무시하고, 두 문자열의 편집 거리(edit distance)만 고려하면 됩니다.

'$\mathrm{dp}(k):=$ 편집 거리가 $k$일 때, 전부 $0$으로 만들기 위한 시행 횟수의 기댓값'이라고 정의합시다.

 

다음의 관찰들을 합시다:

1. $\mathrm{dp}(0)=0$입니다. 당연하죠?
2. $\mathrm{dp}(n)=\mathrm{dp}(n-1)+1$입니다. 왜냐하면 편집 거리가 더 커지거나 그대로일 수 없기 때문입니다.
3. $\displaystyle \mathrm{dp}(k)=\frac {k\cdot \mathrm{dp}(k-1) + (n-k) \cdot \mathrm{dp}(k+1)} n + 1$입니다. 잘 생각해보세요.

그러면 이제 $\mathrm{dp}(1),\mathrm{dp}(2),\ldots,\mathrm{dp}(n-1)$의 점화식만 계산할 수 있는 형태로 바꿔주면 좋겠습니다.

$\mathrm{dp}(k)=a_k\cdot \mathrm{dp}(k-1)+b_k$라고 합시다.

그러면 [관찰 2]에 따라 $(a_n,b_n)=(1,1)$임을 알 수 있습니다.

이를 바탕으로 $(a_k,b_k)=f(a_{k+1},b_{k+1})$ 형태로 역으로 채워갈 수 있겠네요.

 

열심히 계산해보면, $\displaystyle (a_k,b_k)=\left(\frac {k} {n-(n-k)\cdot a_{k+1}}, \frac {(n-k)\cdot b_{k+1}+n} {n-(n-k)\cdot a_{k+1}} \right)$라는 관계식이 나옵니다.

코드 보기

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
...
#pragma endregion modnum template
using mint = modnum<998244353>;

const int N = 1e6+3;
int n;
char a[N], b[N];
mint dp[N], A[N], B[N];

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        scanf("%d %s %s ", &n, a+1, b+1);
        int ed = 0;
        rep(i,1,n) if (a[i] != b[i]) ed++;
        dp[0] = 0;
        A[n] = 1, B[n] = 1;
        per(k,1,n-1) {
            mint c = n-(n-k)*A[k+1];
            A[k] = k/c;
            B[k] = ((n-k)*B[k+1]+n)/c;
        }
        rep(k,1,n) {
            dp[k] = A[k]*dp[k-1]+B[k];
        }
        printf("%d\n", int(dp[ed]));
    }
}