AtCoder Beginner Contest 286（ABC286）

atcoder.jp

A - Range Swap

$ Q - P = S - R $ が成り立つので $ 0 \leq i \leq Q-P $ を満たす $ i $ について $ (A_{i+P}, A_{i+R}) $ をスワップした $ A $ を出力すればいい

提出コード

void solve() {
    int N, P, Q, R, S;
    cin >> N >> P >> Q >> R >> S;
    --P, --Q, --R, --S;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    REP(i, Q - P + 1) swap(A[i + P], A[i + R]);
    REP(i, N) cout << A[i] << " ";
    cout << endl;
}

B - Cat

$ S_i = $ n、$ S_{i+1} = $ a を満たす場合、nyaを出力し、それ以外はそのまま出力する

提出コード

void solve() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    REP(i, N) {
        if (i + 1 < N and S[i] == 'n' and S[i + 1] == 'a') {
            cout << "nya";
            i++;
        }
        else cout << S[i];
    }
    cout << endl;
}

C - Rotate and Palindrome

$ A $ 円の操作を決め打ちしたときに $ B $ 円の操作で回文にするためのコストを全探索で求める

提出コード

void solve() {
    int N, A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;
    S += S;
    ll ans = LINF;
    REP(i, N) {
        ll tmp = i * A;
        REP(j, N / 2) {
            if (S[i + j] != S[i + N - j - 1]) tmp += B;
        }
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

D - Money in Hand

$ dp[i][j] := i $ 番目まで見たときに和が $ j $ となるような支払い方があるかどうかでDP をする
制約が優しいので愚直で求められる

提出コード

void solve() {
    int N, X;
    cin >> N >> X;
    vector<int> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];
    vector dp(X + 10, 0);
    dp[0] = 1;
    REP(i, N) {
        vector nxt(X + 1, 0);
        REP(j, X + 1) if (dp[j]) {
            nxt[j] |= dp[j];
            REP(k, B[i] + 1) {
                if (j + k * A[i] <= X) {
                    nxt[j + k * A[i]] |= dp[j];
                }
            }
        }
        swap(dp, nxt);
    }
    cout << (dp[X] ? "Yes" : "No") << endl;
}

E - Souvenir

ワーシャルフロイド法で最短経路を求める際に、価値の総和を同時に更新していく
距離が小さくなる場合は距離が小さくなる場合の価値に更新し、距離が同じ場合は、価値の大きなもので更新すればいい

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    vector<vector<ll>> dist(N, vector<ll>(N, LINF));
    vector<vector<ll>> value(N, vector<ll>(N, 0LL));
    REP(i, N) {
        string S;
        cin >> S;
        REP(j, N) if (S[j] == 'Y') {
            dist[i][j] = 1;
            value[i][j] = A[i];
        }
    }
    REP(k, N) REP(i, N) REP(j, N) {
        if (chmin(dist[i][j], dist[i][k] + dist[k][j])) {
            value[i][j] = value[i][k] + value[k][j];
        }
        else if (dist[i][j] == dist[i][k] + dist[k][j]) {
            chmax(value[i][j], value[i][k] + value[k][j]);
        }
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int U, V;
        cin >> U >> V;
        --U, --V;
        if (dist[U][V] == LINF) cout << "Impossible" << endl;
        else cout << dist[U][V] << " " << value[U][V] + A[V] << endl;
    }
}