AtCoder Beginner Contest 427 A ~ D問題

ABC427に参加しました。
A ~ Dの4完でperfは 1189　レートは 1133 → 1139 (+6) となりました。

A - ABC -> AC

$S$ の長さを $N$ とすると、$S$ の中央の文字は 0-indexedで $S[(N - 1) / 2]$ となるので、それを削除すればよいです。

A.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string S;
    cin >> S;
    S.erase(S.begin() + (S.size() - 1) / 2);
    cout << S << endl;
}

B - Sum of Digits Sequence

$f(x)$ は簡単に求めることができるので、問題文の通りにやればよいです。

B.cpp

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

int f(int x) {
    string s = to_string(x);
    int res = 0;
    for (char c : s) res += c - '0';
    return res;
}
 
int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);
    A[0] = 1;
    for (int i = 1; i <= N; i++) for (int j = 0; j < i; j++) A[i] += f(A[j]);
    cout << A[N] << endl;
}

C - Bipartize

各頂点における、黒、白の塗り分け方をbit全探索します。
二部グラフであるためには、辺が結んでいる頂点の色は異なる必要があるので、
同じときにその辺を削除しなければなりません。
各塗り分け方について、計算は $O(M)$ でできるので、全体の計算量は $O(2^NM)$ です。

C.cpp

#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}
 
int main() {
    int N, M;
    cin >> N >> M;    

    vector<int> u(M), v(M);
    for (int i = 0; i < M; i++) {
        cin >> u[i] >> v[i];
        u[i]--, v[i]--;
    }

    int ans = 1e9;
    for (int bit = 0; bit < (1 << N); bit++) {
        int cur = 0;
        for (int i = 0; i < M; i++) {
            if ((bit >> u[i] & 1) == (bit >> v[i] & 1)) cur++;
        }

        chmin(ans, cur);
    }

    cout << ans << endl;
}

D - The Simple Game

逆順で考えて動的計画法を用います。
$dp[v][i] = (頂点vにいて、操作があとi回できるとき、Aliceは必勝か)$ とします。
答えは $dp[0][2K]$ です。
$dp[v][0]$ は $S[v] = A$ のとき $true$ $S[v] = B$ のとき $false$　です。
遷移は以下の通りです。

• $i$ が偶数のとき
  $v$ と繋がっている頂点であって $dp[u][i - 1] = true$ となる $u$ が存在するとき、
  $dp[v][i]$ は $true$ そうでなければ $false$
• $i$ が奇数のとき
  $v$ と繋がっている頂点であって $dp[u][i - 1] = false$ となる $u$ が存在するとき、
  $dp[v][i]$ は $false$ そうでなければ $true$

各 $i$ について、計算は $O(N + M)$ でできるので、全体の計算量は $O(K(N + M))$ です。

D.cpp

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, M, K;
        string S;
        cin >> N >> M >> K >> S;
        vector<vector<int>> G(N);
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            G[u].push_back(v);
        }

        vector<vector<bool>> dp(N, vector<bool>(2 * K + 1));
        for (int i = 0; i < N; i++) {
            if (S[i] == 'A') dp[i][0] = true;
        }

        for (int i = 1; i <= 2 * K; i++) {
            for (int v = 0; v < N; v++) {
                if (i % 2 == 0) {
                    bool A_is_win = false;
                    for (int &next_v : G[v]) if (dp[next_v][i - 1]) A_is_win = true;
                    if (A_is_win) dp[v][i] = true;
                }

                else {
                    bool B_is_win = false;
                    for (int &next_v : G[v]) if (!dp[next_v][i - 1]) B_is_win = true;
                    if (!B_is_win) dp[v][i] = true;
                }
            }
        }

        cout << (dp[0][2 * K] ? "Alice" : "Bob") << endl;
    }
}