AtCoder Beginner Contest 397

## [A - Thermometer](https://atcoder.jp/contests/abc397/tasks/abc397_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() {
    double x;
    cin >> x;

    if(x >= 38.0){
        cout << 1 << endl;
    }else if(x >= 37.5){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }

    return 0;
}
```

## [B - Ticket Gate Log](https://atcoder.jp/contests/abc397/tasks/abc397_b)

O(N)
Sの文字列を２文字毎に判定して、奇数のインデックスは`io`、偶数のインデックスは`oi`になっているか探索します。

```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() {
    string s;
    cin >> s;

    int n = s.size();
    string t;
    int ans = 0;
    rep(i, n){
        if(t.size()%2==0 && s[i] == 'o'){
            t += 'i';
            t += 'o';
        }else if(t.size()%2==1 && s[i] == 'i'){
            t += 'o';
            t += 'i';
        }else{
            t += s[i];
        }
    }
    if(t.back() == 'i') t += 'o';
    cout << t.size() - s.size() << endl;
    return 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() {
    string s;
    cin >> s;

    int n = s.size();
    int ans = 0;
    char target = 'i';
    rep(i, n){
        if(target != s[i]) ans++;
        else target = target == 'i'?'o':'i';
    }
    if(s.back() == 'i') ans++;
    cout << ans << endl;
    return 0;
} 
```

## [C - Variety Split Easy](https://atcoder.jp/contests/abc397/tasks/abc397_c)

単純に全探索を行うとO(N^2)となってTLEになります。

O(NlogN)
全ての要素の値をキーにして個数を値として保持をするmapを用意します。
先頭からループして、種類数を保持するsetを用意します。
ループ中にsetへ値を追加、mapから個数を減算していき0になったらキーを削除します。

```
ans = max(ans, setのサイズ+mapのサイズ)
```

が答えになります。

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

void solve(int N, vector<int>& A){
    map<int, int> mp;
    rep(i, N) mp[A[i]]++;

    int ans = 0;
    set<int> st;
    rep(i, N-1){
        st.insert(A[i]);
        if(mp.find(A[i]) != mp.end()){
            mp[A[i]]--;
            if(mp[A[i]] <= 0){
                mp.erase(A[i]);
            }
        }
        int m = st.size() + mp.size();
        ans = max(ans, m);
    }
    cout << ans << endl;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    solve(N, A);

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

void solve(int N, vector<int>& A){
    vector<int> numl(N+1), numr(N+1);
    {
        set<int> st;
        rep(i, N){
            st.insert(A[i]);
            numl[i+1] = st.size();
        }
    }
    {
        set<int> st;
        for(int i=N-1; i>=0; i--){
            st.insert(A[i]);
            numr[i] = st.size();
        }
    }

    int ans = 0;
    for(int i=1; i<N; i++){
        ans = max(ans, numl[i] + numr[i]);
    }
    cout << ans << endl;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    solve(N, A);

    return 0;
} 
```

## [D - Cubes](https://atcoder.jp/contests/abc397/tasks/abc397_d)

数学の問題です。
`x^3 - y^3`を因数分解します。

```math
(x-y) * (x^2 + xy + y^2)
```

`x > y`であり、`x`と`y`の差分は0以上だと分かります。
`x`を、

```math
x = y + d
```

として、`x^3 - y^3`の式を考察します。

```math
x^3 - y^3 = (y+d)^3 - y^3
```

```math
(y+d)^3 - y^3 = y^3 + 3y^2d + 3yd^2 + d^3 - y^3 = d^3 + 3y^2d + 3yd^2
```

```math
d^3 + 3y^2d + 3yd^2 = d^3 + 3yd * (y+d)
```

よって、

```math
N = d^3 + 3yd * (y+d)
```

```math
\frac{(N - d^3)}{3d} = y * (y+d)
```

```math
\frac{(N - d^3)}{3d} = c
```

として、

```math
y^2 + dy - c = 0
```

`y`は、解の公式から

```math
y = \frac{-d * \sqrt{d^2 + 4 * 1 * c}}{ 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() {
    ll N;
    cin >> N;

    for(ll d = 1; d * d * d < N; d++){
        ll c = N - d * d * d;
        if(c % (3 * d)) continue;
        c /= 3 * d;
        ll y = (sqrt(d * d + 4 * c) - d) / 2;
        if(y * y + d * y - c == 0){
            cout << y+d << ' ' << y << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
} 
```

忘れないように１週間に１回、あと５回ぐらい解こうと思います。