AtCoder Beginner Contest 249

## [A - Jogging](https://atcoder.jp/contests/abc249/tasks/abc249_a)

O(1)
計算問題。

```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 a, b, c, d, e, f, x;
    cin >> a >> b >> c >> d >> e >> f >> x;

    ll takahashi =  x / (a+c) * a * b + min(a, x%(a+c))*b;
    ll aoki =  x / (d+f) * d * e + min(d, x%(d+f))*e;

    if(takahashi == aoki) cout << "Draw" << endl;
    else if(takahashi > aoki) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;

    return 0;
} 
```

## [B - Perfect String](https://atcoder.jp/contests/abc249/tasks/abc249_b)

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

    map<char, int> mp;
    int ok1=false, ok2=false;
    for(auto c:s){
        mp[c]++;
        if(c >= 'a' && c <= 'z'){
            // 小文字
            ok1 = true;
        }else if(c >= 'A' && c <= 'Z'){
            // 大文字
            ok2 = true;
        }
    }

    int ok3=true;
    for(auto m:mp){
        if(m.second>1) ok3 = false;
    }

    if(ok1 && ok2 && ok3) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [C - Just K](https://atcoder.jp/contests/abc249/tasks/abc249_c)

O(2^N)
N<=16です。
この手の問題は、O(2^N)のbit全探索の傾向が強いです。

```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, K;
    cin >> N >> K;
    vector<string> S(N);
    for(auto &s:S) cin >> s; 

    int ans=0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        map<char, int> mp;
        for (int i = 0; i < N; ++i) {
            if (bit & (1<<i)) {
                for(auto c:S[i]){
                    mp[c]++;
                }
            }
        }

        int cnt=0;
        for(auto m:mp){
            if(m.second == K) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Index Trio](https://atcoder.jp/contests/abc249/tasks/abc249_d)

まず全探索の計算量を考察します。
O(N^2)にて２*１０＾５＾２になります。
全探索は無理ですね。

次は問題文の計算式を考察します。

```txt
A[i] / A[j] = A[k]
```
を
```txt
A[i] * A[j] = A[k]
```
に変換しましょう。
このときに、 問題の文章からA[k]の最大が２*１０＾５であることが分かります。

```txt
A[i] * A[j] <= 200000 （1 <= A[i] <= 200000) 
```
よって以下の２重ループを考察できます。

```C++:C++
for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        if(A[i]*A[j]>200000) break;
    }
}
```

しかし、これだと数列Aの要素が全て２など、A[i]*A[j]<=200000が成立する要素ばかりだとTLEになります。
同じ数字の要素はまとめて計算するのが良さそうです。

```C++:C++
map<ll, ll> mp;
for(auto &a:A) mp[a]++;

for(auto a:mp){
    for(auto b:mp){
        if(a.first * b.first > 200000) break;

    }
}
```

これで計算量を減らせそうです。


```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;
    vector<ll> A(N);
    for(auto &a:A) cin >> a;

    if(N<3){
        cout << 0 << endl;
        return 0;
    }

    map<ll, ll> mp;
    for(auto &a:A) mp[a]++;

    ll ans=0;
    for(auto a:mp){
        for(auto b:mp){
            if(a.first * b.first > 200000) break;
            ll t = a.first * b.first;
            if(mp.find(t) != mp.end()){
                ans += mp.find(t)->second * a.second * b.second;
            }
        }
    }
    cout << ans << endl;

    return 0;
} 
```