【ABC370】AtCoder Beginner Contest 370【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）

コンテストURL

開催日

2024/09/07 21:00-22:40

---

A: Raise Both Hands

解法

• 問題文通りに判定する

ABC370A.cpp

#include <iostream>
using namespace std;

int main(){
    int l, r;
    cin >> l >> r;

    if(l==1 && r==0){
        cout << "Yes" << endl;
    }else if(l==0 && r==1){
        cout << "No" << endl;
    }else{
        cout << "Invalid" << endl;
    }

    return 0;
}

B: Binary Alchemy

解法

• 問題文通りにシミュレーションする

ABC370B.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<vector<int>> A(n);
    int a;
    for(int i=0; i<n; i++){
        for(int j=0; j<i+1; j++){
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    int now = 0;
    for(int i=0; i<n; i++){
        if(now>=i){
            now = A[now][i];
        }else{
            now = A[i][now];
        }
    }

    cout << now + 1 << endl;
    return 0;
}

C: Word Ladder

解法

• $S_i > T_i$ と $S_i < T_i$ で場合分けする
• $S_i > T_i$ の場合を $S_i < T_i$ の場合より優先する
• $S_i > T_i$ であるもののうち $i$ が小さいものから優先する
• $S_i < T_i$ であるもののうち $i$ が大きいものから優先する

ABC370C.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    string s, t;
    cin >> s >> t;

    vector<int> A, B;
    for(int i=0; i<s.size(); i++){
        if(s[i]>t[i]){
            A.push_back(i);
        }else if(s[i]<t[i]){
            B.push_back(i);
        }
    }

    sort(A.begin(), A.end());
    sort(B.rbegin(), B.rend());
    vector<string> V;
    for(int i=0; i<A.size(); i++){
        s[A[i]] = t[A[i]];
        V.push_back(s);
    }
    for(int i=0; i<B.size(); i++){
        s[B[i]] = t[B[i]];
        V.push_back(s);
    }

    cout << V.size() << endl;
    for(int i=0; i<V.size(); i++){
        cout << V[i] << endl;
    }

    return 0;
}

D: Cross Explosion

解法

• vector<set<int>> で壁が存在するマスを各列・各行について記録する
• lower_bound() と upper_bound() で上下左右の最初に現れる壁を探索する
• set<int> st; の場合は、 st.lower_bound(key) とすることに注意する

1. begin() end() で判定する
2. set<int> に番兵を追加して工夫する

ABC370D_1.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <tuple>
using namespace std;

int main(){
    int h, w, q;
    cin >> h >> w >> q;

    vector<set<int>> yoko(h);
    vector<set<int>> tate(w);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            yoko[i].insert(j);
        }
    }
    for(int i=0; i<w; i++){
        for(int j=0; j<h; j++){
            tate[i].insert(j);
        }
    }

    int cnt = h * w;
    int r, c;
    for(int i=0; i<q; i++){
        cin >> r >> c;
        r--;
        c--;

        if(yoko[r].count(c)){
            yoko[r].erase(c);
            tate[c].erase(r);
            cnt--;
        }else{
            auto yokominv = yoko[r].lower_bound(c);
            if(yokominv!=yoko[r].begin()){
                yokominv--;
                yoko[r].erase(*yokominv);
                tate[*yokominv].erase(r);
                cnt--;
            }
            auto yokomaxv = yoko[r].upper_bound(c);
            if(yokomaxv!=yoko[r].end()){
                yoko[r].erase(*yokomaxv);
                tate[*yokomaxv].erase(r);
                cnt--;
            }
            auto tateminv = tate[c].lower_bound(r);
            if(tateminv!=tate[c].begin()){
                tateminv--;
                yoko[*tateminv].erase(c);
                tate[c].erase(*tateminv);
                cnt--;
            }
            auto tatemaxv = tate[c].upper_bound(r);
            if(tatemaxv!=tate[c].end()){
                yoko[*tatemaxv].erase(c);
                tate[c].erase(*tatemaxv);
                cnt--;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

ABC370D_2.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main(){
    int h, w, q;
    cin >> h >> w >> q;

    vector<set<int>> yoko(h+1);
    vector<set<int>> tate(w+1);
    for(int i=0; i<h; i++){
        for(int j=0; j<w+2; j++){
            yoko[i+1].insert(j);
        }
    }
    for(int i=0; i<w; i++){
        for(int j=0; j<h+2; j++){
            tate[i+1].insert(j);
        }
    }

    int cnt = h * w;
    int r, c;
    for(int i=0; i<q; i++){
        cin >> r >> c;

        if(yoko[r].count(c)){
            yoko[r].erase(c);
            tate[c].erase(r);
            cnt--;
        }else{
            auto yokominv = yoko[r].lower_bound(c);
            yokominv--;
            if(*yokominv!=0){
                yoko[r].erase(*yokominv);
                tate[*yokominv].erase(r);
                cnt--;
            }
            auto yokomaxv = yoko[r].upper_bound(c);
            if(*yokomaxv!=w+1){
                yoko[r].erase(*yokomaxv);
                tate[*yokomaxv].erase(r);
                cnt--;
            }
            auto tateminv = tate[c].lower_bound(r);
            tateminv--;
            if(*tateminv!=0){
                tate[c].erase(*tateminv);
                yoko[*tateminv].erase(c);
                cnt--;
            }
            auto tatemaxv = tate[c].upper_bound(r);
            if(*tatemaxv!=h+1){
                tate[c].erase(*tatemaxv);
                yoko[*tatemaxv].erase(c);
                cnt--;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}