AtCoder Beginner Contest 218（ABC218） - 接着剤の精進日記

atcoder.jp

草
Bondo416さんのAtCoder Beginner Contest 218での成績：2693位
パフォーマンス：960相当
レーティング：1519→1473 (-46) :(#AtCoder #ABC218 https://t.co/FX0Ik0WPTG
— ボンド@競プロ (@bond_cmprog) September 11, 2021

A - Weather Forecast

$ N $ 日目が o かどうか
提出コード

void solve(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    cout << (S[N-1] == 'o' ? "Yes" : "No") << endl;
}

B - qwerty

$ i $ 番目はアルファベット順で $ P_i $ 番目の文字
提出コード

void solve(){
    vector<int> P(26);
    REP(i,26) cin >> P[i];
    REP(i,26) cout << char(P[i] - 1 + 'a');
    cout << endl;
}

C - Shapes

盤面を固定したとき、 $ S $ と $ T $ の一番左上の # の位置を平行移動で合わせて比較する
# の数が $ S, T $ で異なればそもそも一致出来ない
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N), T(N);
    REP(i,N) cin >> S[i];
    REP(i,N) cin >> T[i];
    int cnt_s = 0, cnt_t = 0;
    REP(i,N) REP(j,N) cnt_s += (S[i][j] == '#');
    REP(i,N) REP(j,N) cnt_t += (T[i][j] == '#');
    if(cnt_s != cnt_t){
        cout << "No" << endl;
        return;
    }
    auto rot = [](vector<string> &s) -> vector<string>{
        vector<string> res(s[0].size());
        REP(i,s.size()){
            REP(j,s[0].size()){
                res[j].push_back(s[i][j]);
            }
        }
        REP(i,res.size()){
            reverse(res[i].begin(), res[i].end());
        }
        return res;
    };
    auto find_left_top = [&](vector<string> &s) -> pair<int, int>{
        REP(i,N) REP(j,N) if(s[i][j] == '#') return {i, j};
    };
    int sum = cnt_s;
    bool ans = false;
    REP(_, 4){
        auto [sx, sy] = find_left_top(S);
        auto [tx, ty] = find_left_top(T);
        int dx = tx - sx;
        int dy = ty - sy;
        bool ok = true;
        int cnt = 0;
        REP(i,N) REP(j,N){
            int x = i + dx;
            int y = j + dy;
            if(x < 0 or x >= N or y < 0 or y >= N) continue;
            if(S[i][j] != T[x][y]) break;
            if(S[i][j] == '#' and T[x][y] == '#') cnt++;
        }
        ans |= (cnt == sum);
        S = rot(S);
    }

    cout << (ans ? "Yes" : "No") << endl;
}

D - Rectangles

$ x_i \lt x_j $ かつ $ y_i \lt y_j $ を満たす2点 $ (i, j) $ を固定すると、残りの二点は一意に決まる
そのような点は $ (x_i, y_j) , (x_j, y_i) $ となるのでmapなどでこの二点が存在するかチェックする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    map<pair<int, int>, int> mp;
    REP(i,N){
        cin >> x[i] >> y[i];
        mp[{x[i], y[i]}]++;
    }
    int ans = 0;
    REP(i,N) REP(j,N){
        if(!(x[i] < x[j] and y[i] < y[j])) continue;
        if(mp.count({x[i], y[j]}) and mp.count({x[j], y[i]})) ans++;
    }
    cout << ans << endl;
}

E - Destruction

報酬の昇順に最小全域木を作っていく
このとき、最小全域木に含まれない辺は取り除いてもいいのでそのような辺の報酬を加えていく
ただし、辺は取り除かなくてもいいので取り除ける辺で負の報酬のものは無視する
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<tuple<int, int, int>> edge(M);
    REP(i,M){
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {c, --a, --b};
    }
    sort(edge.begin(), edge.end());
    UnionFind uf(N);
    ll ans = 0;
    for(auto [c, a, b] : edge){
        if(uf.issame(a, b)){
            if(c > 0) ans += c;
            continue;
        }
        uf.unite(a, b);
    }
    cout << ans << endl;
}

F - Blocked Roads

最初にすべての辺が使える状態で最短経路を求める
このとき、最短経路に含まれるような辺は最大でも $ N - 1 $ 個となる
そのため、最初に求めた最短経路に含まれない辺の場合、そのまま求めた距離を出力すればいい
残りの辺はそれぞれ求める必要があるが、愚直に求めても $ O(N(N + M)) $ となるので十分間に合う
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> g(N);
    REP(i,M){
        int s, t;
        cin >> s >> t;
        g[--s].emplace_back(--t, i);
    }
    vector dist(N, INF);
    vector prev(N, make_pair(-1, -1));
    queue<int> q;
    q.emplace(0);
    dist[0] = 0;
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(auto [nv, edge] : g[v]){
            if(dist[nv] < INF) continue;
            dist[nv] = dist[v] + 1;
            prev[nv] = {v, edge};
            q.emplace(nv);
        }
    }
    if(dist[N-1] == INF){
        REP(i,M) cout << -1 << endl;
        return;
    }
    vector used(M, 0);
    pair<int, int> cur = prev[N-1];
    while(cur != make_pair(-1, -1)){
        auto [nv, edge] = cur;
        used[edge] = 1;
        cur = prev[nv];
    }
    REP(i,M){
        if(!used[i]) cout << dist[N-1] << endl;
        else{
            vector dist2(N, INF);
            queue<int> q;
            q.emplace(0);
            dist2[0] = 0;
            while(!q.empty()){
                int v = q.front(); q.pop();
                for(auto [nv, edge] : g[v]){
                    if(dist2[nv] < INF) continue;
                    if(edge == i) continue;
                    dist2[nv] = dist2[v] + 1;
                    q.emplace(nv);
                }
            }
            cout << (dist2[N-1] == INF ? -1 : dist2[N-1]) << endl;
        }
    }
}