AtCoder Beginner Contest 205（ABC205）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 205での成績：1191位
パフォーマンス：1381相当
レーティング：1441→1435 (-6) :(#AtCoder #ABC205 https://t.co/fQNwZWT4s5

— ボンド@競プロ (@bond_cmprog) June 13, 2021

A - kcal

$ 1 $ mLあたり $ \frac{A}{100} $ kcalなので $ \frac{AB}{100} $ を出力
提出コード

void solve(){
    double A, B;
    cin >> A >> B;
    printf("%.12lf\n", A / 100 * B);
}

B - Permutation Check

$ A $ を昇順ソートした後、$ {1, 2, ..., N} $ と一致するかどうかを判定
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> B(N);
    iota(B.begin(), B.end(), 1);
    sort(A.begin(), A.end());
    if(A == B) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - POW

$ A = B $ のときは = となり、それ以外の場合を考える
$ C $ が奇数の場合、$ A, B $ の符号は変化しないので、$ A, B $ の大小比較を行えばいい
$ C $ が偶数の場合、$ A, B $ が負の場合、符号が変化するので、$ |A|, |B| $ の大小比較を行う
提出コード

void solve(){
    ll A, B, C;
    cin >> A >> B >> C;
    if(A == B) cout << "=" << endl;
    else if(C % 2 == 1){
        if(A < B) cout << "<" << endl;
        else cout << ">" << endl;
    }
    else{
        if(abs(A) < abs(B)) cout << "<" << endl;
        else if(abs(A) > abs(B)) cout << ">" << endl;
        else cout << "=" << endl;
    }
}

D - Kth Excluded

二分探索を行う
ある整数 $ x $ が題意を満たす $ K_i $番目以上の整数のうち、最小の整数を求めればいい
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    vector<ll> query(Q);
    REP(i,Q) cin >> query[i];
    auto check = [&](ll m, ll K) -> bool{
        ll cnt = upper_bound(A.begin(), A.end(), m) - A.begin();
        return m - cnt >= K;
    };

    for(auto K : query){
        ll l = 0, r = 2*LINF;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(check(m, K)) r = m;
            else l = m;
        }
        cout << r << endl;
    }
}

F - Grid and Tokens

解説AC
解説のとおりに辺を貼り、最大流を求める
提出コード

void solve(){
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> A(N), B(N), C(N), D(N);
    REP(i,N){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        --A[i], --B[i], --C[i], --D[i];
    }
    int s = 2 * N + H + W, t = s + 1;
    mf_graph<int> g(2 * N + H + W + 2);
    REP(i,H) g.add_edge(s, i, 1);
    REP(i,W) g.add_edge(2*N+H+i, t, 1);

    REP(i,N){
        for(int h=A[i];h<=C[i];h++) g.add_edge(h, H + i, 1);
        g.add_edge(H + i, H + N + i, 1);
        for(int w=B[i];w<=D[i];w++) g.add_edge(H + N + i, H + N + N + w, 1);
    }
    cout << g.flow(s, t) << endl;
}