AtCoder Beginner Contest 192

##[A - Star](https://atcoder.jp/contests/abc192/tasks/abc192_a)

O(1)

```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 x;
    cin >> x;
 
    x = x % 100;
    int res = 100 - x;
    cout << res << endl;
 
    return 0;
}
```

##[B - uNrEaDaBlE sTrInG](https://atcoder.jp/contests/abc192/tasks/abc192_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; }
const long long INF = 1LL << 60;
 
int main() {
    string S;
    cin >> S;

    int res=1;
    for(int i=0; i<S.length(); i++){
        if(i%2==0 && islower(S[i])){

        }else if(i%2==1 && isupper(S[i])){

        }else{
            res = 0;
            break;
        }
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}
```

##[C - Kaprekar Number](https://atcoder.jp/contests/abc192/tasks/abc192_c)

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; }
const long long INF = 1LL << 60;

ll g2(ll x){
    vector<int> temp;
    while(x>0){
        int r = x % 10;
        x = x / 10;
        temp.push_back(r);
    }

    sort(temp.begin(), temp.end());
    reverse(temp.begin(), temp.end());

    ll ret=0;
    for(int i=0; i<temp.size(); i++){
        ret += temp[i] * pow(10, i);
    }
    return ret;
}

ll g1(ll x){
    vector<int> temp;
    while(x>0){
        int r = x % 10;
        x = x / 10;
        temp.push_back(r);
    }

    sort(temp.begin(), temp.end());

    ll ret=0;
    for(int i=0; i<temp.size(); i++){
        ret += temp[i] * pow(10, i);
    }
    return ret;
}

ll dfs(ll x){
    ll ret = g1(x) - g2(x);
    return ret;
}
 
int main() {
    ll n, k;
    cin >> n >> k;

    ll res=n;
    for(int i=1; i<=k; i++){
        res = dfs(res);
    }
    cout << res << endl;
 
    return 0;
}
```

##[D - Base n](https://atcoder.jp/contests/abc192/tasks/abc192_d)

O(NlogN)
d問題は、n進数の種類ではないです。
xをn進数表記として扱い10進数に返還した際の種類ね。
1は2進数でも9進数でも1種類という事。

考え方はleft=d, right=Mとし、n=midとしてXを変換してます。
L進数まで変換可能なら, d+1からL進数までの種類が答えと判断。
L-dが答えだと思ってます。

```python:python 
import math
import heapq
import itertools
from functools import reduce
 
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out
 
# main
def main():
    S = str(input())
    M = int(input())
    d = 0
 
    if len(S) == 1:
        if int(S) <= M:
            print(1)
        else:
            print(0)
 
        return
 
    for i in range(0, len(S)):
        d = max(d, int(S[i]))
 
    L = d
    R = M+1
    while (R-L)>1:
        mid = (R+L) // 2
        T = Base_n_to_10(S, mid)
        if T <= M:
            L = mid
        else:
            R = mid
    res = L-d
    print(res)
 
# エントリポイント
if __name__ == '__main__':
    main()
```

##感想
レート通りの結果が出ました。
時間があったらダイクストラも勉強します。