エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

##[A - Three Dice](https://atcoder.jp/contests/abc202/tasks/abc202_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 a, b, c;
    cin >> a >> b >> c;

    int res = 21 - (a+b+c);
    cout << res << endl;

    return 0;
}
```

##[B - 180°](https://atcoder.jp/contests/abc202/tasks/abc202_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; }

int main() {
    string s;
    cin >> s;

    string t = s;

    rep(i, s.length()){
        if(s[i] == '6') t[i] = '9';
        else if(s[i] == '9') t[i] = '6';
    }

    reverse(t.begin(), t.end());
    cout << t << endl;

    return 0;
}
```

##[C - Made Up](https://atcoder.jp/contests/abc202/tasks/abc202_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; }

int main() {
    int n;
    cin >> n;

    vector<int> A(n), B(n), C(n), memo(n);

    rep(i, n) cin >> A[i];
    rep(i, n) cin >> B[i];
    rep(i, n) cin >> C[i];
    rep(i, n) memo[i] = 0;

    ll res=0;
    rep(i, n) memo[B[C[i] - 1]]++;
    rep(i, n) res += memo[A[i]];
    
    cout << res << endl;

    return 0;
}
```

##[D - aab aba baa](https://atcoder.jp/contests/abc202/tasks/abc202_d)

O(N)
まずは全探索。
TLEですね。

```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 A, B, K;
vector<string> st;

void dfs(string s, int a, int b){
    if(a+b >= A+B){
        st.push_back(s);
        return;
    }

    if(a<A) dfs(s+"a", a+1, b);
    if(b<B) dfs(s+"b", a, b+1);
};

int main() {
    cin >> A >> B >> K;

    dfs("", 0, 0);
    sort(st.begin(), st.end());

    cout << st[K-1] << endl;

    return 0;
}
```

nCrで考えましょう。
組み合わせの総数がKより大きいなら'b'、小さいなら'a'。
一桁確定するごとにA、Bを--していきます。

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

std::vector<std::vector<long long>> comb(int n, int r) {
  std::vector<std::vector<long long>> v(n + 1,std::vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

int main() {
    ll A, B, K;
    cin >> A >> B >> K;
    K--;
    string s;
    ll l = A+B;
    rep(i, l){
        if(0<A){
            ll ans = comb(A+B-1, B)[A+B-1][B];
            if(K < ans){
                s += 'a';
                A--;
            }else{
                s += 'b';
                K -= ans;
                B--;
            }
        }else{
            s += 'b';
            B--;
        }
    }
    cout << s << endl;

    return 0;
}
```