【ABC378】AtCoder Beginner Contest 378【C++】

コンテスト名

AtCoder Beginner Contest 378

コンテストURL

開催日

2024/11/02 21:00-22:40

---

A: Pairing

解法

• 各色のボールの個数を記録する
• 2 で割った商の数だけ操作できる

ABC378A.cpp

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

int main(){
    int a;
    vector<int> A(4);
    for(int i=0; i<4; i++){
        cin >> a;
        a--;
        A[a]++;
    }

    int cnt = 0;
    for(int i=0; i<4; i++){
        cnt += A[i]/2;
    }

    cout << cnt << endl;

    return 0;
}

B: Garbage Collection

解法

• $d_j$ を $q_{t_j}$ で割った余りと $r_{t_j}$ の大小で場合分けする

ABC378B.cpp

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

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

    vector<int> Q(n), R(n);
    for(int i=0; i<n; i++){
        cin >> Q[i] >> R[i];
    }

    int q;
    cin >> q;
    int t, d;
    for(int i=0; i<q; i++){
        cin >> t >> d;
        t--;
        if(d%Q[t]<=R[t]){
            cout << d + R[t] - d%Q[t] << '\n';
        }else{
            cout << Q[t]*(d/Q[t]+1) + R[t] << '\n';
        }
    }

    return 0;
}

C: Repeating

解法

• 各数字が最後に出現した位置を map<int, int> に記録しておき、順番に更新する

ABC378C.cpp

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

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

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

    map<int, int> M;
    vector<int> B(n);
    for(int i=0; i<n; i++){
        if(!M.count(A[i])){
            B[i] = -1;
            M[A[i]] = i + 1;
        }else{
            B[i] = M[A[i]];
            M[A[i]] = i + 1;
        }
    }

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

    return 0;
}

D: Count Simple Paths

解法

• 深さ優先探索 (DFS)

ABC378D.cpp

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

int h, w, k;
vector<vector<char>> S;
int ans = 0;
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vector<vector<int>> seen;

void dfs(int x, int y, int cnt){
    if(cnt==k){
        ans++;
        return;
    }

    for(int i=0; i<4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx<0 || nx>=h || ny<0 || ny>=w){
            continue;
        }
        if(S[nx][ny]=='#'){
            continue;
        }
        if(seen[nx][ny]){
            continue;
        }
        
        seen[nx][ny] = 1;
        dfs(nx, ny, cnt+1);
        seen[nx][ny] = 0;
    }
}

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

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

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(S[i][j]=='#'){
                continue;
            }
            seen[i][j] = 1;
            dfs(i, j, 0);
            seen[i][j] = 0;
        }
    }

    cout << ans << endl;
    
    return 0;
}