接着剤の精進日記

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

トップ > AtCoderBeginnerContest173 > AtCoder Beginner Contest 173（ABC173）

AtCoder Beginner Contest 173（ABC173）

AtCoderBeginnerContest173 AtCoderBeginnerContest ABC173 ABC

atcoder.jp

A - Payment

Nを超える最小の1000の倍数からNを引く
Nが小さいからループでもいい
提出コード

void solve(){
    int N;
    cin >> N;
    int cnt = (N + 999) / 1000;
    cout << cnt * 1000 - N << endl;
}

B - Judge Status Summary

注意力？
それぞれでカウントして出力形式に気をつける
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> cnt(5);
    REP(i,N){
        string s;
        cin >> s;
        if(s == "AC") cnt[0]++;
        if(s == "WA") cnt[1]++;
        if(s == "TLE") cnt[2]++;
        if(s == "RE") cnt[3]++;
    }
    cout << "AC x " << cnt[0] << endl;
    cout << "WA x " << cnt[1] << endl;
    cout << "TLE x " << cnt[2] << endl;
    cout << "RE x " << cnt[3] << endl;
}

C - H and V

制約が小さいのでどこを選ぶかをbit全探索する
bit全探索出来るならこっちのほうが簡潔な気がするけど再帰で書いた人もいるっぽい
提出コード（bit全探索）

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    REP(h, 1<<H) REP(w,1<<W){
        vector<string> tmp = fi;
        REP(i,H) if(h >> i & 1){
            REP(k,W) tmp[i][k] = '?';
        }
        REP(i,W) if(w >> i & 1){
            REP(k,H) tmp[k][i] = '?';
        }
        int cnt = 0;
        REP(i,H) REP(j,W){
            if(tmp[i][j] == '#') cnt++;
        }
        if(cnt == K) ans++;
    }
    cout << ans << endl;
}

提出コード（再帰）

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    auto dfs = [&](auto && self, vector<int> &v) ->void{
        if(size(v) == H + W){
            auto tmp = fi;
            REP(i,H) if(v[i] == 1){
                REP(j,W) tmp[i][j] = '?';
            }
            REP(j,W) if(v[H+j] == 1){
                REP(i,H) tmp[i][j] = '?';
            }
            int cnt = 0;
            REP(i,H) REP(j,W){
                if(tmp[i][j] == '#') cnt++;
            }
            if(cnt == K) ans++;
        }
        else{
            REP(i,2){
                v.push_back(i);
                self(self, v);
                v.pop_back();
            }
        }
    };
    vector<int> v;
    dfs(dfs, v);
    cout << ans << endl;
}

D - Chat in a Circle

これ難しくない？
最初に到達人以外を考える
2人目は最初に来た人の値になるので最初の人は高いほうが良い
2人目以降は自分が割り込んだ位置の時計回りと反時計回り方向に自分の値の区間が出来る
そのため、降順ソートをし、区間の大きい値を貪欲にとっていく
そうすると降順ソートした後、数列の先頭から 1, 2, 2, 2, ..., の回数だけ値を加算できる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    priority_queue<int> pq;
    ll ans = 0;
    REP(i,N){
        if(i == 0){
            pq.push(A[i]);
            continue;
        }
        ans += pq.top(); pq.pop();
        pq.push(A[i]);
        pq.push(A[i]);
    }
    cout << ans << endl;
}

E - Multiplication 4

頭壊れる
N = Kときは自明
すべての値が負なら、絶対値の小さい順に掛けていく
それ以外の場合は必ず非負に出来る
絶対値の降順にソートをし、大きい順にK個取る
その時点で値が非負ならそれが答え
負になった時、選んだものの中から負のものを1個取って、選んでないものの中から1個非負を選ぶ
もしくは、正のものを1個取って、負を1個取る
選んだものの中からは出来るだけ小さいものを取りたい、また、選んでないものの中からは出来るだけ大きいものを取りたいのでこれは一意に定まる
この2つのうち、積が大きくなる方を選べばいいが、片方しか選べないときがあるので注意する
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    int plus = 0, minus = 0;

    REP(i,N){
        cin >> A[i];
        if(A[i] >= 0) plus++;
        else  minus++;
    }
    mint ans = 1;
    if(N == K){
        REP(i,N) ans *= A[i];
        cout << ans << endl;
        return;
    }
    if((K & 1) && plus == 0){
        REP(i,N) if(A[i] < 0) A[i] *= -1;
        sort(A.begin(), A.end());
        REP(i,K) ans *= A[i];
        ans = -ans;
        cout << ans << endl;
        return;
    }
    bool flg = false;
    sort(A.begin(), A.end(), [&](int x, int y){return abs(x) > abs(y);});
    ll m = -LINF, p = LINF;

    REP(i,K){
        ans *= A[i];
        if(A[i] < 0){
            flg = 1 - flg;
            chmax(m, A[i]);
        }
        else chmin(p, A[i]);
    }

    if(!flg){
        cout << ans << endl;
        return;
    }

    ll c1 = LINF, c2 = LINF;
    for(int i=K;i<N;i++){
        if(A[i] >= 0 && c1 == LINF){
            c1 = A[i];
        }
        if(A[i] < 0 && c2 == LINF){
            c2 = A[i];
        }
    }

    if((p != LINF && c2 != LINF) && (m == -LINF || c1 == LINF)) cout << ans / p * c2 << endl;
    else if((p == LINF || c2 == LINF) && (m != -LINF && c1 != LINF)) cout << ans / m * c1 << endl;
    else if(abs(c1 * p) <= abs(c2 * m)) cout << ans / p * c2 << endl;
    else cout << ans / m * c1 << endl;
}

F - Intervals on Tree

\sum (連結成分数)を求めたい
これを愚直に求めると\sum^{N}_{L=1} \sum^{N}_{R=L} f(L,R)となり\mathcal{O}(N^2)かかってしまう
ここで、木の誘導グラフを考えるとそれらはすべて森となる
森の場合の連結成分数は(頂点数) - (辺の数)で求めることが出来る
よって
\sum (連結成分数) = \sum (頂点数) - (辺の数)
= \sum (頂点数) - \sum (辺の数)として求めることが出来る
頂点数は、長さiの区間が何個出来るかで \sum^{N}_{i=1} i \times (N - i + 1)で求められる
辺の数は、ある辺が何回寄与するかを考える
u \lt vとするとuとvが含まれる区間というのは 1 \leq l \leq uかつ v \leq r \leq Nを満たす区間なので
u \times (N - v + 1)が各辺が寄与する回数となり、その総和を求めた後、辺の数からこれを引いてあげればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll vertices = 0, edges = 0;
    for(int i=1;i<=N;i++){
        vertices += i * (N - i + 1);
    }
    REP(i,N-1){
        ll u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        edges += u * (N - v + 1);
    }
    cout << vertices - edges << endl;
}