接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 301（ABC301）

AtCoder Beginner Contest 301（ABC301）

AtCoderBeginnerContest AtCoderBeginnerContest301 ABC ABC301

atcoder.jp

A - Overall Winner

T と A の個数を数える
個数が同じ場合、最後に数えたものが負け

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    bool f = false;
    int a = 0, t = 0;
    REP(i, N) {
        if (S[i] == 'T') {
            t++;
            f = true;
        }
        else {
            a++;
            f = false;
        }
    }
    if (a > t) cout << "A" << endl;
    else if (a < t) cout << "T" << endl;
    else {
        if (f) cout << "A" << endl;
        else cout << "T" << endl;
    }
}

B - Fill the Gaps

問題文の条件のとおりに出力をする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    cout << A[0] << " ";
    REP(i, 1, N) {
        if (abs(A[i] - A[i - 1]) == 1) cout << A[i] << " ";
        else if (A[i] > A[i - 1]) {
            REP(j, A[i - 1] + 1, A[i] + 1) cout << j << " ";
        }
        else if (A[i] < A[i - 1]) {
            for (int j = A[i - 1] - 1; j >= A[i]; j--)
                cout << j << " ";
        }
    }
    cout << endl;
}

C - AtCoder Cards

各文字ごとに文字数を数え、SとTで文字数が同じかどうかを比較していく
このとき @はa, t, c, o, d, e, rに置き換えられるので足りない分は置き換えてしまっていい
SとTで文字数を同じにできない文字がある場合はNo、それ以外はYesとなる

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    vector<int> s(27), t(27);
    for (char c : S) {
        if (c == '@') s[26]++;
        else s[c - 'a']++;
    }
    for (char c : T) {
        if (c == '@') t[26]++;
        else t[c - 'a']++;
    }
    set<char> st = {'a', 't', 'c', 'o', 'd', 'e', 'r'};
    REP(i, 26) {
        if (s[i] == t[i]) continue;
        else if (!st.count(char(i + 'a'))) {
            cout << "No" << endl;
            return;
        }
        else if (s[i] > t[i]) {
            if (s[i] - t[i] > t[26]) {
                cout << "No" << endl;
                return;
            }
            else {
                t[26] -= s[i] - t[i];
            }
        }
        else if (s[i] < t[i]) {
            if (t[i] - s[i] > s[26]) {
                cout << "No" << endl;
                return;
            }
            else {
                s[26] -= t[i] - s[i];
            }
        }
    }
    cout << "Yes" << endl;
}

D - Bitmask

? を 0とした場合の2進数整数を予め求めておく
その後、上位bitから順に見ていき?を1としたときの2進数整数が $ N $ 以下の場合、そのbitは1としてしまって良い

提出コード

void solve() {
    string S;
    ll N;
    cin >> S >> N;
    ll cur = 0;
    reverse(ALL(S));
    REP(i, S.size()) if (S[i] == '1') cur += 1LL << i;
    if (cur > N) {
        cout << -1 << endl;
        return;
    }
    for (int i = (int)S.size() - 1; i >= 0; i--)
        if (S[i] == '?' and cur + (1LL << i) <= N) cur += 1LL << i;
    cout << cur << endl;
}

E - Pac-Takahashi

S, G, o のみに注目すると頂点数は高々20となり巡回セールスマン問題のようにbit DPで求めることができる
そのため、各頂点間の距離を予めBFSなどで求めておくことで以下のDPで答えを求めることができる
$ dp[i][j] := $ 最後に訪れた頂点が $ i $ で、訪れた頂点集合が $ j $ としたときの移動回数の最小
求めたい答えは、最後にGを訪れたときに移動回数が $ T $ 以下であるときの頂点集合に含まれる oの数の最大であるので条件を満たすもののうち、頂点集合に含まれる oの数の最大を求めればいい

提出コード

void solve() {
    int H, W, T;
    cin >> H >> W >> T;
    vector<string> s(H);
    REP(i, H) cin >> s[i];
    vector<pair<int, int>> snack;
    int sh, sw, gh, gw;
    REP(i, H) REP(j, W) {
        if (s[i][j] == 'S') sh = i, sw = j;
        else if (s[i][j] == 'G') gh = i, gw = j;
    }
    snack.emplace_back(sh, sw);
    snack.emplace_back(gh, gw);
    REP(i, H) REP(j, W) {
        if (s[i][j] == 'o') snack.emplace_back(i, j);
    }
    int n = snack.size();
    vector<vector<int>> dist(n, vector<int>(n, INF));
    REP(i, n) {
        auto [h, w] = snack[i];
        vector<vector<int>> d(H, vector<int>(W, INF));
        d[h][w] = 0;
        queue<pair<int, int>> q;
        q.emplace(h, w);
        while (!q.empty()) {
            auto [cur_h, cur_w] = q.front();
            q.pop();
            REP(dir, 4) {
                int nh = cur_h + dx[dir];
                int nw = cur_w + dy[dir];
                if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
                if (s[nh][nw] == '#') continue;
                if (d[nh][nw] < INF) continue;
                d[nh][nw] = d[cur_h][cur_w] + 1;
                q.emplace(nh, nw);
            }
        }
        REP(j, n) dist[i][j] = d[snack[j].first][snack[j].second];
    }
    vector dp(n, vector<int>(1 << n, INF));
    dp[0][0] = 0;
    dp[0][1] = 0;  // s = 0, g=1
    REP(i, 1, (1 << n) + 1) {
        REP(j, n) if (i >> j & 1) {
            REP(k, n) {
                int cost = dp[j][i ^ (1 << j)] + dist[j][k];
                chmin(dp[k][i], cost);
            }
        }
    }
    int ma = -1;
    REP(i, 1 << n) if ((i & 1) and (i >> 1 & 1) and dp[1][i] <= T) { chmax(ma, __builtin_popcount(i ^ 1 ^ 2)); }
    cout << ma << endl;
}