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

### コンテスト名
AtCoder Beginner Contest 378

### コンテストURL
https://atcoder.jp/contests/abc378

### 開催日
2024/11/02 21:00-22:40

---

## [A: Pairing](https://atcoder.jp/contests/abc378/tasks/abc378_a)
**解法**
- 各色のボールの個数を記録する
- 2 で割った商の数だけ操作できる
```cpp: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](https://atcoder.jp/contests/abc378/tasks/abc378_b)
**解法**
- $d_j$ を $q_{t_j}$ で割った余りと $r_{t_j}$ の大小で場合分けする
```cpp: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](https://atcoder.jp/contests/abc378/tasks/abc378_c)
**解法**
- 各数字が最後に出現した位置を `map<int, int>` に記録しておき、順番に更新する
```cpp: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](https://atcoder.jp/contests/abc378/tasks/abc378_d)
**解法**
- 深さ優先探索 (DFS)
```cpp: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;
}
```