2020 UCPC 예선 대비 개인 연습 (2)

AtCoder Beginner Contest 171

문제 풀이

문제 링크

D. Replacing

$A$의 원소들의 합을 관리하는 배열과 $X[x]$ := ($A$에 $x$가 등장하는 횟수) 로 정의된 배열 $X$를 잘 관리해주면 된다.

 

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

typedef long long ll;

int N, Q;
ll X[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    ll sum = 0;
    for (int i=0; i<N; i++){
        int x; cin >> x;
        X[x]++;
        sum += x;
    }
    cin >> Q;
    while (Q--){
        int b, c;
        cin >> b >> c;
        sum -= b * X[b];
        sum += X[b] * c;
        X[c] += X[b];
        X[b] = 0;
        cout << sum << '\n';
    }
}

E. Red Scarf

어떤 수를 홀수번 XOR 하면 원래의 수와 같고, XOR 연산들은 순서에 상관없음을 이용하면 된다. 문제에서 주어진 값들을 모두 XOR 한 값을 $X$, $i$ 번째로 주어진 값을 $X_i$라 하면, $A_i = X \oplus X_i$ 가 됨을 확인할 수 있다.

 

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

typedef long long ll;

int N;
int A[200005];
int X;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> A[i];
        X ^= A[i];
    }
    for (int i=0; i<N; i++) cout << (X ^ A[i]) << ' ';
    cout << endl;
}

F. Strivore

문제를 요약하자면, 어떤 문자열 $S$가 주어지면, $S$를 부분문자열로 하는 길이 $N(=|S|+K)$의 문자열의 개수를 구하는 문제이다. 단, 사용할 수 있는 문자들의 집합 $\Sigma = { a, b, \dots, z}$ 이다.

 

문제를 바꾸어서 길이 $N$인 문자열 중 $S$를 부분문자열로 포함하지 않는 문자열의 수를 구해보자. 한 가지 좋은 점근은 $A_i$ := (부분문자열인 $S$의 접두사 중 가장 긴 것의 길이가 $i$인 길이 $N$의 문자열의 집합) 로 정의할 때, 이 $|A_i|$ 들에 대한 명확한 식을 찾아내는 것이다.

 

그런데, $A_i$에 속하는 문자열들을 다음의 규칙을 통해 만들어낼 수 있음을 확인할 수 있다.

• $1, 2, \dots, N$ 가운데 $S_1$과 같은 문자를 가지는 가장 빠른 인덱스 $k_1$, $k_1$ 이후 인덱스 가운데 $S_2$와 같은 문자를 가지는 인덱스 $k_2$, ... 와 같은 식으로 $i$개의 인덱스 $k_1 < k_2 < \dots < k_i$를 잘 골라준다.
• $k_j$ 에는 문자 $S_j$를 배정한다.
• 이후 나머지 인덱스에 문자를 배정하는데, 인덱스 $k'$이 $k_j < k' < k_{j+1}$일 때 (단, $k_{i+1} = \infty$) $k'$ 번째 위치에는 $S_{j+1}$이 아닌 문자 아무거나 배정한다.

결국 $|A_i|$ = (${ k_j }$들에 문자를 배정하는 경우의 수 ) × (나머지 문자 배정하는 경우의 수) 가 되므로,
$$
|A_i| = {N \choose i} (|\Sigma | - 1) ^ {N - i}
$$
이 된다. 문제의 답은 $|\Sigma|^N - \sum_{i=0}^{|S|-1} |A_i|$ 가 된다.

 

사족. 개인적으로는 생각보다 어려운 문제였다. 푸는데 꽤나 오래 걸렸던 것 같다.

 

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

typedef long long ll;

const ll mod = 1'000'000'007;

ll powmod(ll x, ll n){
    x %= mod;
    ll res = 1;
    while (n){
        if (n & 1) res = (res * x) % mod;
        n >>= 1;
        x = (x * x) % mod;
    }
    return res;
}

inline ll submod(ll x, ll y){
    x %= mod; y %= mod;
    return (x + mod - y) % mod;
}

inline ll addmod(ll x, ll y){
    x %= mod; y %= mod;
    return (x + y) % mod;
}

inline ll mulmod(ll x, ll y){
    x %= mod; y %= mod;
    return (x * y) % mod;
}

ll K, N;
string S;
ll fac[2000006], ifac[2000006];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> K;
    cin >> S; N = S.length() + K;
    ll ans = powmod(26, N);
    fac[0] = 1;
    for (ll i=1; i<=2000000; i++) fac[i] = mulmod(fac[i-1], i);
    ifac[2000000] = powmod(fac[2000000], mod-2);
    for (ll i=2000000; i; i--) ifac[i-1] = mulmod(ifac[i], i);
    for (ll i=0; i<S.length(); i++){
        ll cur = powmod(25, N-i);
        ll binom = mulmod(mulmod(fac[N], ifac[i]), ifac[N-i]);
        cur = mulmod(binom, cur);
        ans = submod(ans, cur);
    }
    cout << ans << endl;
}

Codeforces Round #651

문제 풀이

문제 링크

C. Number Game

경우를 다음과 같이 나누어 생각해볼 수 있다.

• $N$이 홀수일 때:
  • $N = 1$인 경우: 선수가 진다.
  • $N$이 $1$보다 큰 홀수인 경우: 선수가 $N /= N$을 할 수 있으므로, 선수가 이긴다.
• $N$이 짝수일 때:
  • $N = 2$인 경우: 선수가 $N -= 1$을 할 수 있으므로, 선수가 이긴다.
  • $N = 2p$ ($p$는 홀수소수)인 경우: 선수가 $N /= p$와 $N -= 1$ 중 어느 것을 택해도 진다.
  • $N = 2^k$ ($k > 1$)인 경우: 선수는 $N -= 1$을 강제로 선택하게 되고, 진다.
  • 이 외의 경우, 선수가 $N$을 ($N$의 모든 odd prime power의 곱) 으로 나누면 이긴다.

개인적으로, 대회 중에 케이스 분류하는게 약간은 까다로웠다.

D. Odd-Even Subsequence

답에 대한 이분탐색을 통해 문제를 해결할 수 있다. $a_1$을 포함하는 subsequence만 고려해도 문제의 답이 바뀌지 않음을 알 수 있다. 자세한 것은 코드를 참고하자.

 

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

typedef long long ll;

int N, K;
int A[200005];

vector<int> I;

bool able(int X){
    I.clear();
    I.push_back(A[1]);
    if (I[0] <= X){
        int j = 1;
        for (int i=2; i<=N; i++){
            if (j % 2 == 0){
                if (A[i] <= X){
                    I.push_back(A[i]);
                    j++;
                }
                continue;
            }
            I.push_back(A[i]);
            j++;
            continue;
        }
        if ((int) I.size() >= K) return true;
    }
    I.clear(); I.push_back(A[1]);
    int j = 1;
    for (int i=2; i<=N; i++){
        if (j % 2 == 1){
            if (A[i] <= X){
                I.push_back(A[i]);
                j++;
            }
            continue;
        }
        I.push_back(A[i]);
        j++;
        continue;
    }

    return ((int) I.size()) >= K;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i=1; i<=N; i++){
        cin >> A[i];
    }
    int lo = 0, hi = 1E9;
    while (lo + 1 < hi){
        int mid = (lo + hi) / 2;
        if (able(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << endl;
}

E. Binary Sequence Rotation

먼저, $s$와 $t$의 $0$, $1$의 개수가 같은 경우만 고려해도 충분함을 확인할 수 있다. 또한, $s_i = t_i$인 인덱스들을 전부 제거하고 고려해도 무방하다.

 

최적 횟수의 연산으로 두 문자열을 같게 만드는 방법 중 각 연산에서 택한 $s$의 인덱스들에 있는 문자가 $1010\dots$ 내지는 $0101 \dots$와 같이 alternating 하게 하는 방법이 있음을 확인할 수 있다.

 

결국 이 문제는 어떤 binary 문자열을 최소 개수의 alternating subsequence로 cover하는 문제가 되고, 이는 $1$이 있는 인덱스에는 $+1$, $0$이 있는 인덱스에는 $-1$로 이루어진 배열의 최대/최소 부분합을 구해서 해결할 수 있다.

 

대회 끝나고 업솔빙을 통해 해결한 문제이다.

Codeforces Round #649

문제 풀이

문제 링크

C. Ehab and Prefix MEX's

핵심이 되는 관찰은 $a_i \neq a_{i-1}$이면, $b_i = a_{i-1}$라는 것이다. 이를 이용해서 잘 구현해주면 되는데, 나는 잘 구현하는게 생각보다 어려웠다. 구현은 생각보다 짧다.

 

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

typedef long long ll;

int N;
int A[100005];
int B[100005];
bool used[100005];
int mx;
stack<int> idx;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=1; i<=N; i++) cin >> A[i];
    bool flag = true;
    memset(B, -1, sizeof(B));
    for (int i=1; i<=N; i++){
        idx.push(i);
        if (A[i] == A[i-1]) continue;
        for (int j=A[i-1]; j<=A[i]-1; j++){
            int k = idx.top();
            idx.pop();
            B[k] = j;
        }
    }
    for (int i=1; i<=N; i++){
        if (B[i] != -1) break;
        B[i] = N+5;
    }
    for (int i=1; i<=N; i++){
        if (B[i] == -1) B[i] = B[i-1];
    }
    for (int i=1; i<=N; i++) cout << B[i] << ' ';
    cout << endl;
}

D. Ehab's Last Corollary

둘 중 하나를 찾을 수 있음이 주어졌으므로, 어느 하나를 찾으려고 시도해보고, 실패할 경우 그 과정에서 얻은 정보로 다른 하나를 효율적으로 찾는 접근을 해볼 수 있다.

어떤 정점 $s$를 시작으로 해서 BFS를 해보자. BFS에서 $1, 2, \dots, k$ 번째로 방문한 정점을 고르자. 고른 정점 가운데 짝수인 정점들의 집합을 $X$, 홀수인 정점들의 집합을 $Y$라 할 때, 비둘기 집의 원리에 의해 둘 중 어느 하나는 $\displaystyle \lceil { k \over 2} \rceil$ 이상이다.

만약, 그래프의 간선 가운데 $X$에 속하는 두 정점을 잇는 간선이 없다면, 우리는 task 1을 해결한 것이다.

아니라고 가정하자. 그러한 간선 $u \to v$가 있다고 하자. 그러면, $u \to v$ 간선을 제외한 나머지 간선만 활용하며 $u$로부터 BFS를 수행하여 $v$로 가는 경로 $P_{uv}$를 찾자. 앞서 밑줄 친 내용에 의해 $u$와 $v$ 사이의 거리는 $k$ 미만임이 보장된다. 따라서, $P_{uv}$에 간선 $u \to v$를 더해주면 크기 $k$ 이하의 사이클이 되므로 task 2에 대한 답이 된다.