AtCoder Beginner Contest 383

## [A - Humidifier 1](https://atcoder.jp/contests/abc383/tasks/abc383_a)

O(N)
シミュレートします。

追加する水`Vi`
経過時間を`T[i] - T[i-1]`
加湿器の水は0未満にならないので

```math
ans = V[i] + max(0, ans - (T[i] - T[i-1]));
```

となります。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    vector<int> T(N), V(N);
    rep(i, N) cin >> T[i] >> V[i];

    int ans = V[0];
    repx(i, 1, N){
        ans = V[i] + max(0, ans - (T[i] - T[i-1]));
    }
    cout << ans << endl;

    return 0;
} 
```

## [B - Humidifier 2](https://atcoder.jp/contests/abc383/tasks/abc383_b)

O(HW * HW * HW)
全探索です。
値が小さいのでO(N^3)でも間に合います。

1. 加湿器を置く2マスを全探索します
2. 1のループ内で、加湿器を置く2マスと他のマスの距離を探索します
3. 2で探索したマスの距離がD以下ならカウントを加算します
4. 3の最大値が答えになります

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 H, W, D;
    cin >> H >> W >> D;
    string S[10];
    rep(i, H) cin >> S[i];

    int ans = 0;
    rep(y1, H) rep(x1, W){
        if(S[y1][x1] == '#') continue;
        rep(y2, H) rep(x2, W){
            if(S[y2][x2] == '#') continue;
            if(y1==y2 && x1==x2) continue;
            int cnt=0;
            rep(i, H) rep(j, W){
                if(S[i][j] == '#') continue;
                bool ok = false;
                if(abs(y1 - i) + abs(x1 - j) <= D) ok=true;
                if(abs(y2 - i) + abs(x2 - j) <= D) ok=true;
                if(ok) cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - Humidifier 3](https://atcoder.jp/contests/abc383/tasks/abc383_c)

O(HW)
bfsです。
通常のbfsを異なるのは多始点bfsと呼ばれる、始点が複数あるタイプのbfsです。
最初にHのある座標をqueueに全て格納します。
Hからの距離を探索して答えを出します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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; }

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int main() {
    int H, W, D;
    cin >> H >> W >> D;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    const int INF = 100100100;
    vector<vector<int>> dist(H, vector<int>(W, INF));

    queue<P> que;
    rep(y, H) rep(x, W){
        if(S[y][x] == 'H'){
            dist[y][x] = 0;
            que.push({x, y});
        }
    }

    while(que.size()){
        auto [x, y] = que.front();
        que.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || W<=nx || ny<0 || H<=ny) continue;
            if(S[ny][nx] == '#') continue;
            if(dist[ny][nx] != INF) continue;            
            dist[ny][nx] = dist[y][x] + 1;
            que.push({nx, ny});
        }
    }

    int ans = 0;
    rep(y, H) rep(x, W) if(dist[y][x] <= D) ans++;
    cout << ans << endl;

    return 0;
} 
```

## [D - 9 Divisors](https://atcoder.jp/contests/abc383/tasks/abc383_d)

O(N)
エラトステネスの篩の問題です。

「正の約数をちょうど9個持つものの個数」を求めます。
正の約数の数の求め方を考えます。
高校数学Aの単元です。
120を素因数分解すると、

```math
2^3 * 3^1 * 5^1
```

それぞれの因数に1を加算した値の積が120の約数の数になります。

```math
4 * 2 * 2 = 16
```

16個であっていますね。
次に約数が9個の場合を変数で考えましょう。
p, qを素数とした時に、

```math
p ^ 2 * q ^ 2の時、((2 + 1) * (2 + 1) = 9)
```
```math
p ^ 8の時、(8 + 1 = 9)
```

素数をエラトステネスの篩で求めます。

```math
2 * 2 * 10^6 * 10^6
```

のパターンを考慮し、エラトステネスの篩で使用する配列は10^6ほど必要です。
求めた素数を使用して、

```math
p ^ 2 * q ^ 2 <= N
```
```math
p ^ 8 <= N
```

を判定して探索すると、答えを求めることができます。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 INF = 1001001;
    bool isPrime[INF];
    for(int i=0; i<INF; i++) isPrime[i] = true;
    for(ll i=2; i*i<INF; i++){
        if(isPrime[i] == false) continue;
        for(ll j=i; j*i<INF; j++){
            isPrime[j*i] = false;
        }
    }

    vector<ll> primes;
    for(int i=2; i<INF; i++){
        if(isPrime[i]) primes.push_back(i);
    }

    ll cnt = 0;
    for(auto p1:primes){
        for(auto p2:primes){
            if(p1 <= p2) break;
            if(p1 * p1 * p2 * p2 > N) break;
            //cout << p1 * p1 * p2 * p2 << endl;
            cnt++;
        }
    }

    for(auto p:primes){
        ll x = 1;
        rep(i, 8) x *= p;
        if(x > N) break;
        //cout << x << endl;
        cnt++;
    }

    cout << cnt << endl;

    return 0;
} 
```