接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 183（ABC183）

AtCoder Beginner Contest 183（ABC183）

AtCoderBeginnerContest AtCoderBeginnerContest183 ABC ABC183

atcoder.jp

A - ReLU

そのまま式の値を出力
提出コード

void solve(){
    int x;
    cin >> x;
    if(x >= 0) cout << x << endl;
    else cout << 0 << endl;
}

B - Billiards

Dまでだと一番難しく感じた
syからy = 0までとy = 0からgyまでの間に$ gx - sx $だけ移動する
これは、sxとgxをsy : gyで内分する点になる
提出コード

void solve(){
    double sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    printf("%.12lf\n", sx + (gx - sx) / (sy + gy) * sy);
}

C - Travel

$ 8! $を全探索しても間に合うのでnext_permutationなどで全探索をする
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> T(N, vector<ll>(N));
    REP(i,N) REP(j,N) cin >> T[i][j];
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    int ans = 0;
    do{
        if(idx[0] != 0) continue;
        ll cur = 0;
        for(int i=1;i<N;i++){
            cur += T[idx[i]][idx[i-1]];
        }
        cur += T[idx.back()][0];
        if(cur == K) ans++;
    }while(next_permutation(idx.begin(), idx.end()));
    cout << ans << endl;
}

D - Water Heater

imos法を使う
imos法で累積和を求めた後、各時刻で$ W $を超える箇所があるかをチェック
提出コード

void solve(){
    ll N, W;
    cin >> N >> W;
    vector<ll> S(N), T(N), P(N);
    vector<ll> imos(202020);
    REP(i,N){
        cin >> S[i] >> T[i] >> P[i];
        imos[S[i]] += P[i];
        imos[T[i]] -= P[i];
    }
    REP(i,202020-1) imos[i+1] += imos[i];
    string ans = "Yes";
    
    REP(i,202020) if(imos[i] > W) ans = "No";
    cout << ans << endl;
}

E - Queen on Grid

頭壊れる
各方向に対してのみ動くとするとその遷移は一つ前までの状態とそこまでの累積和になる
そのため、横、下、斜め下の3方向に対して累積和を持ちながらdpで更新していく
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    vector<vector<mint>> dp(H, vector<mint>(W));
    vector<vector<mint>> sum1(H+1, vector<mint>(W+1));
    auto sum2 = sum1, sum3 = sum1;
    dp[0][0] = 1;
    for(int i=0;i<H;i++) for(int j=0;j<W;j++){
        if(fi[i][j] == '#') continue;
        dp[i][j] += sum1[i][j] + sum2[i][j] + sum3[i][j];
        if(i + 1 < H) sum1[i+1][j] += dp[i][j] + sum1[i][j];
        if(j + 1 < W and fi[i][j+1] != '#') sum2[i][j+1] += dp[i][j] + sum2[i][j];
        if(i + 1 < H and j + 1 < W) sum3[i+1][j+1] = dp[i][j] + sum3[i][j];
    }
    cout << dp[H-1][W-1] << endl;
}

F - Confluence

マージテクを使う
各生徒の集合をUnionFindで管理をし、その集合の各クラスの生徒数をmapで管理をする
集合同士をmergeする際にサイズの大きい方に小さい方をmergeすればいい
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<map<int, int>> mp(N);
    UnionFind uf(N);
    REP(i,N){
        int c;
        cin >> c;
        mp[i][c] = 1;
    }
    while(Q--){
        int q, x, y;
        cin >> q >> x >> y;
        if(q == 1){
            x--, y--;
            if(uf.issame(x, y)) continue;
            if(uf.size(x) < uf.size(y)) swap(x, y);
            for(auto &p : mp[uf.root(y)]){
                if(mp[uf.root(x)].count(p.first)) mp[uf.root(x)][p.first] += p.second;
                else mp[uf.root(x)][p.first] = p.second;
            }
            uf.unite(x, y);
        }
        else{
            --x;
            cout << mp[uf.root(x)][y] << endl;
        }
    }
}