AtCoder Beginner Contest 213（ABC213）

atcoder.jp

久々黄パフォ & Highest
Bondo416さんのAtCoder Beginner Contest 213での成績：326位
パフォーマンス：2020相当
レーティング：1494→1559 (+65) :)
Highestを更新しました！#AtCoder #ABC213 https://t.co/FpXNfnK7TK

— ボンド@競プロ (@bond_cmprog) August 8, 2021

A - Bitwise Exclusive Or

$ A $ xor $ C = B \Leftrightarrow C = A$ xor $ B $ となるので $ A $ xor $ B $ を出力
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    cout << (A ^ B) << endl;
}

B - Booby Prize

$ A $ の降順にソートしたインデックス配列を別に持つ
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return A[a] > A[b];
    });
    cout << idx[1] + 1 << endl;
}

C - Reorder Cards

$ A, B $ それぞれで座圧をする
提出コード

void solve(){
    ll H, W, N;
    cin >> H >> W >> N;
    vector<int> A(N), B(N);
    Compress<int> cmpA, cmpB;
    REP(i,N){
        cin >> A[i] >> B[i];
        cmpA.add(A[i]);
        cmpB.add(B[i]);
    }
    cmpA.build();
    cmpB.build();
    REP(i,N){
        cout << cmpA.get(A[i]) + 1 << " " << cmpB.get(B[i]) + 1 << endl;
    }
}

D - Takahashi Tour

dfsをして行きがけと帰りがけのタイミングでその頂点を出力する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        g[--a].emplace_back(--b);
        g[b].emplace_back(a);
    }
    REP(i,N) sort(g[i].begin(), g[i].end());
    vector<int> used(N);
    auto dfs = [&](auto && self, int v, int par) -> void{
        cout << v + 1 << " ";
        used[v] = 1;
        bool ok = true;
        for(auto nv : g[v]){
            if(nv == par) continue;
            if(used[nv]) continue;
            self(self, nv, v);
            ok = false;
        }
        if(par != -1) cout << par + 1 << " ";
    };
    dfs(dfs, 0, -1);
    cout << endl;
}

E - Stronger Takahashi

ダイクストラをする
# に遷移するとき、#を消すようなパンチの範囲は

...
.#.
...

のように#の周囲8マスとなる
そのため、今までにパンチした回数をcntとすると、#とその周囲8マスにcnt+1で遷移させる
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    vector dist(H, vector(W, INF));
    using T = tuple<int, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.emplace(0, 0, 0);
    dist[0][0] = 1;
    while(!pq.empty()){
        auto [cnt, h, w] = pq.top(); pq.pop();
        if(dist[h][w] < cnt) continue;
        REP(d,4){
            int nh = h + dx[d];
            int nw = w + dy[d];
            if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
            if(fi[nh][nw] == '.'){
                if(chmin(dist[nh][nw], cnt)){
                    pq.emplace(cnt, nh, nw);
                }
            }
            else{
                REP(k,8){
                    int nnh = nh + dx[k];
                    int nnw = nw + dy[k];
                    if(nnh < 0 or nnh >= H or nnw < 0 or nnw >= W) continue;
                    if(chmin(dist[nnh][nnw], cnt+1)){
                        pq.emplace(cnt+1, nnh, nnw);
                    }
                }
            }
        }
    }
    cout << dist[H-1][W-1] << endl;
}