AtCoder Beginner Contest 302

## [A - Attack](https://atcoder.jp/contests/abc302/tasks/abc302_a)

O(1)

下記は除算の切り上げです。
多くの場面で使うので覚えましょう。

```
(A+B-1) / B
```

```C++:C++
#include <bits/stdc++.h>
 
#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() {
    ll A, B;
    cin >> A >> B;
    cout << (A+B-1) / B << endl;
    return 0;
} 
```

## [B - Find snuke](https://atcoder.jp/contests/abc302/tasks/abc302_b)

O(H*W*8*5)

実装問題です。
複雑な実装問題は、自分が認識できる分だけ分割していきましょう。
今回は問題文を読み以下に分割しました。

・H*Wのループをして全てのマスを探索する
・H*Wのループをして探索したマスに対して、１マスの探索毎に８方向の探索を行う
・８方向の探索は、１方向毎に５マスの探索を行い”｀snuke”の文字列になっているかチェックを行う

```C++:C++
#include <bits/stdc++.h>
 
#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[8] = {-1,  0,  1, -1, 1, -1, 0, 1};
int dy[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
string snuke = "snuke";
int H, W;
vector<string> S;

// snukeかチェックする
int checkSnuke(int w, int h, int cnt, int ddx, int ddy){
    int x = w;
    int y = h;
    for(int i=0; i<5; i++){
        if(x<0 || W <= x || y<0 || H <= y){
            return 0;
        }
        if(S[y][x] == snuke[cnt]){
            cnt++;
            x+=ddx;
            y+=ddy;
        }else{
            return 0;
        }
    }
    return 1;
}

int main() {
    cin >> H >> W;

    S.resize(H);
    rep(i, H) cin >> S[i];

　　　　　　　　// H*Wのループ
    for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
　　　　　　　　　　　　　　　　　　　　　　　　　// 8方向のループ
            for(int i=0; i<8; i++){
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// snukeかチェックする
                if(checkSnuke(w, h, 0, dx[i], dy[i])){
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// output
                    int ddx = w+1;
                    int ddy = h+1;
                    for(int j=0; j<5; j++){
                        cout << ddy << ' ' << ddx << endl;
                        ddx = ddx + dx[i];
                        ddy = ddy + dy[i];
                    }   
                }
            }
        }
    }
    return 0;
} 
```

## [C - Almost Equal](https://atcoder.jp/contests/abc302/tasks/abc302_c)

O(N!*M)
順列の全探索の問題です。
N<=8の制約はbit全探索か順列全探索と覚えてしまって良いです。

C++が有利な問題ですね。
next_permutationを使用することで簡単に解答できます。

```C++:C++
#include <bits/stdc++.h>
 
#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 N, M;
int check(string S, string T){
    int cnt=0;
    rep(i, M){
        if(S[i] != T[i]) cnt++;
    }
    return cnt;
}

int main() {
    
    cin >> N >> M;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
    sort(S.begin(), S.end());

    do {
        int ok=1;
        for(int i=0; i<N-1; i++){
            if(check(S[i], S[i+1]) != 1){
                ok = 0;
                break;
            }
        }
        if(ok){
            cout << "Yes" << endl;
            return 0;
        }
    } while (next_permutation(S.begin(), S.end()));

    cout << "No" << endl;

    return 0;
} 
```

## [D - Impartial Gift](https://atcoder.jp/contests/abc302/tasks/abc302_d)

O(N*logM)
片方の値を固定して、もう片方の値を計測する問題です。
今回は二分探索を使用しました。
二分探索なので、A,Bを前処理でソートしましょう。
Aを固定し、Bを二分探索します。
久しぶりに実装したのでバグを生み、時間内に解答できなかったです。

```C++:C++
#include <bits/stdc++.h>
 
#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() {
    ll N, M, D;
    cin >> N >> M >> D;
    vector<ll> A(N), B(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if((N==0)||(M==0)){
        cout<<-1<<endl;
        return 0;
	}

    ll ans=-1;
    rep(i, N){
        ll ok=0;
        ll ng=M;
        while (ng - ok>-1)
        {
            ll mid = (ok+ng) / 2;
            if(abs(A[i] - B[mid]) <= D){
                ans = max(ans, A[i] + B[mid]);   
            }
            if(A[i]+D < B[mid]) ng = mid-1;
            else ok = mid+1;
        }
    }
    cout << ans << endl;
    return 0;
} 
```