AtCoder Beginner Contest 378

## [A - Pairing](https://atcoder.jp/contests/abc378/tasks/abc378_a)

O(N)

```
ans += 各数字が出現した回数 / 2
```

データ構造の問題です。
mapを使用しましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N = 4;
    map<int, int> mp;
    rep(i, N){
        int a;
        cin >> a;
        mp[a]++;
    }
    int ans = 0;
    for(auto m:mp){
        ans += m.second / 2;
    }
    cout << ans << endl;

    return 0;
} 
```

## [B - Garbage Collection](https://atcoder.jp/contests/abc378/tasks/abc378_b)

O(N)
N種類のゴミを何日に回収するかという問題です。

```math
d_i / q_{t_i} = x + a
```

とした時に、

(a <= r_i の時) 

```math
d_i - a + r_i
```
(a > r_i の時) 

```math
d_i - a + q_{t_i} + r_i
```

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, Q;
    cin >> N;
    vector<int> q(N), r(N);
    rep(i, N) cin >> q[i] >> r[i];
    cin >> Q;
    vector<int> t(Q), d(Q);
    rep(i, Q) cin >> t[i] >> d[i];

    rep(i, Q){
        int index = t[i] - 1;
        int a = d[i] % q[index];
        if(a <= r[index]){
            cout << d[i] - a + r[index] << endl;
        }else{
            cout << d[i] - a + q[index] + r[index] << endl;
        }
    }

    return 0;
} 
```

## [C - Repeating](https://atcoder.jp/contests/abc378/tasks/abc378_c)

O(N)
データ構造の問題です。
mapでキーをA_i、値をindexにして保持します。
mapにキーが存在するならmap[A_i]を出力、値を更新。
mapにキーが存在しないなら-1を出力、値を更新。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    map<int, int> mp;
    rep(i, N){
        int a;
        cin >> a;
        if(mp.find(a) != mp.end()){
            cout << mp[a] << endl;
            mp[a] = i+1;
        }else{
            cout << -1 << endl;
            mp[a] = i+1;           
        }
    }

    return 0;
} 
```

## [D - Count Simple Paths](https://atcoder.jp/contests/abc378/tasks/abc378_d)

O(4*3^10)
dfsの問題です。
経路の組み合わせを探索するのはdfsです。

進行方向を考察します。
最初は4方向、その後は3方向に移動できます。
よって、4*3^10=236196の計算量になります。

bfsだと、
「ある空きマスを出発し、上下左右に隣接するマスへの移動をK回行う方法であって、障害物のあるマスを通らず、同じマスを2回以上通らないようなものの個数を数えてください。」
の条件で、経路の組み合わせを探索するのに適さないです。

考察が終わりました。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int H, W, K, ans;
vector<string> S;
int graph[10][10];

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

    for(int i=0; i<4; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];

        if(xx<0 || W<=xx || yy<0 || H<=yy) continue;
        if(graph[yy][xx]) continue;
        if(S[yy][xx] == '#') continue;

        graph[yy][xx] = true;
        dfs(xx, yy, cnt+1);
        graph[yy][xx] = false;
    }
}

int main() {
    
    cin >> H >> W >> K;
    S.resize(H);
    rep(i, H) cin >> S[i];

    rep(y, H){
        rep(x, W){
            if(S[y][x] == '#') continue;
            graph[y][x] = true;
            dfs(x, y, 0);
            graph[y][x] = false;
        }
    }
    cout << ans << endl;

    return 0;
} 
```