AtCoder Beginner Contest 243（ABC243）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 243での成績：965位
パフォーマンス：1499相当
レーティング：1541→1536 (-5) :(#AtCoder #ABC243 https://t.co/l9vyoTOksF

— ボンド@競プロ (@bond_cmprog) March 12, 2022

A - Shampoo

$ V = V \% (A + B + C) $ として考えていいので、この状態で誰が不足した状態になるかをシミュレートする

提出コード

void solve(){
    int V, A ,B, C;
    cin >> V >> A >> B >> C;
    V %= (A + B + C);
    if(V < A) cout << "F" << endl;
    else if(V < A + B) cout << "M" << endl;
    else cout << "T" << endl;
}

B - Hit and Blow

$ O(N^2) $ でも間に合うので全探索で数えればいい
もしくは、mapなどを使うことで計算量を改善できる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    int ans1 = 0;
    REP(i,N) if(A[i] == B[i]) ans1++;
    map<int, int> mp;
    REP(i,N) mp[B[i]]++;
    int ans2 = 0;
    REP(i,N){
        int cnt = mp[A[i]];
        if(A[i] == B[i]) cnt--;
        ans2 += cnt;
    }
    cout << ans1 << endl;
    cout << ans2 << endl;
}

C - Collision 2

$ Y $ が同じ $ X $ について昇順に $ S_i $ を並べると、その文字列の中にRLが存在するかどうかを判定すればいい

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    REP(i,N) cin >> X[i] >> Y[i];
    string S;
    cin >> S;
    map<int, vector<pair<int, char>>> mp;
    REP(i,N){
        mp[Y[i]].emplace_back(X[i], S[i]);
    }
    string ans = "No";
    for(auto [k, v] : mp){
        sort(ALL(v));
        REP(i,(int)v.size()-1){
            if(v[i].second == 'R' and v[i+1].second == 'L') ans = "Yes";
        }
    }
    cout << ans << endl;
}

D - Moves on Binary Tree

今いる頂点の番号を2進数で考え、文字列で表現する
Uの操作は、文字列の末尾をpopする
Lの操作は、末尾に0を追加する
Rの操作は、末尾に1を追加する
操作として置き換えられるのですべての操作を終えたあとに文字列を10進数に戻せばいい

提出コード

void solve(){
    ll N, X;
    cin >> N >> X;
    string ans = "";
    while(X > 0){
        ans += char(X % 2 + '0');
        X /= 2;
    }
    reverse(ALL(ans));
    string S;
    cin >> S;
    for(auto c : S){
        if(c == 'U') ans.pop_back();
        else if(c == 'L') ans += '0';
        else if(c == 'R') ans += '1';
    }
    ll sum = 0;
    reverse(ALL(ans));
    REP(i,ans.size()) if(ans[i] == '1') sum += (1LL << i);
    cout << sum << endl;
}

E - Edge Deletion

$ dist[i][j] := i $ から $ j $ までの最短距離として全点間の最短距離を予め求めておく
辺 $ i $ を削除してもいいかどうかは $ A_i $ から $ B_i $ までの距離が $ C_i $ 以下となるようなパスが他にあるかどうかで判定できる
よって、予めワーシャルフロイドで最短距離を求めておき、各辺に対し判定を行えばいい

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector dist(N, vector<ll>(N, LINF));
    vector<ll> A(M), B(M), C(M);
    REP(i,M){
        cin >> A[i] >> B[i] >> C[i];
        --A[i], --B[i];
        dist[A[i]][B[i]] = dist[B[i]][A[i]] = C[i];
    }
    REP(k,N) REP(i,N) REP(j,N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
    int ans = 0;
    REP(i,M){
        bool ok = false;
        REP(j,N){
            if(dist[A[i]][j] + dist[j][B[i]] <= C[i]) ok = true;
        }
        ans += ok;
    }
    cout << ans << endl;
}