AtCoder Beginner Contest 221

##[A - Seismic magnitude scales](https://atcoder.jp/contests/abc221/tasks/abc221_a)

O(1)
powの戻り値はint型ではないです。
そこに気をつけてください。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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;

    ll res=1;
    for(ll i=min(A, B); i<max(A, B); i++){
        res = res * 32;
    }
    cout << res << endl;
    
    return 0;
}
```

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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;
    cin >> A >> B;
 
    cout << (int)pow(32, max(A, B) - min(A, B)) << endl;
 
    return 0;
}
```

##[B - typo](https://atcoder.jp/contests/abc221/tasks/abc221_b)

O(N)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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() {
    string S, T;
    cin >> S >> T;

    if(S == T){
        cout << "Yes" << endl;
        return 0;
    }

    int n = S.size();
    for(int i=0; i<n; i++){
        if(S[i] != T[i]){
            string C = S;
            if(i-1>=0){
                swap(C[i], C[i-1]);
                if(C == T){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
            
            C = S;
            if(i+1<n){
                swap(C[i], C[i+1]);
                if(C == T){
                    cout << "Yes" << endl;
                    return 0;
                }
            }           
        }
    }

    cout << "No" << endl;

    return 0;
}
```

##[C - Select Mul](https://atcoder.jp/contests/abc221/tasks/abc221_c)

O(N!)
順列全探索かbit全探索で解きます。
１０桁の数字を並び替えます。
その数字を２つに分けて積を求めます。
積の最大値が解答です。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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() {
    string N;
    cin >> N;
    sort(N.begin(), N.end());

    int res=0;
    do {
        for(int i=1; i<N.size(); i++){
            string t = N.substr(0, i);
            string u = N.substr(i, N.size()-i);
            if(t[0] == '0' || u[0] == '0') continue;

            res = max(res, atoi(t.c_str()) * atoi(u.c_str()) );
        }

    } while (next_permutation(N.begin(), N.end()));

    cout << res << endl;

    return 0;
}
```

##[D - Online games](https://atcoder.jp/contests/abc221/tasks/abc221_d)

O(N)
累積和、imos法思い浮かべると10^9の配列が用意できないです。
このパターンはイベントソートになります。

人数が増える日、人数が減る日をデータ構造で保持します。
その後、日付を基準にソートをします。
何日から何日までこの人数がログインしていると計算できます。
それを人数をキーにしてデータ構造に保持をします。

最後に0人を除いて出力を行います。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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<ll,ll>;
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;

    map<ll, ll> mp;
    rep(i, N){
        ll a, b;
        cin >> a >> b;
        mp[a] += 1;
        mp[a+b] += -1;
    }

    ll s=0, t=0;
    vector<ll> vec(N+1);
    for(auto m:mp){
        ll p = m.first - s;
        vec[t] += p;
        s = m.first;
        t += m.second;
    }

    for(int i=1; i<vec.size(); i++){
        cout << vec[i];
        if(i != vec.size()-1) cout << " ";
    }

    return 0;
}
```