接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 322（ABC322）

AtCoder Beginner Contest 322（ABC322）

AtCoderBeginnerContest AtCoderBeginnerContest322 ABC ABC322

atcoder.jp

A - First ABC 2

全探索をして一番初めに見つかったindexを答える

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    REP(i, N - 2) {
        if (S.substr(i, 3) == "ABC") {
            cout << i + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

B - Prefix and Suffix

c++20から starts_with と ends_with が使えるのでそれを使うと楽

提出コード

void solve() {
    int N, M;
    string S, T;
    cin >> N >> M >> S >> T;
    int ans = 3;
    if (T.starts_with(S) and T.ends_with(S)) ans = 0;
    else if (T.starts_with(S)) ans = 1;
    else if (T.ends_with(S)) ans = 2;
    cout << ans << endl;
}

C - Festival

$ i $ 以上となる最小の $ A_j $ を二分探索で求めその差分が答え

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    REP(i, M) cin >> A[i];
    REP(i, 1, N + 1) {
        int start = *lower_bound(ALL(A), i);
        cout << start - i << endl;
    }
}

D - Polyomino

各ポリオミノの回転、置く場所を全通り試し、条件を満たすかどうかをチェックする

提出コード

void solve() {
    vector<string> P1(4), P2(4), P3(4);
    REP(i, 4) cin >> P1[i];
    REP(i, 4) cin >> P2[i];
    REP(i, 4) cin >> P3[i];
    const int sz = 10;
    auto rot = [](vector<string> &s) -> vector<string> {
        vector<string> res(s[0].size());
        REP(i, s.size()) {
            REP(j, s[0].size()) { res[j].push_back(s[i][j]); }
        }
        REP(i, res.size()) { reverse(res[i].begin(), res[i].end()); }
        return res;
    };
    REP(d1, 4) {
        REP(d2, 4) {
            REP(d3, 4) {
                REP(h1, 7) REP(w1, 7) REP(h2, 7) REP(w2, 7) REP(h3, 7) REP(w3, 7) {
                    vector<vector<char>> fi(10, vector<char>(10, '.'));
                    bool ok = true;
                    REP(i, 4) REP(j, 4) {
                        if (P1[i][j] == '#') {
                            if (3 <= h1 + i and h1 + i <= 6 and 3 <= w1 + j and w1 + j <= 6) fi[h1 + i][w1 + j] = '#';
                            else {
                                ok = false;
                                break;
                            }
                        }
                    }
                    if (!ok) break;
                    REP(i, 4) REP(j, 4) {
                        if (P2[i][j] == '#') {
                            if (3 <= h2 + i and h2 + i <= 6 and 3 <= w2 + j and w2 + j <= 6) {
                                if (fi[h2 + i][w2 + j] == '.') fi[h2 + i][w2 + j] = '#';
                                else {
                                    ok = false;
                                    break;
                                }
                            }
                            else {
                                ok = false;
                                break;
                            }
                        }
                    }
                    if (!ok) break;
                    REP(i, 4) REP(j, 4) {
                        if (P3[i][j] == '#') {
                            if (3 <= h3 + i and h3 + i <= 6 and 3 <= w3 + j and w3 + j <= 6) {
                                if (fi[h3 + i][w3 + j] == '.') fi[h3 + i][w3 + j] = '#';
                                else {
                                    ok = false;
                                    break;
                                }
                            }
                            else {
                                ok = false;
                                break;
                            }
                        }
                    }
                    REP(i, 3, 7) REP(j, 3, 7) if (fi[i][j] != '#') ok = false;
                    if (ok) {
                        cout << "Yes" << endl;
                        dumps(d1, h1, w1, d2, h2, w2, d3, h3, w3);
                        return;
                    }
                }
                P3 = rot(P3);
            }
            P2 = rot(P2);
        }
        P1 = rot(P1);
    }
    cout << "No" << endl;
}

E - Product Development

$ dp[i][k_1][k_2][k_3][k_4][k_5] := i $ 番目まで見てパラメータ $ j $ が $ k_j $ であるときの最小値としてDPを行う

提出コード

ll dp[111][6][6][6][6][6];

void solve() {
    ll N, K, P;
    cin >> N >> K >> P;
    vector<ll> C(N);
    vector<vector<ll>> A(N, vector<ll>(6));
    REP(i, N) {
        cin >> C[i];
        REP(j, K) cin >> A[i][j];
    }
    REP(num, 111) REP(i, 6) REP(j, 6) REP(k, 6) REP(l, 6) REP(m, 6) dp[num][i][j][k][l][m] = LINF;
    dp[0][0][0][0][0][0] = 0;
    REP(num, N) {
        REP(i, 6) REP(j, 6) REP(k, 6) REP(l, 6) REP(m, 6) {
            chmin(dp[num + 1][i][j][k][l][m], dp[num][i][j][k][l][m]);
            chmin(dp[num + 1][min(P, i + A[num][0])][min(P, j + A[num][1])][min(P, k + A[num][2])]
                    [min(P, l + A[num][3])][min(P, m + A[num][4])],
                  dp[num][i][j][k][l][m] + C[num]);
        }
    }
    ll ans = LINF;
    if (K == 1) ans = dp[N][P][0][0][0][0];
    else if (K == 2) ans = dp[N][P][P][0][0][0];
    else if (K == 3) ans = dp[N][P][P][P][0][0];
    else if (K == 4) ans = dp[N][P][P][P][P][0];
    else if (K == 5) ans = dp[N][P][P][P][P][P];
    cout << (ans == LINF ? -1 : ans) << endl;
}