AtCoder Beginner Contest 187（ABC187）

atcoder.jp

しょっぱい
Bondo416さんのAtCoder Beginner Contest 187での成績：1031位
パフォーマンス：1451相当
レーティング：1481→1478 (-3) :(#AtCoder #ABC187 https://t.co/2FGkSRg73O

— ボンド@競プロ (@bond_cmprog) January 2, 2021

A - Large Digits

桁和を求めてそのmaxを出力する
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    int suma = 0, sumb = 0;
    while(A > 0){
        suma += A % 10;
        A /= 10;
    }
    while(B > 0){
        sumb += B % 10;
        B /= 10;
    }
    cout << max(suma, sumb) << endl;
}

B - Gentle Pairs

傾きは$ \frac{y_i - y_j}{x_j - x_i} $なので$ -1 \leq \frac{y_j - y_i}{x_j - x_i} \leq 1 $を満たすものを数えればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    int ans = 0;
    REP(i,N) for(int j=i+1;j<N;j++){
        int xx = x[j] - x[i];
        int yy = y[j] - y[i];
        if(abs(yy) <= abs(xx)) ans++;
    }
    cout << ans << endl;
}

C - 1-SAT

!がついているものとついていないものをそれぞれsetなどで管理する
!がついている文字列を見ていき、!を除いた文字列がもう片方のsetに入っていればそれを出力する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    set<string> st;
    set<string> ex;
    REP(i,N){
        if(S[i][0] == '!') ex.insert(S[i]);
        else st.insert(S[i]);
    }
    for(auto s : ex){
        if(st.find(s.substr(1,(int)s.size())) != st.end()){
            cout << s.substr(1, (int)s.size()) << endl;
            return;
        }
    }
    cout << "satisfiable" << endl;
}

D - Sum of difference

$ i $番目の町で演説すると高橋くんは$ A_i + B_i $票、青木くんは$ - A_i $票得られる
よって高橋くんが得する票数はその差分$ A_i + B_i - (- A_i) = 2A_i + B_i $になる
そのためこの降順にソートして貪欲に演説していけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    // vector<ll> A(N), B(N);
    vector<pair<ll, ll>> v(N);
    ll sumA = 0;
    REP(i,N){
        ll A, B;
        cin >> A >> B;
        sumA += A;
        v[i].first = 2 * A + B;
        v[i].second = A;
    }
    sort(v.rbegin(), v.rend());
    ll sum = 0;
    REP(i,N){
        sum += v[i].first - v[i].second;
        sumA -= v[i].second;
        // dumps(v[i].first, v[i].second);
        if(sum > sumA){
            cout << i + 1 << endl;
            return;
        }
    }
}

E - Through Path

適当な頂点を根とした根付き木として考える
そうすると各クエリはある頂点の部分木に$ x $加算するか部分木以外の全頂点に$ x $加算するクエリになる
どちらの点が部分木に含まれるかどうかは予めdfsなどで各頂点の深さを求めておき、深い方の頂点を部分木の頂点とすればいい
ここで部分木以外の全頂点に加算するクエリを全頂点に$ x $加算し、部分木に$ - x$加算するクエリとすれば全て部分木に加算するクエリにまとめられる
全体に加算する値と各頂点にその頂点の部分木にどれだけ加算するかの値を持っておけば最後に根から木上の累積和を取ればいい
オイラーツアー + imos法とかでも解ける
提出コード

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    vector<int> a(n), b(n);
    REP(i,n-1){
        cin >> a[i] >> b[i];
        g[--a[i]].emplace_back(--b[i]);
        g[b[i]].emplace_back(a[i]);
    }
    vector<ll> plus(n), minus(n);
    int q;
    cin >> q;
    ll sum = 0;
    vector<int> depth(n);
    auto rec = [&](auto && self, int v, int par, int dep = 0)->void{
        depth[v] = dep;
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, dep + 1);
        }
    };
    rec(rec, 0, -1);
    while(q--){
        int t, e, x;
        cin >> t >> e >> x;
        --e;
        dumps(depth[a[e]], depth[b[e]]);
        if(t == 1){
            if(depth[a[e]] < depth[b[e]]){
                sum += x;
                minus[b[e]] += x;
            }
            else{
                plus[a[e]] += x;
            }
        }
        else{
            if(depth[a[e]] < depth[b[e]]){
                plus[b[e]] += x;
            }
            else{
                sum += x;
                minus[a[e]] += x;
            }
        }
    }
    vector<ll> ans(n);
    auto dfs = [&](auto && self, int v, int par, ll num) -> void{
        ans[v] = sum + num + plus[v] - minus[v];
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, num + plus[v] - minus[v]);
        }
    };
    dfs(dfs, 0, -1, 0);
    REP(i,n) cout << ans[i] << endl;
}

提出コード（オイラーツアー + imos）

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    vector<pair<int, int>> edge(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        g[--a].emplace_back(--b);
        g[b].emplace_back(a);
        edge[i] = make_pair(a, b);
    }
    vector<int> ls(N), rs(N);
    int idx = 0;
    auto dfs = [&](auto && self, int v, int par) -> void{
        ls[v] = idx++;
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v);
        }
        rs[v] = idx;
    };
    dfs(dfs, 0, -1);
    vector<ll> imos(N+1);
    int q;
    cin >> q;
    while(q--){
        int t, e, x;
        cin >> t >> e >> x;
        auto [a, b] = edge[--e];
        if(t == 2) swap(a, b);
        if(ls[a] < ls[b]){
            imos[0] += x;
            imos[N] -= x;
            imos[ls[b]] -= x;
            imos[rs[b]] += x;
        }
        else{
            imos[ls[a]] += x;
            imos[rs[a]] -= x;
        }
    }
    REP(i,N) imos[i+1] += imos[i];
    REP(i,N) cout << imos[ls[i]] << "\n";
}

F - Close Group

まず、全ての集合についてその集合がクリークかどうかを前計算で求める
ある集合にその集合に含まれない頂点を1つ加えるとすると、その頂点から集合に含まれる全ての頂点にへの辺が存在すればその頂点を加えた集合もクリークになる
その次に、ある集合が最小何個のクリークで構成出来るかbitDPで求めればいい
これはある集合に対し、その部分集合を列挙すれば良く、$ \mathcal{O}(3^N) $で出来る
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> g(N);
    REP(i,M){
        int A, B;
        cin >> A >> B;
        --A, --B;
        g[A] |= (1 << B);
        g[B] |= (1 << A);
    }
    vector<int> dp(1<<N, INF);
    dp[0] = 1;
    REP(i,1<<N) REP(j,N) if(i >> j & 1){
        int tar = i - (1 << j);
        if(dp[tar] <= 1 and (g[j] & tar) == tar) dp[i] = 1;
    }
    for(int i=1;i<(1<<N);i++){
        for(int j=i;j>0;j=(j-1)&i){
            chmin(dp[i], dp[i^j] + dp[j]);
        }
    }
    cout << dp[(1<<N)-1] << endl;
}