接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 274（ABC274）

AtCoder Beginner Contest 274（ABC274）

AtCoderBeginnerContest AtCoderBeginnerContest274 ABC ABC274

atcoder.jp

A - Batting Average

%.3lf で出力する

提出コード

void solve() {
    int A, B;
    cin >> A >> B;
    printf("%.3lf\n", (double)B / A);
}

B - Line Sensor

各列ごとに#の数を数える

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector C(H, vector<char>(W));
    REP(i, H) REP(j, W) cin >> C[i][j];
    vector<int> ans(W);
    REP(i, W) REP(j, H) ans[i] += (C[j][i] == '#');
    REP(i, W) cout << ans[i] << " ";
    cout << endl;
}

C - Ameba

$ dp[i] := i $ 番のアメーバが何代目かどうか、でDPをする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) { cin >> A[i]; }
    vector<int> ans(2 * N + 10);
    ans[1] = 0;
    REP(i, N) {
        ans[(i + 1) * 2] = ans[A[i]] + 1;
        ans[(i + 1) * 2 + 1] = ans[A[i]] + 1;
    }
    REP(i, 1, 2 * N + 2) cout << ans[i] << endl;
}

D - Robot Arms 2

奇数回目の操作では、y方向には影響せず、偶数回目の操作の場合にもx方向には影響しないのでx,y方向それぞれについて独立にDPを行うことができる
それぞれについて $ dp[i][j] := i $ 回操作したときに $ j $ に存在するか、としてDPを行う

提出コード

void solve() {
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    int base = 10101;
    vector<int> dp_x(base * 2, 0), dp_y(base * 2, 0);
    dp_x[base] = 1;
    dp_y[base] = 1;
    {
        for (int i = 0; i < N; i += 2) {
            vector<int> nxt(base * 2, 0);
            REP(j, 2 * base) if (dp_x[j]) {
                if (j + A[i] < 2 * base) nxt[j + A[i]] = 1;
                if (i > 0 and j - A[i] > 0) nxt[j - A[i]] = 1;
            }
            swap(dp_x, nxt);
        }
    }
    {
        for (int i = 1; i < N; i += 2) {
            vector<int> nxt(base * 2, 0);
            REP(j, 2 * base) if (dp_y[j]) {
                if (j + A[i] < 2 * base) nxt[j + A[i]] = 1;
                if (j - A[i] > 0) nxt[j - A[i]] = 1;
            }
            swap(dp_y, nxt);
        }
    }

    if (dp_x[base + X] and dp_y[base + Y]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

E - Booster

$ N + M $ 頂点の巡回セールス問題をbitDPで解く
$ M $ 頂点はすべて通る必要がないので $ N $ 頂点のbitがすべて立っているものの中で距離が最小となるものを出力すればいい

提出コード

void solve() {
    int N, M;
    cin >> N >> M;

    vector<ll> X(N + 1), Y(N + 1), P(M), Q(M);
    X[0] = Y[0] = 0;
    REP(i, N) cin >> X[i + 1] >> Y[i + 1];
    REP(i, M) cin >> P[i] >> Q[i];

    vector<int> two(M + 1);
    two[0] = 1;
    REP(i, M) two[i + 1] = two[i] * 2;

    vector<ll> x = X;
    vector<ll> y = Y;
    REP(j, M) {
        x.emplace_back(P[j]);
        y.emplace_back(Q[j]);
    }
    int sz = x.size();
    vector dp(1 << sz, vector<double>(sz, LINF));
    dp[0][0] = 0;
    REP(bit, 1, 1 << sz) {
        REP(j, sz) if (bit >> j & 1) {
            REP(k, sz) {
                double booster = two[__builtin_popcount(bit >> (N + 1))];
                pair<int, int> prev = {x[j], y[j]};
                pair<int, int> nxt = {x[k], y[k]};
                double dist = hypot(prev.first - nxt.first, prev.second - nxt.second) / booster;
                chmin(dp[bit][k], dp[bit - (1 << j)][j] + dist);
            }
        }
    }
    double ans = LINF;
    int base = (1 << (N + 1)) - 1;
    REP(i, 1 << M) { chmin(ans, dp[(i << (N + 1)) ^ base][0]); }
    printf("%.12lf\n", ans);
}