接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 214（ABC214）

AtCoder Beginner Contest 214（ABC214）

AtCoderBeginnerContest AtCoderBeginnerContest214 ABC ABC214

atcoder.jp

A - New Generation ABC

問題文のとおりにif文
提出コード

void solve(){
    int N;
    cin >> N;
    if(N <= 125) cout << 4 << endl;
    else if(N <= 211) cout << 6 << endl;
    else cout << 8 << endl;
}

B - How many?

$ 0 \leq a, b, c \leq 100 $ の範囲で全探索
提出コード

void solve(){
    int S, T;
    cin >> S >> T;
    int ans = 0;
    REP(a,101) REP(b,101) REP(c,101){
        if((a + b + c <= S) and (a * b * c <= T)) ans++;
    }
    cout << ans << endl;
}

C - Distribution

$ i - 1 $ の宝石をもらう時刻が求まっているとすると $ i $ のもらう時刻は
$ ans_i = min(ans_{i-1} + S_{i-1}, T_i )$ となるので順々に決めていけばいい
ただし、円環上になっているので2周回す
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> S(N), T(N);
    REP(i,N) cin >> S[i];
    REP(i,N) cin >> T[i];
    vector<ll> ans(2 * N, LINF);
    ll sum = LINF;
    REP(i,2*N){
        chmin(sum, T[i%N]);
        ans[i] = sum;
        sum += S[i%N];
    }
    REP(i,N) cout << min(ans[i], ans[i+N]) << endl;
}

D - Sum of Maximum Weights

クラスカル法の要領で辺の重みの小さい順に見ていく
今見ている辺を追加するときに増える経路の個数は $ u_i $ の連結成分数と $ v_i $ の連結成分数の積になる
よって経路の増加分と辺の重みの積が辺を追加するときの答えへの寄与となる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<tuple<ll, int, int>> edge;
    REP(i,N-1){
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        edge.emplace_back(c, u, v);
    }
    ll ans = 0;
    sort(edge.begin(), edge.end());
    UnionFind uf(N);
    for(auto [c, u, v] : edge){
        if(uf.issame(u, v)) continue;
        ans += c * (ll)uf.size(u) * (ll)uf.size(v);
        uf.unite(u, v);
    }
    cout << ans << endl;
}

E - Packing Under Range Regulations

制約のキツイ方から処理したいので $ R $ の昇順に $ L, R $ をソートする
$ L_i \leq x \leq R_i $ の区間のどこかにボールを追加するとき、この区間のMEXを使用するのが最適となる
よって、setなどで区間を管理しながらMEXを求められればいい
このMEXが $ R_i $ よりも大きくなる場合、Noとなる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> L(N), R(N);
    REP(i,N) cin >> L[i] >> R[i];
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return R[a] < R[b];
    });
    RangeSet<ll> rs;
    for(auto i : idx){
        int mi = rs.mex(L[i]);
        if(mi > R[i]){
            cout << "No" << endl;
            return;
        }
        rs.insert(mi);
    }
    cout << "Yes" << endl;
}

F - Substrings

部分列DPでほぼ下記記事と同様
qiita.com ある1文字を選んだ際に、その次の文字は選べないので
$ dp[next[i][j] + 1] += dp[i] $ となっているところを $ dp[next[i][j] + 2] += dp[i] $ として遷移させればいい
提出コード

void solve(){
    string S;
    cin >> S;
    int n = S.size();
    auto next = calcNext(S);
    vector<mint> dp(n+1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 26; ++j) {
            if (next[i][j] >= n) continue;
            dp[min(n, next[i][j] + 2)] += dp[i];
        }
    }

    mint ans = 0;
    for (int i = 1; i <= n; ++i) ans += dp[i];
    cout << ans << endl;
}