AtCoder Beginner Contest 390

## [A - 12435](https://atcoder.jp/contests/abc390/tasks/abc390_a)

O(N^2)
ソートの回数を探索しましょう。
ソートの回数が1の時、`Yes`です。

```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 = 5;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int cnt = 0;
    rep(i, n) for(int j=i+1; j<n; j++){
        if(a[i] > a[j]){
            swap(a[i], a[j]);
            cnt++;
        }
    }
    if(cnt==1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
} 
```

O(N)で回答することができます。
要素を一回だけ入れ替えた時、`vector<int>({1, 2, 3, 4, 5})`と等しいか判定します。

```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 = 5;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n){
        swap(a[i], a[i+1]);
        if(a == vector<int>({1, 2, 3, 4, 5})){
            cout << "Yes"<< endl;
            return 0;
        }
        swap(a[i], a[i+1]);
    }
    cout << "No" << endl;
    return 0;
} 
```

コンテスト中にこのようなコードが書けるようになりたいです。

## [B - Geometric Sequence](https://atcoder.jp/contests/abc390/tasks/abc390_b)

O(N)
配列Aが等比数列か判定します。
等比数列の条件は、

```math
a_{i+1} / a_i = a_{i+2} / a_{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<long double> a(n);
    rep(i, n) cin >> a[i];

    if(n==2){
        cout << "Yes" << endl;
        return 0;
    }

    long double r = a[1] / a[0];

    for(int i=0; i<n-1; i++){
        if(r != a[i+1] / a[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
} 
```

もう少し考察をしましょう。
判定を整数で行うことができます。

```math
a_{i+1} / a_i = a_{i+2} / a_{i+1}
```

を

```math
a_{i+1} * a_{i+1} = a_{i+2} * a_{i}
```

と式を変形します。

```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<long double> a(n);
    rep(i, n) cin >> a[i];
    for(int i=0; i<n-2; i++){
        if(a[i+1] * a[i+1] != a[i+2] * a[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
} 
```

コンテスト中にこのようなコードが書けるようになりたいです。

## [C - Paint to make a rectangle](https://atcoder.jp/contests/abc390/tasks/abc390_c)

O(N)
`#`であるマスの最小のx, yを探索。
`#`であるマスの最大のx, yを探索。
範囲内のマスが`#`, `?`なら、黒マス全体が長方形である条件を満たしています。

```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;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int max_x = 0;
    int max_y = 0;
    int min_x = w;
    int min_y = h;

    rep(i, h) rep(j, w){
        if(s[i][j] == '#'){
            max_x = max(max_x, j);
            max_y = max(max_y, i);
            min_x = min(min_x, j);
            min_y = min(min_y, i);
        }
    }

    rep(i, h) rep(j, w){
        if(min_x <= j && j <= max_x && min_y <= i && i <= max_y){
            if(s[i][j] == '.'){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;

    return 0;
} 
```

## [D - Stone XOR](https://atcoder.jp/contests/abc390/tasks/abc390_d)

O(N!)
dfsの全探索の問題です。
同じ袋に入れるA_iの要素を探索してグループ分けする問題です。
サンプル1を考察します。

```
3
2 5 7
```

は、

```
2 5 7
0 7 7
0 5 9
2 0 12
0 0 14
```

とパターン分けができます。
この処理を実装できるかが問題の鍵になります。

コンテスト中にTLEとなったコードを書きます。
グループ分けの手法が誤っています。
n=12の時、O(13^12)となっています。

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

set<ll> st;

void dfs(vector<ll> &A, int index){

    int n = A.size();

    if(index >= n){
        ll sum = 0;
        rep(i, n) sum ^= A[i];
        return;
    }

    dfs(A, index+1);

    ll t = A[index];
    A[index] = 0;
    for(int i=index+1; i<n; i++){
        A[i] += t;
        dfs(A, index+1);
        A[i] -= t;
    }
    A[index] = t;
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    dfs(A, 0);
    cout << st.size() << endl;
    return 0;
} 
```

最初にn個の配列を用意して、各要素へb+=a, a=0と加算していく手法はダメだと分かります。
2次元配列groupを用意して、a[i]の要素をgroupに下記のように追加していきます。

- すでにあるグループへ追加する
- 新しいグループを作り追加する

O(N!)の処理になります。

```
[0] = {2, 5, 7}
```

```
[0] = {2, 5}
[1] = {7} 
```

```
[0] = {2, 7} 
[1] = {5}
```

```
[0] = {2} 
[1] = {5, 7}
```

```
[0] = {2}
[1] = {5}
[2] = {7} 
```

のように処理を行います。

```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<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> group;
    set<ll> st;
    auto dfs = [&](auto dfs, int v){
        if(v >= N){
            ll sum = 0;
            int n = group.size();
            rep(i, n){
                sum ^= group[i];
            } 
            st.insert(sum);
            return;
        }

        int n = group.size();
        rep(i, n){
            group[i] += A[v];
            dfs(dfs, v+1);
            group[i] -= A[v];
        }

        group.push_back(A[v]);
        dfs(dfs, v+1);
        group.pop_back();
    };
    dfs(dfs, 0);

    cout << st.size() << endl;
    return 0;
} 
```

O(12!) = 479001600
処理速度は間に合うと思われますがTLEになりました。
setのデータ構造の問題です。

setは要素をソートして保持します。
O(logN)の為、TLEの原因になっています。
unordered_setを使用します。
unordered_setはハッシュ値に基づき、コンピュータにとって都合の良い任意の順序で要素を保持します。
O(1), O(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() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> group;
    unordered_set<ll> st;
    auto dfs = [&](auto dfs, int v){
        if(v >= N){
            ll sum = 0;
            int n = group.size();
            rep(i, n){
                sum ^= group[i];
            } 
            st.insert(sum);
            return;
        }

        int n = group.size();
        rep(i, n){
            group[i] += A[v];
            dfs(dfs, v+1);
            group[i] -= A[v];
        }

        group.push_back(A[v]);
        dfs(dfs, v+1);
        group.pop_back();
    };
    dfs(dfs, 0);

    cout << st.size() << endl;
    return 0;
} 
```

ACできました。
全ての基本である全探索を学びました。
今回のABCは良問が揃っていたコンテストだと思います。