【ABC391】AtCoder Beginner Contest 391【C++】

コンテスト名

AtCoder Beginner Contest 391

コンテストURL

開催日

2025/02/01 21:00-22:40

---

A: Lucky Direction

解法

• map<char, char> で反対の方角を記録して、文字列を変換する

ABC391A.cpp

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    string d;
    cin >> d;

    map<char, char> M;
    M['N'] = 'S';
    M['S'] = 'N';
    M['E'] = 'W';
    M['W'] = 'E';

    for(int i=0; i<d.size(); i++){
        d[i] = M[d[i]];
    }

    cout << d << endl;

    return 0;
}

B: Seek Grid

解法

• 全探索
• $a, b$ を全探索する

ABC391B.cpp

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

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

    vector<vector<char>> S(n, vector<char>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> S[i][j];
        }
    }
    vector<vector<char>> T(m, vector<char>(m));
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            cin >> T[i][j];
        }
    }

    for(int i=0; i<=n-m; i++){
        for(int j=0; j<=n-m; j++){
            bool flag = true;
            for(int k=i; k<i+m; k++){
                for(int l=j; l<j+m; l++){
                    if(S[k][l]!=T[k-i][l-j]){
                        flag = false;
                        break;
                    }
                }
                if(!flag){
                    break;
                }
            }

            if(flag){
                cout << i+1 << " " << j+1 << endl;
                return 0;
            }
        }
    }
}

C: Pigeonhole Query

解法

• 各鳩がいる巣、各巣にいる鳩の羽数を記録しながら、複数の鳩がいる巣の個数を更新する
  • 鳩 $P$ がもといた巣にいた鳩の羽数が $2$ ならば、複数の鳩がいる巣の個数は $1$ 減る
  • 鳩 $P$ が移動する先の巣 $H$ にいた鳩の羽数が $1$ ならば、複数の鳩がいる巣の個数は $1$ 増える

ABC391C.cpp

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

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

    vector<int> V(n), C(n, 1);
    for(int i=0; i<n; i++){
        V[i] = i;
    }

    int num, p, h;
    int cnt = 0;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> p >> h;
            p--;
            h--;

            if(C[V[p]]==2){
                cnt--;
            }
            if(C[h]==1){
                cnt++;
            }
            C[V[p]]--;
            C[h]++;
            V[p] = h;
        }else{
            cout << cnt << '\n';
        }
    }

    return 0;
}

D: Gravity

解法

• 各列について、 $y$ の昇順にソートする
• 各列の $i$ 番目をブロックをまとめて考える
  • $i$ 番目のブロックの個数がちょうど $W$ であれば、 $i$ 番目のブロックのうち $y$ が最大のブロックが $1$ 行目に到達したとき、 $1$ 行目がブロックで埋まる
  • $i$ 番目のブロックの個数が $W$ 未満であれば、 $i$ 番目のブロックがすべて $1$ 行目に到達しても、 $1$ 行目をブロックで埋めることは不可能である

ABC391D.cpp

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

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

    vector<set<pair<int, int>>> G(w, set<pair<int, int>>());
    int x, y;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        x--;
        y--;
        G[x].emplace(y, i);
    }

    vector<vector<pair<int, int>>> V(n, vector<pair<int, int>>());
    for(int i=0; i<w; i++){
        if(G[i].size()==0){
            continue;
        }
        int cnt = 0;
        for(auto [ny, num] : G[i]){
            V[cnt].emplace_back(ny, num);
            cnt++;
        }
    }

    vector<int> ans(n, -1);
    for(int i=0; i<n; i++){
        if(V[i].size()==w){
            auto [maxv, num] = *max_element(V[i].begin(), V[i].end());

            for(auto [ny, num] : V[i]){
                ans[num] = 1 + maxv;
            }
        }else{
          break;
        }
    }

    int q;
    cin >> q;
    int t, a;
    for(int i=0; i<q; i++){
        cin >> t >> a;
        a--;
        if(ans[a]>t || ans[a]==-1){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
    }

    return 0;
}