接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 267（ABC267）

AtCoder Beginner Contest 267（ABC267）

AtCoderBeginnerContest AtCoderBeginnerContest267 ABC ABC267

atcoder.jp

A - Saturday

if文で場合分け

提出コード

void solve() {
    string S;
    cin >> S;
    int ans = 0;
    if (S == "Monday") ans = 5;
    else if (S == "Tuesday") ans = 4;
    else if (S == "Wednesday") ans = 3;
    else if (S == "Thursday") ans = 2;
    else ans = 1;
    cout << ans << endl;
}

B - Split?

2つの列の選び方を全通り試し、条件を満たすものがあるかどうかを判定

提出コード

void solve() {
    string S;
    cin >> S;
    string ans = "No";
    vector<vector<int>> row(7);
    row[0] = vector({7});
    row[1] = vector({4});
    row[2] = vector({2, 8});
    row[3] = vector({1, 5});
    row[4] = vector({3, 9});
    row[5] = vector({6});
    row[6] = vector({10});
    if (S[0] == '0') {
        REP(i, 7) REP(j, i + 2, 7) {
            bool ok1 = false;
            bool ok2 = false;
            for (auto x : row[i])
                if (S[x - 1] == '1') ok1 = true;
            for (auto x : row[j])
                if (S[x - 1] == '1') ok2 = true;

            if (!(ok1 and ok2)) continue;
            bool ok = true;
            for (int k = i + 1; k < j; k++) {
                for (auto x : row[k])
                    if (S[x - 1] == '1') ok = false;
            }
            if (ok) {
                cout << "Yes" << endl;
                return;
            }
        }
    }
    cout << "No" << endl;
}

C - Index × A(Continuous ver.)

$ A_0 + 2A_1 + \dots + MA_M $ を一つ右にずらすと
$ A_1 + 2A_2 + \dots + (M - 1)A_M + MA_{M+1}$ となり、$ A_0 + A_1 + \dots + A_M $ を引いたあとに $ MA_{M+1} $ を加算することになる
そのため、もとの配列 $ A $ の累積和などを持ちながら値を更新していけばいい

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    ll sum = 0;
    ll sum_M = 0;
    REP(i, M) {
        sum += (i + 1) * A[i];
        sum_M += A[i];
    }
    ll ans = sum;
    REP(i, M, N) {
        sum -= sum_M;
        sum_M -= A[i - M];
        sum_M += A[i];
        sum += M * A[i];
        chmax(ans, sum);
    }
    cout << ans << endl;
}

D - Index × A(Not Continuous ver.)

$ dp[i][j] : = i $ 番目まで見ていて、$ j $ 個選んだときの最大値、としてDPを行う

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    vector dp(M + 1, -LINF);
    dp[0] = 0;
    REP(i, N) {
        vector nxt(M + 1, -LINF);
        REP(j, M + 1) if (dp[j] > -LINF) {
            chmax(nxt[j], dp[j]);
            if (j + 1 <= M) chmax(nxt[j + 1], dp[j] + (j + 1) * A[i]);
        }
        swap(dp, nxt);
    }
    cout << dp[M] << endl;
}

E - Erasing Vertices 2

操作のコストが$ X $ 以下の操作のみを行ってすべての頂点を消すことができるか、という判定問題を二分探索で求める
$ X $ 以下の操作が可能な頂点をstackなどで管理をし、操作が行える頂点から操作を行っていく
操作を行った際に、$ X $ 以下の操作が可能になった頂点を追加し、操作可能な頂点が空になるまで操作を行う
操作が終わった際に、すべての頂点を消すことができたかを判定する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    vector<vector<pair<int, int>>> g(N);
    vector<int> u(M), v(M);
    REP(i, M) {
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        g[u[i]].emplace_back(v[i], i);
        g[v[i]].emplace_back(u[i], i);
    }
    auto check = [&](ll m) -> bool {
        vector<ll> sum(N);
        REP(i, M) {
            sum[u[i]] += A[v[i]];
            sum[v[i]] += A[u[i]];
        }
        vector<int> vertices;
        REP(i, N)
        if (sum[i] <= m) vertices.emplace_back(i);
        vector<int> used(N);
        while (!vertices.empty()) {
            int cur = vertices.back();
            vertices.pop_back();
            for (auto [x, i] : g[cur]) {
                if (used[x]) continue;
                sum[x] -= A[cur];
                sum[cur] -= A[x];
                if (sum[x] + A[cur] > m and sum[x] <= m) vertices.emplace_back(x);
            }
            used[cur] = 1;
        }

        if (accumulate(ALL(used), 0) == N) return true;
        else return false;
    };

    ll l = -1, r = LINF;
    while (r - l > 1) {
        ll m = (r + l) >> 1;
        if (check(m)) r = m;
        else l = m;
    }
    cout << r << endl;
}

F - Exactly K Steps

木の直径を求め、その頂点を $ (l, r) $ とする
$ (l, r ) $ を根としたときのパスをそれぞれdfsで求め、クエリの頂点 $ u_i $ に到達したときに距離が $ k_i $ 離れている頂点が求めたいものであるので、$ k_i $ 個前に訪れた頂点を求めればいい

提出コード

void solve() {
    int N;
    cin >> N;
    treeDiameter tree(N);
    REP(i, N - 1) {
        int u, v;
        cin >> u >> v;
        tree.add_edge(--u, --v);
    }
    tree.build(0);
    int l = tree.v;
    int r = tree.w;
    auto &g = tree.G;
    int Q;
    cin >> Q;
    vector<vector<pair<int, int>>> q(N);
    REP(i, Q) {
        int u, k;
        cin >> u >> k;
        --u;
        q[u].emplace_back(i, k);
    }
    vector<int> ans(Q, -1);
    for (auto root : {l, r}) {
        vector<int> vertices;
        auto dfs = [&](auto &&self, int v, int par) -> void {
            for (auto [i, k] : q[v]) {
                if (k <= (int)vertices.size()) {
                    ans[i] = vertices[(int)vertices.size() - k] + 1;
                }
            }
            vertices.emplace_back(v);
            for (auto nv : g[v]) {
                if (par == nv) continue;
                self(self, nv, v);
            }
            vertices.pop_back();
        };
        dfs(dfs, root, -1);
    }
    REP(i, Q) cout << ans[i] << endl;
}