AtCoder Beginner Contest 406

## A - Not Acceptable
[問題文](https://atcoder.jp/contests/abc406/tasks/abc406_a)

O(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 a, b, c, d;
    cin >> a >> b >> c >> d;

    if(a * 60 + b > c * 60 + d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 
```

## B - Product Calculator
[問題文](https://atcoder.jp/contests/abc406/tasks/abc406_b)

O(N)
ループ文とオーバーフローの問題です。
下記のコードはオーバーフローしてWAになります。
コンテスト中は解決策が思いつかなかったので回避策を取りました。

```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, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll ans = 1;
    rep(i, N){
        ans *= A[i];
        if(ans >= mod) ans=1;
    }
    cout << ans << endl;
    return 0;
} 
```

pyhotnは整数のbit数を気にしなくて良いです。

```python
import sys
import math
import heapq
import itertools
import numpy as np
from collections import deque
from functools import reduce
from string import ascii_lowercase

# main
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    mod = 1
    for i in range(0, K):
        mod *= 10

    ans = 1
    for i in range(0, N):
        ans *= A[i]
        if(ans >= mod):
          ans=1
    
    print(ans)

# エントリポイント
if __name__ == '__main__':
    main()
```

正攻法の解決策ではないです。
しっかり勉強しないとCやD問題で詰むようになります。
正攻法を考察しましょう。
オーバーフローをしないように掛け算を割り算に変更します。

```math
a_i * x >= m
```

を

```math
a_i >= m / x
```

にするとWAになります。
これはなぜでしょうか。下記のサンプル入力で詳しく考察していきます。

```
2 1
3 3
```

の時、計算式は、

```math
3 * 3 >= 10
```

両辺を3で割ります。

```math
3 >= 10 / 3 
```

端数の少数部分は切り捨て、

```math
3 >= 3
```

if文の判定式はtrueになります。
これでは`x = 1`となりWAになってしまいます。
本来なら、

```math
3 >= 3.33333....
```

`3`は`3.333.....`より小さいのでfalseになります。
整数型の割り算、仕様の問題ですね。
`>=`は少数部分、切り捨ての値を考慮しない不等式だと分かります。
それでは`>`を使用しましょう。

```math
a_i * x > (m-1)
```

`>`なので`m`未満の最大の整数である`m-1`を使用します。
これを先ほどのサンプル入力で考察しましょう。

```math
3 * 3 > 10 - 1 
```

```math
3 > (10 - 1 ) / 3
```

```math
3 > 3
```

`3`は`3`より大きくないのでfalseになります。
`>`は少数部分の切り捨てを考慮できる不等式ですね。

```math
a_i > (m-1) / x
```

が答えになります。
コーディングしましょう。

```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, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll x = 1;
    rep(i, N){
        if(A[i] > (mod-1) / x) x=1;
        else x *= A[i];
    }
    cout << x << endl;
    return 0;
} 
```

ACできました。
さらに`>=`の不等式を使用する方法はないのか。
そこも考察していきましょう。
少数部分の切り捨てが問題です。
 `m / A[i]`の計算時に1以上の余りが存在するなら切り上げの処理を行いましょう。

 ```math
 a_i * x >= m
 ```
 
 ```math
 x >= (m + A[i] - 1) / A[i]
 ```

 `A[i] - 1`を加算しているので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() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll mod = 1;
    rep(i, K) mod *= 10;
    ll x = 1;
    rep(i, N){
        if(x >= (mod+A[i]-1)/A[i]) x=1;
        else x *= A[i];
    }
    cout << x << endl;
    return 0;
} 
```

ACになりました。
`>=`は式の変更時、割り算なら切り上げの処理を実装する。
`>`は式の変更時、割り算なら切り捨てを考慮しているのでそのまま処理を実装する。
これで式を変更する際に、割り算で発生する少数部分を考慮してプログラミングを組む事ができるようになりました。

## C - ~

[問題文](https://atcoder.jp/contests/abc406/tasks/abc406_c)

ランレングス圧縮の問題です。
私はコンテスト中、尺取法に見えて沼りました。
この問題は問題文を理解するのが難しい問題です。

```math
A_{i-1} < A_i > A_{i+1}
```

と

```math
A_{i-1} > A_i < A_{i+1}
```

の並びを一つずつ含む数列Pを求めます。
サンプル1で考察しましょう。

```
6
1 3 6 4 2 5
```

の場合、

```
3 6 4 2 5
1 3 6 4 2 5
```

の２つの数列が答えになります。
次にサンプル3を見ましょう。

```
12
11 3 8 9 5 2 10 4 1 6 12 7
```

下記のパターンを数列Pとして良いか。

```
11 3 8 9 5
```

答えは❌です。条件に、

```math
A_1 < A_2
```

とあります。
数列Pは＜の不等号から始まらなければいけません。

```
3 8 9 5 2 10
8 9 5 2 10
2 10 4 1 6
2 10 4 1 6 12
```

の４つのパターンになりました。
４つのパターンを見ると数列Pは以下のように値が増減しています。

![名称未設定.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/626801/06615193-e525-44d4-97bc-83606685710f.png)

ランレングス圧縮を行います。
数列Pの不等号が`>`の時を基準にして、左右の辺の長さを掛け算した値の合計を求めると良さそうです。
考察ができました。

```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;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    vector<int> d;
    rep(i, n-1){
        d.push_back((p[i]<p[i+1]? 0:1));
    }

    vector<P> rle;
    for(auto x:d){
        if(rle.size() && rle.back().first == x) rle.back().second++;
        else rle.push_back({x, 1});
    }

    ll ans = 0;
    rep(i, rle.size()){
        if(rle[i].first == 1){
            ll l = 0, r = 0;
            if(0<i) l = rle[i-1].second;
            if(i+1<rle.size()) r = rle[i+1].second;
            ans += l*r;
        }
    }
    cout << ans << endl;
    return 0;
} 
```

## D - Garbage Removal
[問題文](https://atcoder.jp/contests/abc406/tasks/abc406_d)

過去に類題がありますね。
もちろん予習済みです。

### 例題
[D - Cross Explosion](https://atcoder.jp/contests/abc370/tasks/abc370_d)
[D - Lamp](https://atcoder.jp/contests/abc129/tasks/abc129_d)

ごみ（x, y）のデータを、各軸ごとに保持をします。
x, y軸を基準したデータ構造を用意します。
`vector<set<int>>`h(H), w(W)が分かりやすです。

queryが`1`の時、`x`行目の要素を削除します。
`h[x].clear()`で全て削除できます。
しかし`w`のデータを、`h`より先に削除しないといけません。

```C++:C++
            for(auto y:h[x]){
                w[y].erase(x);
            }
            h[x].clear();
```

`h[x]`から列`y`の値を取り出します。
`y`列目に`x`の値の要素があるので、`w[y].erase(x);`で要素を削除します。

queryが`2`の時も`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 H, W, N, Q;
    cin >> H >> W >> N;
    vector<set<int>> h(H), w(W);
    rep(i, N){
        int x, y;
        cin >> x >> y;
        x--; y--;
        h[x].insert(y);
        w[y].insert(x);
    }
    cin >> Q;
    for(int i=0; i<Q; i++){
        int q;
        cin >> q;

        if(q==1){
            int x;
            cin >> x;
            x--;
            cout << h[x].size() << endl;

            for(auto y:h[x]){
                w[y].erase(x);
            }
            h[x].clear();
        }   

        if(q==2){
            int y;
            cin >> y;
            y--;
            cout << w[y].size() << endl;
            for(auto x:w[y]){
                h[x].erase(y);
            }
            w[y].clear();
        }   

    }

    return 0;
} 
```