接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 204（ABC204）

AtCoder Beginner Contest 204（ABC204）

AtCoderBeginnerContest AtCoderBeginnerContest204 ABC ABC204

atcoder.jp

A - Rock-paper-scissors

$ x = y $ のときは同じものを、そうでないときは $ x, y $ と異なるものを出力
提出コード

void solve(){
    int x, y;
    cin >> x >> y;
    if(x == y) cout << x << endl;
    else cout << (3 ^ x ^ y) << endl;
}

B - Nuts

$ A_i \gt 10 $ のとき $ A_i - 10 $ を加算し、その総和が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 0;
    REP(i,N) if(A[i] > 10) ans += A[i] - 10;
    cout << ans << endl;
}

C - Tour

各頂点ごとに、BFSなどでたどり着ける自分を含めた頂点の個数を答えに加算する
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].emplace_back(b);
    }
    ll ans = 0;
    REP(i,N){
        queue<int> q;
        vector<int> used(N);
        q.emplace(i);
        while(!q.empty()){
            int v = q.front(); q.pop();
            if(used[v]) continue;
            used[v]++;
            ans++;
            for(auto nv : G[v]) if(!used[nv]) q.emplace(nv);
        }
    }
    cout << ans << endl;
}

D - Cooking

$ T_i $ の総和を $ sum $ とする
片方のオーブンに使う料理の集合を決めたとして、そのかかる時間を $ t $ とすると、残りの料理をもう片方のオーブンを使ったときにかかる時間は $ sum - t $ となり $ \max(t, sum - t) $ が全体でかかる時間となる
そのため、片方のみのオーブンを使ったときにかかる時間をDPで求め、その中で全体にかかる時間の最小を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> T(N);
    REP(i,N) cin >> T[i];
    int sum = accumulate(T.begin(), T.end(), 0);
    vector<int> dp(101010);
    dp[0] = 1;
    REP(i,N){
        vector<int> nxt(101010);
        REP(j,sum+1){
            if(dp[j] == 0) continue;
            nxt[j] = dp[j];
            nxt[j+T[i]] = dp[j];
        }
        swap(nxt, dp);
    }
    int ans = INF;
    REP(i,sum+1) if(dp[i] > 0){
        chmin(ans, max(sum - i, i));
    }
    cout << ans << endl;
}

E - Rush Hour 2

道路 $ i $ を時刻 $ t $ のときに通行するコストは $ f(t) = t + C_i + \frac{D_i}{t + 1} $ となる
この関数は $ \sqrt{D_i} $ 付近で最小となることが実験などによりわかる
そのため、$ \sqrt{D_i} $ の前後を確認してその中で最小のコストとなるものを選べばいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M), C(M), D(M);
    vector<vector<tuple<int, int>>> G(N);
    REP(i,M){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        --A[i], --B[i];
        G[A[i]].emplace_back(B[i], i);
        G[B[i]].emplace_back(A[i], i);
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(0, 0);
    vector<ll> dist(N, LINF);
    dist[0] = 0;
    while(!pq.empty()){
        auto [t, cur] = pq.top(); pq.pop();
        if(dist[cur] < t) continue;
        for(auto [nv, i] : G[cur]){
            ll sq = sqrt(D[i]);
            for(int j=sq-5;j<=sq+5;j++){
                if(j < t) continue;
                ll nc = j + C[i] + D[i] / (j + 1);
                if(chmin(dist[nv], nc)) pq.emplace(dist[nv], nv);
            }
            if(chmin(dist[nv], t + C[i] + D[i] / (t + 1))) pq.emplace(dist[nv], nv);
        }
    }
    cout << (dist[N-1] == LINF ? -1 : dist[N-1]) << endl;
}