Atcoder Beginner Contest 200 풀이

A, B, C는 정말 쉬운 편이고 D, E, F는 평균적인 라운드보다 좀 어렵게 뽑힌 거 같다.

A - Century

$x$가 주어지면 $ceil(x/100)$을 출력하면 된다.

#include<bits/stdc++.h>
using namespace std;
int main() {
  int x; cin >> x;
  cout << (x+99)/100 << '\n';
  return 0;
}

B - 200th ABC-200

$N, K$ 범위가 둘 다 작기 때문에 그대로 구현하면 된다. $N$이 200으로 나누어 떨어지지 않을 때는 $N \leftarrow 1000N + 200$을 해주면 되고 나누어 떨어지면 그냥 200으로 나누어 주도록 한다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
ll N, K;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    while(K--) {
        if(N%200 == 0) N /= 200;
        else N = N*1000 + 200;
    }
    cout << N << '\n';
    return 0;
}

C - Ringo's Favorite Numbers 2

$A_i$가 주어졌을 때 $A_i \equiv A_j \pmod{200}$인 $j < i$의 갯수를 세주면 된다. 이는 크기 200짜리의 $cnt$배열으 만들면 $O(1)$에 해결 가능하다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
int cnt[200];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    long long ans = 0;
    for(int i=0;i<N;++i) {
        int x; cin >> x;
        ans += cnt[x%200];
        cnt[x%200]++;
    }
    cout << ans << '\n';
    return 0;
}

D - Happy Birthday! 2

DP로 풀어보자. $dp(i, j)$를 $1...i$까지의 원소들로만 부분 수열을 구성했을 때 그 부분 수열의 합의 $\mod{200}$이 $j$인 수열이라고 하자.

그러면 $i$번째 원소를 추가할 때 $j < i$에 대해서 각 $k$에 대해서 $dp(j, k)$를 전부 살펴보면 $dp(i, k+A_i \mod{200})$을 구할 수 있다. 만약 어떤 $k$에 대해서 $dp(i, k)$와 $dp(j, k)$가 두 개 존재한다면 그게 답이 된다.

시간복잡도는 $O(N^3)$이 된다.

위 DP풀이보다 훨씬 좋은 풀이가 존재한다. 찾아야 되는 두 부분 수열은 수열의 합을 200으로 나눈 나머지가 같으면서 서로 다른 부분 수열 두개다.

길이가 $N$인 수열에서 나올 수 있는 비어 있지 않은 부분 수열은 $2^N-1$가지가 있으며 $N$이 8만 되어도 이 값을 200을 넘는다.

비둘기집의 원리에 의해서 수열의 길이가 8 이상이기만 하면 항상 답은 존재하기 때문에 수열의 길이가 8보다 크다면 그 중에서 8개만 골라서 전부 시도해보면 답을 찾을 수 있다. 그리고 8보다 작아도 전부 시도해보면 된다.

코드는 DP 풀이의 코드다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
bool avail[201][201];
vector<int> ans[201][201];
int N;
int a[201], orig[201];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=1;i<=N;++i) {
        cin >> orig[i];
        a[i] = orig[i] % 200;
    }
    ans[1][a[1]].push_back(1);
    avail[1][a[1]] = true;
    avail[0][0] = true;
    for(int i=2;i<=N;++i) {
        for(int j=0;j<i;++j) {
            for(int k=0;k<200;++k) {
                if(avail[j][k]) {
                    int l = (k + a[i]) % 200;
                    if(avail[i][l]) {
                        ll sum1 = 0, sum2 = 0;
                        cout << "Yes" << '\n';
                        cout << ans[i][l].size() << ' ';
                        for(int x : ans[i][l]) {
                            cout << x << ' ';
                            sum1 += a[x];
                        }
                        cout << '\n';
                        cout << ans[j][k].size() + 1 << ' ';
                        for(int x : ans[j][k]) {
                            cout << x << ' ';
                            sum2 += a[x];
                        }
                        sum2 += a[i];
                        cout << i << ' ';
                        cout << '\n';
                        assert(sum1 % 200 == sum2 % 200);
                        return 0;
                    }
                    avail[i][l] = true;
                    ans[i][l] = ans[j][k];
                    ans[i][l].push_back(i);
                }
            }
        }
    }
    for(int i=1;i<=N;++i) for(int j=i+1;j<=N;++j) {
        for(int k=0;k<200;++k) {
            if(avail[i][k] && avail[j][k]) {
                ll sum1 = 0, sum2 = 0;
                cout << "Yes" << '\n';
                cout << ans[i][k].size() << ' ';
                for(int x : ans[i][k]) {
                    cout << x << ' ';
                    sum1 += a[x];
                }
                cout << '\n';
                cout << ans[j][k].size() << ' ';
                for(int x : ans[j][k]) {
                    cout << x << ' ';
                    sum2 += a[x];
                }
                cout << '\n';
                assert(sum1 % 200 == sum2 % 200);
                return 0;
            }
        }
    }
    cout << "No" << '\n';
    return 0;
}

E - Patisserie ABC 2

$1 \le i,j,k \le N$,$(i,j,k)$를 $i,j,k$의 합 $i$,$j$,$k$로 정렬하기 때문에 이 순서대로 될 수 없는 순서쌍들을 지워나가면 된다.

어떤 말이냐면 $(i, j)$를 $i$, $j$ 순으로 정렬한다고 해보자. $i$가 1인 순서쌍이 $N$개, 2인 순서쌍도 $N$개 이런식으로 존재할 것이다. 이 때 $K$번째 순서쌍을 알고 싶다면 $K$에서 $N$씩 빼주면서 $K$가 $N$보다 같거나 작아지면 $i$가 어떤 수인지 알 수 있게 된다.

이 방법을 그대로 사용하자. 위 방법을 사용하기 위해서는 어떤 수를 1부터 $N$까지의 수 $k$개의 합으로 나타낼 수 있는 경우의 수이다. 이를 $dp(k, sum)$이라고 하자. 그러면 $i+j+k$, 즉 세 수의 합을 고정하기 위해서는 $K$에서 $dp(3, 3)$부터 시작해서 빼나가면 된다. $i$를 고정하는 데에는 $dp(2, 2)$부터 하고 $j$를 고정하는 데에는 $dp(1,1)$부터 하면 된다. 그렇게 $i,j,k$를 전부 고정할 수 있다.

이제 이 dp값들을 구해야 하는데 $dp(k, sum) = \sum_{i=1}^N dp(k-1, sum-i)$인데 이는 누적합으로 $O(N)$에 구할 수 있다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
vector<vector<ll>> dp(4);
ll N, K;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    vector<ll> v(N+1);
    for(int i=1;i<=N;++i) v[i] = 1;
    dp[1] = v;
    dp[2].resize(2*N+1);
    for(int i=2;i<=2*N;++i) {
        if(i <= N) dp[2][i] = i-1;
        else dp[2][i] = 2*N - i + 1;
    }
    dp[3].resize(3*N+1);
    ll psum = dp[2][2];
    for(int i=3;i<N+3;++i) {
        dp[3][i] = psum;
        psum += dp[2][i];
    }
    // psum dp(2, 2) ... dp(2, N+2) -> N+1 elements
    psum -= dp[2][2];
    for(int i=N+3;i<=2*N;++i) {
        dp[3][i] = psum;
        psum -= dp[2][i-N];
        psum += dp[2][i];
    }
    for(int i=2*N+1;i<=3*N;++i) {
        dp[3][i] = psum;
        psum -= dp[2][i-N];
    }
    ll X = 3*N;
    for(int sum=3;sum<=3*N;++sum) {
        if(K > dp[3][sum]) K -= dp[3][sum];
        else {
            X = sum;
            break;
        }
    }
    ll x;
    if(X > 2*N) x = X - 2*N;
    else x=1;
    for(;x<=N;++x) {
        if(K > dp[2][X-x]) K -= dp[2][X-x];
        else break;
    }
    ll y;
    if(X-x > N) y = X-x-N;
    else y=1;
    for(;y<=N;++y) {
        if(K > dp[1][X-x-y]) K -= dp[1][X-x-y];
        else break;
    }
    ll z = X - x - y;
    cout << x << ' ' << y << ' ' << z << '\n';
    return 0;
}

F - Minflip Summation

일단 $K=1$일 때의 문제부터 해결해보자. 구간 XOR 연산을 최소 횟수로 시행해서 모든 수를 같은 수로 만들어야 한다.

구간 $[l, r]$에 대해서 XOR을 한다고 했을 때 해당 구간의 수는 전부 같아야 할 것이다. 이를 토대로 생각해보자.

문자열 내에서 연속해서 1인 구간의 수를 $cnt_1$, 연속해서 0인 구간의 수를 $cnt_0$라고 하면 답은 $\min(cnt_0, cnt_1)$이 된다.

여기서 풀이를 뽑아내는 데에 도움되는 형태로 바꾸자. 인접한 두 원소의 수가 다른 쌍의 갯수를 $cnt$라고 하자. 그러면 최소 연산횟수는 $(cnt+1)/2$가 된다.

왜 그러냐면 어떤 구간에 대해서 XOR을 했다고 치자. 그러면 위와 같은 원소 쌍이 최대 2개 줄어들 것이다. 그리고 그 구간이 끝에 걸쳐있었다면 1개가 줄어들 것이다. 따라서 연산 한 번당 위와 같은 원소 쌍을 2개씩 줄여나간다고 생각하면 최소 연산횟수가 $(cnt+1)/2$가 된다.

이제 원래 문제로 돌아가자. 최소 연산횟수는 서로 다른 인접 원소 쌍의 수로 정해진다. 그러면 문자열 $S$를 $K$번 붙인 문자열의 인접 원소 쌍의 수를 계산해야 한다. 당연한 얘기지만 전부 해볼 순 없다. $2^{Kq}$만큼 있기 때문이다.

여기서 생각해볼 수 있는 것이 직접적인 수를 계산하는 것이 아니라 하나의 원소가 인접 원소 쌍의 수에 기여할 수 있는 게 어느정도인지에 대한 기댓값으로 바꿔서 생각하는 것이다.

어떤 인접 원소 쌍 $S_i, S_{i+1}$을 살펴봤을 때 $S_i$가 1이고 $S_{i+1}$도 1이라면 이 문자열을 아무리 이어붙인다 한들 서로 다른 인접 원소 쌍의 수에는 영향을 줄 수 없다. 서로 1과 0이라 하면 항상 1씩 늘리는 영향을 준다.

$?$가 섞여 있다면 줄 수도 있고 안 줄 수도 있는데 그 비율이 정확히 반반이다. 이를 통해서 $S$를 $K$번 이어붙였을 때 그 문자열 $S'$ $cnt$의 기댓값을 구할 수 있다. 식으로 써보자면 아래와 같을 것이다.
$$
cnt=K\sum_{i=1}^{\vert S \vert} f(S_i, S_{i+1}) + (K-1)f(S_{\vert S \vert}, S_1)
$$
$f(S_i, S_{i+1})$은 두 인접 원소 $S_i, S_{i+1}$이 $cnt$에 영향을 끼칠 기댓값이다. $K-1$인 이유는 첫 원소와 끝 원소는 $K-1$번 인접하기 때문이다.

위에서 말했듯이 최소 연산횟수는 $(cnt+1)/2$이다. 저 1이 문제다. $cnt/2$로 일괄적으로 구할 수가 없다는 것이다. $cnt/2$에다가 $cnt$가 홀수일 때 1을 더해준다.

그러면 홀수일 기댓값을 더해주면 되지 않을까? 언제 인접 원소 쌍의 수가 홀수가 될까? 첫 원소와 끝 원소가 다를 때 뿐이다. 따라서 $f(S_{\vert S \vert}, S_1)$을 한번 더 더해주면 맘놓고 $cnt/2$를 해도 된다. 따라서 답은 $2^{Kq} cnt / 2$가 된다.

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
using mint = atcoder::modint1000000007;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    string s; ll K;
    cin >> s >> K;
    if(s.size() == 1 && K == 1) {
        cout << 0 << '\n';
        return 0;
    }
    mint ans = 0;
    mint inv2 = mint(2).inv();
    int cnt = 0;
    for(char &c : s) cnt += c == '?';
    s.push_back(s[0]);
    for(int i=0;i<s.size()-1;++i) {
        if(s[i] == '?' || s[i+1] == '?') ans += K*inv2;
        else if(s[i] != s[i+1]) ans += K;
    }
    ans *= mint(2).pow(cnt*K);
    ans *= inv2;
    cout << ans.val() << '\n';
    return 0;
}