AtCoder Beginner Contest 324

## [A - Same](https://atcoder.jp/contests/abc324/tasks/abc324_a)

O(N)
文字の種類を計測する。

```C++:C++
#include <bits/stdc++.h>
 
#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;
    set<int> st;
    rep(i, N){
        int a;
        cin >> a;
        st.insert(a);
    }

    if(st.size() == 1) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [B - 3-smooth Numbers](https://atcoder.jp/contests/abc324/tasks/abc324_b)

O(?)
Nを２で割り続ける。
Nを3で割り続ける。
Nが１かどうか

```C++:C++
#include <bits/stdc++.h>
 
#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;

    while(N%2==0) N = N / 2;
    while(N%3==0) N = N / 3;

    if(N==1) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [C - Error Correction](https://atcoder.jp/contests/abc324/tasks/abc324_c)

実装問題。
文字列の長さでパターン分けをして、愚直に実装した方がいい。

```C++:C++
#include <bits/stdc++.h>
 
#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;

    string T;
    cin >> T;

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    int len = T.size();
    vector<int> ans;
    rep(i, N){
        if(len < S[i].size()-1 || len > S[i].size() + 1){
            continue;
        }

        if(len == S[i].size()+1){
            int cnt = 0;
            int k = 0;
            for(int j=0; j<len; j++){
                if(S[i][k] != T[j]){
                    cnt++;
                }else{
                    k++;
                }
                if(cnt>1) break;
            }

            if(cnt<2){
                ans.push_back(i+1);
            }
            continue;
        }

        if(len == S[i].size()){
            int cnt = 0;
            for(int j=0; j<S[i].size(); j++){
                if(S[i][j] != T[j]){
                    cnt++;
                }
                if(cnt>1) break;
            }

            if(cnt<2){
                ans.push_back(i+1);
            }

            continue;
        }

        if(len == S[i].size() - 1){
            int cnt = 0;
            int k = 0;
            for(int j=0; j<S[i].size(); j++){
                if(S[i][j] != T[k]){
                    cnt++;
                }else{
                    k++;
                }
                if(cnt>1) break;
            }

            if(cnt<2){
                ans.push_back(i+1);
            }

            continue;
        }

    }

    cout << ans.size() << endl;
    rep(i, ans.size()) cout << ans[i] << ' ';

    return 0;
} 
```

下記が復習したコーディング内容。

文字列の前から一致しない文字まで判定。
文字列の後から一致しない文字まで判定。
同じ文字の数をcntとする。
Tの長さlenTとS[i]の長さlenSとcntを比較する。
lenT-1<=cnt, lenS-1<=cnt
の２つを満たす時、文字列Tと等しい可能性のある文字列である。

```C++:C++
#include <bits/stdc++.h>
 
#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;

    string T;
    cin >> T;

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    vector<int> ans;
    rep(i, N){
        int start = 0;
        int end_T = T.size()-1;
        int end_S = S[i].size()-1;
        int cnt = 0;

        if(T.size() < S[i].size()-1 || T.size() > S[i].size() + 1) continue;

        while(S[i][start] == T[start] && start<min(T.size(), S[i].size())) cnt++, start++;

        while(S[i][end_S] == T[end_T] && end_T>=0 && end_S>=0) cnt++, end_T--, end_S--;

        if(cnt>=T.size()-1 && cnt>=S[i].size()-1) ans.push_back(i+1);
    }

    cout << ans.size() << endl;
    rep(i, ans.size()) cout << ans[i] << ' ';

    return 0;
} 
```

本番にて、上のコードをノーペナルティで通すの無理だと思われる。
そうなると１番目のコードで良かった。

## [D - Square Permutation](https://atcoder.jp/contests/abc324/tasks/abc324_d)

平方根の問題。
N=13の順列はTLEで間に合わない。

Sで可能な最大値をmax_valueとする。
i=0からループして、i×i<max_valueまでの判定を行う。
i×iの各桁の数字の数が、Sの各桁の数字の数と同じ構成になっているかどうか。

テストケース中の１つのチェックは、0^2=0を判定している。
0の平方根は0である。

```C++:C++
#include <bits/stdc++.h>
 
#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;
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    reverse(S.begin(), S.end());
    ll maxNum = atoll(S.c_str());
    ll cnt = 0;
    reverse(S.begin(), S.end());

    for(ll i=0; i*i<=maxNum; i+=1LL){
        string T = to_string(i*i);
        ll add = S.size() - T.size();

        while(add) T = '0' + T, add--;
        sort(T.begin(), T.end());
        if(T == S) cnt++;
    }
    cout << cnt << endl;

    return 0;
} 
```