AtCoder Beginner Contest 231（ABC231）

atcoder.jp

Bondo416さんのパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)での成績：919位
パフォーマンス：1425相当
レーティング：1461→1457 (-4) :(#AtCoder #パナソニックプログラミングコンテスト2021(ABC231) https://t.co/0IbB3aehs6

— ボンド@競プロ (@bond_cmprog) December 11, 2021

A - Water Pressure

$ \frac{D}{100} $ を出力

提出コード

void solve(){
    double D;
    cin >> D;
    printf("%.12lf\n", D/100.0);
}

B - Election

mapなどで投票数を管理する

提出コード

void solve(){
    int N;
    cin >> N;
    map<string, int> mp;
    REP(i,N){
        string S;
        cin >> S;
        mp[S]++;
    }
    int ma = 0;
    string ans = "";
    for(auto [x, n] : mp) if(chmax(ma, n)) ans = x;
    cout << ans << endl;
}

C - Counting 2

二分探索などで $ x_i $ 以上の個数を数える

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    sort(ALL(A));
    while(Q--){
        int x;
        cin >> x;
        cout << N - (lower_bound(ALL(A), x) - A.begin()) << endl;
    }
}

D - Neighbors

次数が2より大きいものがあればNo
もしくは、ループが存在する場合もNoとなる

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> deg(N);
    UnionFind uf(N);
    string ans = "Yes";
    REP(i,M){
        int a, b;
        cin >> a >> b;
        deg[--a]++;
        deg[--b]++;
        if(uf.issame(a, b)){
            ans = "No";
        }
        uf.unite(a, b);
    }
    REP(i,N) if(deg[i] > 2) ans = "No";
    cout << ans << endl;
}

F - Jealous Two

$ A_i \geq A_j $ かつ $ B_i \leq B_j $ を満たす $ (i, j) $ の個数を数える
$ A_i $ の昇順、同値の場合は $ B_i $ の降順にソートを行う
$ A_ i $ の昇順に見ていくことで、$ B_i \leq B_j $ を満たす個数のみをカウントしていけばいい
$ (A_i, B_i) = (A_j, B_j) $ 存在する場合、それらをまとめて処理する必要がある

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    Compress<int> cmp_a, cmp_b;
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    vector<pair<int, int>> vp(N);
    map<pair<int, int>, ll> mp;
    REP(i,N){
        vp[i] = {A[i], -B[i]};
        cmp_a.add(A[i]);
        cmp_b.add(B[i]);
        mp[{A[i], B[i]}]++;
    }
    cmp_a.add(0);
    cmp_b.add(0);
    cmp_a.add(2*INF);
    cmp_b.add(2*INF);
    cmp_a.build();
    cmp_b.build();
    int sz = cmp_b.size();
    sort(ALL(vp));
    vp.erase(unique(ALL(vp)), vp.end());
    BIT<int> bit(sz);
    ll ans = 0;
    for(auto [a, b] : vp){
        b = -b;
        int x = cmp_b.get(b);
        ll cnt = mp[{a, b}];
        ll sum = bit.sum(x, sz);
        ans += cnt * (cnt + sum);
        bit.add(x, cnt);
    }
    cout << ans << endl;
}