AtCoder Beginner Contest 400

## [A - ABC400 Party](https://atcoder.jp/contests/abc400/tasks/abc400_a)

O(1)
数学の問題です。

```math
A * B = 400
```

が成立しているか確認します。
この問題ではAが与えられるのでBと余りを求めます。

```math
B = 400 / A
```

```math
400 / A = x 余り 0
```

考察が終わりました。

```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 A;
    cin >> A;

    if(400 % A == 0){
        cout << 400 / A << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
} 
```

## [B - Sum of Geometric Series](https://atcoder.jp/contests/abc400/tasks/abc400_b)

O(M*M!)
i=0からMの回数だけループをします。
ansに`N^i`を加算していきます。
`N＝2`、`M＝５`の時、

```
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
```

合計は、

```
1 + 2 + 4 + 8 + 16 + 32 = 63
```

int型だとオーバーフローを起こします。
ループ内で最初に`10^9`を超えるタイミングで、終了処理をします。
全ての計算が終わった後だと、オーバーフローしていてif文の分岐処理が上手くいかないからです。

```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() {
    ll N, M;
    cin >> N >> M;

    const ll inf = 1e9;
    ll ans = 0;
    for(ll i=0; i<=M; i++){
        ll x = 1;
        for(int j=0; j<i; j++) x *= N;
        ans += x;
        if(ans > inf){
            cout << "inf" << endl;
            return 0;
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - 2^a b^2](https://atcoder.jp/contests/abc400/tasks/abc400_c)

AtCoderの公式の解説の手法だと、計算量はO(1)になります。

私が理解できた手法の計算量は、O(60^2)です。
数学の問題です。
計算式を理解することが大事です。

```math
2^a * b^2 <= N
```

である整数(a, b)の組み合わせの数を求める。
`N=10^18`の時、`2^a`だけを見て`10^18`以下になるパターンは、`2^0`から`2^60`までである。
これはlong long型が64bitであることから考察できます。

```math
x = N / 2 ^ a
```

```math
b = \sqrt{x}
```

の時、`1`から`b`までの値を撮ります。
次は値が重複するパターンを考えましょう。

```
a = 2
b = 2
2 ^ a * b ^ 2 = 2 * 2 * 2 * 2
```

`a=4`、`b=1`の時と重複しています。

```
a = 2
b = 6
2 ^ a * b ^ 2 = 2 * 2 * 6 * 6 = 2 * 2 * 2 * 3 * 2 * 3
```

`a=4`、`b=3`の時と重複しています。

```
a = 2
b = 5
2 ^ a * b ^ 2 = 2 * 2 * 5 * 5
```

重複するパターンが存在しません。
約数を見ていくと分かりますが、`b`が奇数の時だけ探索すると答えになります。

```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() {
    ll N;
    cin >> N;

    ll ans = 0;
    for(ll a=1; a<61; a++){
        ll x = N;
        for(int i=0; i<a; i++) x /= 2;
        ll b = sqrtl(x);
        ans += (b + 1) / 2;
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Takahashi the Wall Breaker](https://atcoder.jp/contests/abc400/tasks/abc400_d)

O(HW)
01BFSの問題です。
ゴールまでの最短経路ではなく、ゴールまでの壁を破壊した最小の数を求めます。

最短経路だとpush_frontができないです。
壁を壊さなくて良い経路を優先的に処理したいので、push_frontで格納します。
壁を壊した経路を後で処理したいので、push_backで格納します。

壁を破壊した数を2次元配列distに格納します。
`.`の時に、

```
dist[yy][xx] = dist[y][x]
```

`#`の時に、

```
dist[yy][xx] = dist[y][x] + 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 dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void solive(int H, int W, vector<string>& S, int A, int B, int C, int D){
    A--; B--; C--; D--;

    deque<pair<int, int>> deq;
    deq.emplace_back(A, B);
    vector<vector<int>> dist(H, vector<int>(W, 1e9));
    dist[A][B] = 0;
    vector<vector<bool>> used(H, vector<bool>(W, false));

    while(deq.size()){
        auto [y, x] = deq.front();
        deq.pop_front();

        if(used[y][x]) continue;
        used[y][x] = true;

        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(dist[yy][xx] <= dist[y][x]) continue;

            if(S[yy][xx] == '.'){
                dist[yy][xx] = dist[y][x];
                deq.emplace_front(yy, xx);
            }
        }

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

                if(xx<0 || W<=xx || yy<0 || H<=yy) continue;
                if(dist[yy][xx] <= dist[y][x]) continue;

                dist[yy][xx] = dist[y][x]+1;
                deq.emplace_back(yy, xx);
            }
        }
    }
    cout << dist[C][D] << endl;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    solive(H, W, S, A, B, C, D);

    return 0;
} 
```