接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 184（ABC184）

AtCoder Beginner Contest 184（ABC184）

AtCoderBeginnerContest AtCoderBeginnerContest184 ABC ABC184

atcoder.jp

A - Determinant

定義が書いてあるのでそれを出力
提出コード

void solve(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << a * d - b * c << endl;
}

B - Quizzes

点数をシミュレートする
提出コード

void solve(){
    int N, X;
    string S;
    cin >> N >> X >> S;
    REP(i,N){
        if(S[i] == 'o') X++;
        else{
            X = max(0, X-1);
        }
    }
    cout << X << endl;
}

C - Super Ryuma

頭壊れる
任意の点に最大3手以内にいける
$ (r_1, c_1) = (r_2, c_2) $の場合は0でそれ以外の場合を考える
初期状態から1手で行けるときは$ |r_1 - r_2| + |c_1 - r_c| \leq 3 $ もしくは対角成分上にあるときならば可能
2手で行けるときは、市松模様にマスに色を塗ったときに同じ色の場合2手で行ける
それ以外の場合、$ |r_1 - r_2| + |c_1 - r_c| \leq 3 $が必要になるので移動できる箇所を全探索し、上記の判定をもう一度考える
提出コード

void solve(){
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    if(r1 == r2 and c1 == c2) cout << 0 << endl;
    else if(abs(r1 - r2) + abs(c1 - c2) <= 3) cout << 1 << endl;
    else if(r1 + c1 == r2 + c2) cout << 1 << endl;
    else if(r1 - c1 == r2 - c2) cout << 1 << endl;
    else if(abs(r2 - r1) % 2 == abs(c2 - c1) % 2) cout << 2 << endl;
    else{
        int ans = INF;
        for(int i=-3;i<=3;i++) for(int j=-3;j<=3;j++){
            if(i == 0 and j == 0) continue;
            ll nr = r1 + i, nc = c1 + j;
            if(abs(r1-nr) + abs(c1-nc) > 3) continue;
            if(r2 == nr and c2 == nc) chmin(ans, 1);
            else if(nr + nc == r2 + c2) chmin(ans, 2);
            else if(nr - nc == r2 - c2) chmin(ans, 2);
            else if(abs(nr - r2) + abs(nc - c2) <= 3) chmin(ans, 2);
            else chmin(ans, 3);
        }
        cout << ans << endl;
    }
}

D - increment of coins

期待値のDPをする
$ dp[a][b][c] := $ 金貨がa枚、銀貨がb枚、銅貨がc枚あるときの期待値とすると3つのうちどれが選ばれるかで
$ dp[a][b][c] = \frac{dp[a+1][b][c] \times a + dp[a][b+1][c] \times b + dp[a][b][c+1] \times c}{a + b + c} + 1 $となる
実装はメモ化再起のほうが楽そう
提出コード

void solve(){
    int A, B, C;
    cin >> A >> B >> C;
    if(A >= 100 or B >= 100 or C >= 100){
        cout << 0 << endl;
        return;
    }
    vector dp(101, vector(101, vector(101, -1.0)));
    auto dfs = [&](auto && self, int a, int b, int c) -> double{
        if(a >= 100 or b >= 100 or c >= 100) return 0;
        if(dp[a][b][c] > -1) return dp[a][b][c];
        double sum = a + b + c;
        return dp[a][b][c] = (self(self, a+1, b, c) * a + self(self, a, b+1, c) * b + self(self, a, b, c+1) * c) / sum + 1;
    };
    printf("%.12lf\n", dfs(dfs, A, B, C));
}

E - Third Avenue

各テレポーターごとに移動可能なマスを予め保存しておく
今いるマスがテレポーターなら同じテレポーターのマスにコスト1で移動出来るとしてBFSをする
テレポーターを使う場合同じテレポーターは一回までしか使わなくていいので、すでに使ったことのあるテレポーターの場合、もう使えないものとして無視すればいい
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    vector<vector<pair<int, int>>> alp(26);
    int sh, sw, gh, gw;
    REP(i,H) REP(j,W){
        if(fi[i][j] == 'S') sh = i, sw = j;
        else if(fi[i][j] == 'G') gh = i, gw = j;
        else if(fi[i][j] != '#' and fi[i][j] !='.'){
            alp[fi[i][j] - 'a'].emplace_back(i, j);
        }
    }
    vector<vector<int>> dist(H, vector<int>(W, INF));
    queue<pair<int, int>> q;
    q.emplace(sh, sw);
    dist[sh][sw] = 0;
    vector<bool> used(26);
    while(!q.empty()){
        auto [h, w] = q.front(); q.pop();
        if('a' <= fi[h][w] and fi[h][w] <= 'z' and !used[fi[h][w]-'a']){
            used[fi[h][w]-'a'] = true;
            for(auto [nh, nw] : alp[fi[h][w]-'a']){
                if(dist[nh][nw] != INF) continue;
                if(chmin(dist[nh][nw], dist[h][w] + 1)){
                    q.emplace(nh, nw);
                }
            }
        }
        REP(i,4){
            int nh = h + dx[i], nw = w + dy[i];
            if(nh < 0 or nh >= H or nw < 0 or nw >= W or fi[nh][nw] == '#') continue;
            if(dist[nh][nw] != INF) continue;
            if(chmin(dist[nh][nw], dist[h][w] + 1)) q.emplace(nh, nw);
        }
    }
    ll ans = dist[gh][gw];
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

F - Programming Contest

半分全列挙をする
集合の半分をbit全探索で各組み合わせのごとの和を昇順ソートした配列を作る
もう半分の集合にbit全探索を行い$ T $以下になる和の最大を二分探索で求める
提出コード

void solve(){
    int N;
    ll T;
    cin >> N >> T;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    int n2 = N / 2;
    vector<ll> v(1<<n2);
    REP(i,1<<n2){
        ll sumT = 0;
        REP(j,n2) if(i >> j & 1) sumT += A[j];
        v.emplace_back(sumT);
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    dump(v);
    REP(i,1<<(N-n2)){
        ll sumT = 0;
        REP(j,N-n2) if(i >> j & 1) sumT += A[j+n2];
        dump(sumT);
        if(sumT <= T){
            ll t = *(upper_bound(v.begin(), v.end(),T - sumT) - 1);
            chmax(ans, sumT + t);
        }
    }
    cout << ans << endl;
}