接着剤の精進日記

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

トップ > AtCoderBeginnerContest153 > AtCoder Beginner Contest 153（ABC153）

AtCoder Beginner Contest 153（ABC153）

AtCoderBeginnerContest153 AtCoderBeginnerContest ABC153 ABC

atcoder.jp

ABC初全完！！
なお水パフォ（ど　ぼ　じ　で）
Eに時間かけたり、FでWA生やしまくったのが良くない…

A - Serval vs Monster

\frac{H + A - 1}{A}でおっけー
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, A;
    cin >> H >> A;
    cout << (H + A - 1) / A << endl;
}

B - Common Raccoon vs Monster

sumがH以上かどうかを見ればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, N;
    cin >> H >> N;
    vector<ll> A(N);
    ll sum = 0;
    REP(i,N){
        cin >> A[i];
        sum += A[i];
    }
    if(H <= sum) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Fennec vs Monster

ソートして大きいものに必殺技を使っていく
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> H(N);
    REP(i,N) cin >> H[i];
    sort(H.rbegin(), H.rend());
    ll ans = 0;
    REP(i,N){
        if(K > 0){
            K--;
        }
        else ans += H[i];
    }
    cout << ans << endl;
}

D - Caracal vs Monster

一回の操作でHは半分になって、スライムの数は2倍になっていくので
愚直にシミュレートしていく
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H;
    cin >> H;
    ll ans = 0;
    ll cur = 1;
    while(H > 0){
        H /= 2;
        ans += cur;
        cur *= 2;
    }
    cout << ans << endl;
}

E - Crested Ibis vs Monster

ぱっと見、個数制限なしナップサックっぽい
今回は最大化ではなく最小化したい
Strange Bankじゃない？となり同じようにDPをする
提出コード

ll dp[22222];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    REP(i,22222) dp[i] = LINF;
    dp[0] = 0;
    for(int i=1;i<22222;i++){
        REP(j,N){
            if(i - A[j] >= 0) chmin(dp[i], dp[i-A[j]] + B[j]);
        }
    }
    ll ans = LINF;
    for(int i=H;i<22222;i++) chmin(ans, dp[i]);
    cout << ans << endl;
}

F - Silver Fox vs Monster

区間処理が必要なのでセグ木使いたくなるけど制約的に座圧しないと使えなさそう（コンテスト終了後セグ木使った人多くて驚きました）
こういうときは区間の両端をvectorで持ってimosっぽく処理していけばおっけー（これこどふぉっぽくない？）
後は、今見ている区間で爆弾を何回使ったかを足し引きしていけばいい
方針は結構すぐ辿り着いたんだけど区間の処理でバグったので怒りの区間2倍したら通りました（こら）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, D, A;
    cin >> N >> D >> A;
    vector<tuple<ll, ll, int, int>> X;
    vector<ll> cnt(N);

    REP(i,N){
        ll x, H;
        cin >> x >> H;
        X.emplace_back(2*x, H, -1, i);
        X.emplace_back(2*x+4*D+1, H, 1, i);
    }
    sort(X.begin(), X.end());
    ll ans = 0;
    ll now = 0;
    for(auto t : X){
        ll x, h;
        int flg, idx;
        tie(x, h, flg, idx) = t;
        //cout << x << " " << h << " " << flg << " " << idx << endl;
        if(flg == 1){
            now -= cnt[idx];
        }
        else{
            ll need = (h - now*A + A - 1) / A;
            //cout << x << " " << h << " " << flg << " " << idx << " " << need << endl;
            if(need > 0){
                ans += need;
                cnt[idx] = need;
                now += need;
            }
        }
    }
    cout << ans << endl;
}

おわりに

初全完出来て嬉しい反面ペナでパフォが微妙で悲しいお気持ち
方針はすぐ出てきたので実装でバグらせない！（素振り）