接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 348（ABC348）

AtCoder Beginner Contest 348（ABC348）

AtCoderBeginnerContest AtCoderBeginnerContest348 ABC ABC348

atcoder.jp

A - Penalty Kick

$ N $ 個の o 文字列を作り、3の倍数番目を x にする

提出コード

void solve() {
    int N;
    cin >> N;
    string ans = string(N, 'o');
    REP(i, N) if ((i + 1) % 3 == 0) ans[i] = 'x';
    cout << ans << endl;
}

B - Farthest Point

全探索で各頂点からの距離が最大の頂点を求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> X(N), Y(N);
    REP(i, N) cin >> X[i] >> Y[i];
    REP(i, N) {
        ll ma = 0;
        int idx = i;
        REP(j, N) {
            if (chmax(ma, (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]))) {
                idx = j;
            }
        }
        cout << idx + 1 << endl;
    }
}

C - Divide and Divide

mapなどで各 $ C_i $ の最小値を持っておき、その中の最大を出力する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), C(N);
    map<int, int> mp;
    REP(i, N) {
        cin >> A[i] >> C[i];
        if (mp.contains(C[i])) chmin(mp[C[i]], A[i]);
        else mp[C[i]] = A[i];
    }
    int ma = 0;
    for (auto [c, a] : mp) {
        chmax(ma, a);
    }
    cout << ma << endl;
}

D - String Bags

2回ワーシャルフロイドをする
薬のある$ N $ 間の最短距離を$ N $ 回BFSをした後にワーシャルフロイドで求める
その後、頂点 $ i $ から頂点 $ j $ まで薬 $ i $ のみを使って移動できる（$ dist[i][j] \leq E_i $） グラフを作り、そのグラフ上でワーシャルフロイドを行いゴールにたどり着けるかどうかを判定する
スタート/ゴールがない場合は予め $ E_k = 0 $ の頂点を追加しておく

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> A(H);
    REP(i, H) cin >> A[i];
    int sh = 0;
    int sw = 0;
    int th = 0;
    int tw = 0;
    REP(i, H) REP(j, W) {
        if (A[i][j] == 'S') {
            sh = i;
            sw = j;
        }
        else if (A[i][j] == 'T') {
            th = i;
            tw = j;
        }
    }
    int N;
    cin >> N;

    vector<int> R(N), C(N), E(N);
    int s = -1, t = -1;
    REP(i, N) {
        cin >> R[i] >> C[i] >> E[i];
        R[i]--, C[i]--;
        if (R[i] == sh && C[i] == sw) s = i;
        if (R[i] == th && C[i] == tw) t = i;
    }
    if (s == -1) {
        R.push_back(sh);
        C.push_back(sw);
        E.push_back(0);
        s = N;
        N++;
    }
    if (t == -1) {
        R.push_back(th);
        C.push_back(tw);
        E.push_back(0);
        t = N;
        N++;
    }
    vector<vector<int>> dist(N, vector<int>(N));
    REP(i, N) {
        vector<vector<int>> d(H, vector<int>(W, INF));
        d[R[i]][C[i]] = 0;
        queue<P> q;
        q.push(P(R[i], C[i]));
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            REP(j, 4) {
                int nr = r + dx[j], nc = c + dy[j];
                if (nr < 0 || nr >= H || nc < 0 || nc >= W || A[nr][nc] == '#') continue;
                if (d[nr][nc] > d[r][c] + 1) {
                    d[nr][nc] = d[r][c] + 1;
                    q.push(P(nr, nc));
                }
            }
        }
        REP(j, N) dist[i][j] = d[R[j]][C[j]];
    }
    REP(k, N) REP(i, N) REP(j, N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
    vector<vector<int>> hokyu(N, vector<int>(N, INF));
    REP(i, N) hokyu[i][i] = 0;
    REP(i, N) REP(j, N) {
        if (i == j) continue;
        if (dist[i][j] <= E[i]) chmin(hokyu[i][j], 1);
    }
    REP(k, N) REP(i, N) REP(j, N) chmin(hokyu[i][j], hokyu[i][k] + hokyu[k][j]);
    cout << (hokyu[s][t] == INF ? "No" : "Yes") << endl;
}

E - Minimize Sum of Distances

ABC220Fと同じ要領でやる
部分木のサイズの代わりに部分木の $ C_i $ の総和を$ sz $ としてdfsで求めておく
根を $ v $ から $ nv $ に移動させたときの変化量は $ sz_{nv} $ だけ減り、$ \sum _i C_i - sz_{nv} $ だけ増えるのでこれをdfsで求めれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    vector<int> u(N - 1), v(N - 1);
    REP(i, N - 1) {
        cin >> u[i] >> v[i];
        G[--u[i]].emplace_back(--v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    vector<ll> C(N);
    vector<ll> sz(N, 1);
    REP(i, N) {
        cin >> C[i];
        sz[i] = C[i];
    }
    ll sum = accumulate(C.begin(), C.end(), 0LL);
    vector<ll> ans(N);
    auto dfs1 = [&](auto &&self, int v, int par = -1) -> void {
        for (auto nv : G[v]) {
            if (nv == par) continue;
            self(self, nv, v);
            sz[v] += sz[nv];
            ans[v] += ans[nv] + sz[nv];
        }
    };

    auto dfs2 = [&](auto &&self, int v, int par = -1) -> void {
        for (auto nv : G[v]) {
            if (nv == par) continue;
            ans[nv] = ans[v] - sz[nv] + sum - sz[nv];
            self(self, nv, v);
        }
    };
    dfs1(dfs1, 0);
    dfs2(dfs2, 0);
    cout << *min_element(ans.begin(), ans.end()) << endl;
}