AtCoder Beginner Contest 242

## [A - T-shirt](https://atcoder.jp/contests/abc242/tasks/abc242_a)

O(1)
c / (b - a)で確率を求めることができます。

```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() {
    double a, b, c, x;
    cin >> a >> b >> c >> x;

    if(a >= x){
        cout << 1 << endl;
    }else if(b >= x){
        cout << c / (b - a) << endl;
    }else{
        cout << 0 << endl;
    }

    return 0;
} 
```

## [B - Minimize Ordering](https://atcoder.jp/contests/abc242/tasks/abc242_b)

O(N)
データ構造を使用して、aがx個、bがy個と計測していきます。
その後、文字列を作成します。

```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;
    rep(i, s.size()){
        mp[s[i]]++;
    }
 
    string ans;
    for(auto m:mp){
        for(int i=0; i<m.second; i++){
            ans+=m.first;
        }
    }
    cout << ans << endl;
    return 0;
}
```

## [C - 1111gal password](https://atcoder.jp/contests/abc242/tasks/abc242_c)

O(N)
全ての整数 1≤i≤N に対して、 1≤Xi≤9
全ての整数 1≤i≤N−1 に対して、 ∣Xi−Xi+1∣≤1
という制約から、2という整数に対して次の桁は1, 2, 3の整数を計測していけばいいことが分かります。
1という整数に対して次の桁は1, 2の整数を計測します。
9という整数に対して次の桁は8, 9の整数を計測します。

```text: 漸化式
if(j==1) dp[i][j] = (dp[i-1][j] + dp[i-1][j+1]) % MOD;
if(j==9) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
if(1<j && j<9) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]) % MOD;
```

漸化式を作成し、コードを書きます。
初心者は受け取るDPで考察すると漸化式を作成しやすいです。

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

ll MOD = 998244353;
ll dp[1000010][10];

int main() {
    ll N, ans=0;
    cin >> N;
    repx(i, 0, 10) dp[0][i] = 1;
    for(int i=1; i<N; i++){
        for(int j=1; j<10; j++){
            if(j==1){
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1]) % MOD;
            }else if(j==9){
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
            }else{
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]) % MOD;
            }
        }
    }
    for(int j=1; j<10; j++){
        ans = (ans + dp[N-1][j]) % MOD;
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - ABC Transform](https://atcoder.jp/contests/abc242/tasks/abc242_d)

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

string s;
int q;

char g(char a, ll add){
    return char('A'+(a-'A'+add)%3);
}

char dfs(ll t, ll k){
    if(t==0) return s[k];
    if(k==0) return g(s[0], t);
    return g(dfs(t-1, k/2), k%2+1);
}

int main() {
    cin >> s >> q;
    rep(i, q){
        ll t, k;
        cin >> t >> k;
        cout << dfs(t, k-1) << endl;
    }

    return 0;
}
```