接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 210（ABC210）

AtCoder Beginner Contest 210（ABC210）

AtCoderBeginnerContest AtCoderBeginnerContest210 ABC ABC210

atcoder.jp

A - Cabbages

$ N \leq A $ の間 $ X $ ずつ加算し、$ N > A $ のとき、$ Y $ ずつ加算する
提出コード

void solve(){
    int N, A, X, Y;
    cin >> N >> A >> X >> Y;
    ll sum = X * min(A, N);
    N -= A;
    sum += max(N, 0) * Y;
    cout << sum << endl;
}

B - Bouzu Mekuri

初めて1が出てきたときの偶奇を見る
提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    REP(i,N){
        if(S[i] == '1'){
            if(i % 2 == 0) cout << "Takahashi" << endl;
            else cout << "Aoki" << endl;
            return;
        }
    }
}

C - Colorful Candies

$ K $ 個の区間の種類数とその個数をmapなどで管理をする
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<ll> C(N);
    REP(i,N) cin >> C[i];
    map<int, int> mp;
    int cnt = 0;
    REP(i,K){
        if(!mp.count(C[i])){
            cnt++;
        }
        mp[C[i]]++;
    }
    int ans = cnt;
    for(int i=K;i<N;i++){
        if(mp[C[i-K]] == 1){
            mp.erase(C[i-K]);
            cnt--;
        }
        else mp[C[i-K]]--;
        if(!mp.count(C[i])){
            cnt++;
        }
        mp[C[i]]++;
        chmax(ans, cnt);
    }
    cout << ans << endl;
}

D - National Railway

$ i' \lt i $ かつ $ j' \lt j $ を満たす2つのマスを選んだとすると、そのコストは $ A_{i, j} + A_{i', j'} + C(i + j - i' - j') $ となる
これを整理すると、$ A_{i, j} + C(i + j) $ と $ A_{i', j'} - C(i' + j') $ に分けられる
したがって、後者をdpで更新しながら最小値を求めればいい
ただし、左上から右下への遷移だけではなく、左下から右上への遷移もあるので $ A $ を反転して上記のやり方で求めればいい
提出コード

void solve(){
    ll H, W, C;
    cin >> H >> W >> C;
    vector<vector<ll>> A(H, vector<ll>(W));
    REP(i,H) REP(j,W) cin >> A[i][j];
    ll ans = LINF;
    REP(_,2){
        vector dp(H, vector(W, LINF));
        REP(h,H) REP(w,W){
            if(h > 0) chmin(dp[h][w], dp[h-1][w]);
            if(w > 0) chmin(dp[h][w], dp[h][w-1]);
            chmin(ans, dp[h][w] + C * (h + w) + A[h][w]);
            chmin(dp[h][w], A[h][w] - C * (h + w));
        }
        reverse(A.begin(), A.end());
    }
    cout << ans << endl;
}

E - Ring MST

コストの小さい順に予めソートをしておく
今 $ N $ 個の連結成分があり、$ A_i $ の操作を行うとその連結成分数は $ gcd(N, A_i) $ 個にすることができる
そのため、$ i $ 番目の操作を行ったときに $ (N - gcd(N, A_i)) C_i $ 費用がかかるのでそれを答えに加算する
操作を行った後、$ N = gcd(N, A_i) $ と更新していき、最終的に $ N = 1 $ ならば上記で求めた答えを、そうでないときは-1を出力する
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(M), C(M);
    REP(i,M) cin >> A[i] >> C[i];
    vector<int> idx(M);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return C[a] < C[b];
    });
    ll ans = 0;
    ll g = N;
    for(int i : idx){
        ll nxt = gcd(A[i], g);
        ans += (g - nxt) * C[i];
        g = nxt;
        if(g <= 1) break;
    }
    if(g != 1) cout << -1 << endl;
    else cout << ans << endl;
}