接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 308（ABC308）

AtCoder Beginner Contest 308（ABC308）

AtCoderBeginnerContest AtCoderBeginnerContest308 ABC ABC308

atcoder.jp

A - New Scheme

問題文の条件を判定する

提出コード

void solve() {
    vector<int> S(8);
    REP(i, 8) cin >> S[i];
    bool ok = true;
    REP(i, 8) if (!(100 <= S[i] and S[i] <= 675)) ok = false;
    REP(i, 8) if (S[i] % 25 != 0) ok = false;
    REP(i, 7) if (S[i] > S[i + 1]) ok = false;
    cout << (ok ? "Yes" : "No") << endl;
}

B - Default Price

mapなどで色に対応する値段を管理する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> C(N), D(M);
    vector<int> P(M + 1);
    REP(i, N) cin >> C[i];
    REP(i, M) cin >> D[i];
    REP(i, M + 1) cin >> P[i];
    map<string, int> mp;
    REP(i, M) mp[D[i]] = P[i + 1];
    ll ans = 0;
    REP(i, N) {
        if (mp.count(C[i])) ans += mp[C[i]];
        else ans += P[0];
    }
    cout << ans << endl;
}

C - Standings

$ \frac{A_i}{A_i+B_i} \lt \frac{A_j} {A_j+B_j} $ の分母を払って $ A_i(A_j+B_j) \lt A_j(A_i+B_i) $ を比較関数にしてソートを行えば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int i, int j) {
        return A[i] * (A[j] + B[j]) == A[j] * (A[i] + B[i]) ? i < j : A[i] * (A[j] + B[j]) > A[j] * (A[i] + B[i]);
    });
    for (auto i : idx)
        cout << i + 1 << " ";
    cout << endl;
}

D - Snuke Maze

$ dist[i][h][w] := $ マス $ (h, w) $ にいて、その時の距離が $ i \pmod{5} $ であるときの最短距離としてBFSなどでこれを求める

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    string snuke = "snuke";
    REP(i, H) cin >> S[i];
    vector dist(5, vector(H, vector(W, INF)));
    if (S[0][0] != 's') {
        cout << "No" << endl;
        return;
    }
    dist[0][0][0] = 0;
    using T = tuple<int, int, int>;
    queue<T> q;
    q.emplace(0, 0, 0);
    while (!q.empty()) {
        auto [d, h, w] = q.front();
        q.pop();
        REP(dd, 4) {
            int nh = h + dy[dd];
            int nw = w + dx[dd];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            int nxt_d = (d + 1) % 5;
            if (S[nh][nw] == snuke[nxt_d]) {
                if (dist[nxt_d][nh][nw] != INF) continue;
                q.emplace(nxt_d, nh, nw);
                dist[nxt_d][nh][nw] = dist[d][h][w] + 1;
            }
        }
    }
    bool ok = false;
    REP(i, 5) if (dist[i][H - 1][W - 1] < INF) ok = true;
    cout << (ok ? "Yes" : "No") << endl;
}

E - MEX

$ dp[i][j][k] := i $ 番目まで見て、MEXの $ j $ 文字目まで決めたときに選んだ集合が $ k $ であるときの場合の数としてDPを行う
最後に $ dp[N][3][k] \times MEX(k) $ の総和を求めてそれを出力する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    string S;
    cin >> S;
    vector dp(N + 1, vector(4, vector(1 << 3, 0LL)));
    dp[0][0][0] = 1;
    string MEX = "MEX";
    REP(i, N) {
        REP(j, 4) {
            REP(k, 1 << 3) {
                dp[i + 1][j][k] += dp[i][j][k];
                if (j < 3 and S[i] == MEX[j]) {
                    dp[i + 1][j + 1][k | (1 << A[i])] += dp[i][j][k];
                }
            }
        }
    }
    ll ans = 0;
    REP(i, 1 << 3) {
        REP(j, 4) {
            if (!(i >> j & 1)) {
                {
                    ans += dp[N][3][i] * (ll)j;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

F - Vouchers

買う値段を最小化したいので、$ D_i $ の大きい順に使っていくことを考える
このとき、 $ L_i $ を満たすギリギリのものを選びたいのでmultisetなどで集合を管理し、lower_boundでその値を求める

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N), L(M), D(M);
    REP(i, N) cin >> P[i];
    REP(i, M) cin >> L[i];
    REP(i, M) cin >> D[i];
    sort(ALL(P));
    reverse(ALL(P));
    multiset<int> mst;
    priority_queue<pair<int, int>> pq;
    REP(i, N) mst.insert(P[i]);
    REP(i, M) pq.emplace(D[i], L[i]);
    ll ans = 0;
    while (!pq.empty()) {
        auto [d, l] = pq.top();
        pq.pop();
        auto it = mst.lower_bound(l);
        if (it == mst.end()) continue;
        ans += *it - d;
        mst.erase(it);
    }
    for (auto x : mst)
        ans += x;
    cout << ans << endl;
}