【ABC351】AtCoder Beginner Contest 351【C++】

コンテスト名

AtCoder Beginner Contest 351

コンテストURL

開催日

2024/04/27 21:00-22:40

---

A: The bottom of the ninth

解法

• $A_i$ の合計から $B_i$ の合計を引いた値に 1 を足した得点が必要

ABC351A.cpp

#include <iostream>
using namespace std;

int main(){
    int asum = 0, bsum = 0;
    int a, b;
    for(int i=0; i<9; i++){
        cin >> a;
        asum += a;
    }
    for(int i=0; i<8; i++){
        cin >> b;
        bsum += b;
    }

    cout << asum - bsum + 1 << endl;
    return 0;
}

B: Spot the Difference

解法

• 全探索する
• 文字が異なる箇所が見つかれば出力して終了

ABC351B.cpp

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

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

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

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(A[i][j]!=B[i][j]){
                cout << i+1 << " " << j+1 << endl;
                return 0;
            }
        }
    }
}

C: Merge the balls

解法

• 問題文通りにシミュレーションする
• スタックを使う
  • 指数を vector<int> で管理する
• $2^k + 2^k = 2^{k + 1}$ に注意する
• A.back() で最後の値、 A.end()[-2] で最後から 2 番目の値を取得できる

ABC351C.cpp

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

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

    vector<int> A;
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        A.push_back(a);
        while(true){
            if(A.size()<=1){
                break;
            }

            int back1 = A.back(), back2 = A.end()[-2];

            if(back1!=back2){
                break;
            }

            if(back1==back2){
                A.pop_back();
                A.pop_back();
                A.push_back(back1 + 1);
            }
        }

    }

    cout << A.size() << endl;
    return 0;
}

D: Grid and Magnet

解法

• 幅優先探索 (BFS)
• まだ到達したことがない各頂点から幅優先探索してそれぞれの「自由度」を求める
  • 上下左右に隣り合うマスのいずれかに磁石があるマスに到達したら探索終了
• 上下左右に隣り合うマスのいずれにも磁石がないマスについて、マス $x$ からマス $y$ に移動できるのであれば、マス $x$ とマス $y$ の「自由度」は等しい
  • マス $x$ 始まりとマス $y$ 始まりを両方調べる必要はない
• 上下左右に隣り合うマスのいずれかに磁石があるマスについては当該マス始まりも含めて最大で 4 回探索される可能性がある
  • 上下左右に隣り合うマスのいずれかに磁石があるマスに入ることはできるが出ることはできないため複数回探索される可能性がある
• 全体で到達したことがあるかどうかを記録する配列と各探索（各頂点始まりの探索）において到達したことがあるかどうかを記録する配列を一つにまとめる
  • 別々の配列を使うと TLE する
  • 各マスに番号が振られていると考えてどのマス始まりの探索で到達したかを vector<int> に記録する
  • 各マスの番号は $i × W + j + 1$

ABC351D.cpp

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

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

    vector<vector<char>> G(h, vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> G[i][j];
        }
    }

    int maxv = 0;
    vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    vector<int> seen(h*w+1, -1);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(G[i][j]=='#' || seen[i*w+j+1]!=-1){
                continue;
            }
            
            int cnt = 1;
            queue<pair<int, int>> Q;
            seen[i*w+j+1] = i*w+j+1;
            Q.emplace(i, j);
            while(!Q.empty()){
                auto [x, y] = Q.front();
                Q.pop();

                bool flag = true;
                for(int k=0; k<4; k++){
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(nx<0 || nx>h-1 || ny<0 || ny>w-1){
                        continue;
                    }

                    if(G[nx][ny]=='#'){
                        flag = false;
                    }
                }

                if(flag){
                    for(int k=0; k<4; k++){
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if(nx<0 || nx>h-1 || ny<0 || ny>w-1){
                            continue;
                        }
                        if(seen[nx*w+ny+1]==i*w+j+1){
                            continue;
                        }

                        cnt++;
                        seen[nx*w+ny+1] = i*w+j+1;
                        Q.emplace(nx, ny);
                    }
                }
            }

            maxv = max(maxv, cnt);
        }
    }

    cout << maxv << endl;
    return 0;
}