マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）　備忘録

https://atcoder.jp/contests/abc201


結果
A：AC
B：AC
C：時間切れ　解説みてAC
D：時間切れ
E：未
F：未

A - Tiny Arithmetic Sequence
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/4718a5e3-4cfe-5253-e4e4-3a3eecc282a0.png)
配列で入力して、並べ替えして、場合分け。

```php
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main() {
    int A[4];
    cin>>A[0]>>A[1]>>A[2];//配列入力
    sort(A, A+3);//並べ替え
    if(A[0]-A[1] == A[1]-A[2]){//場合分け
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
  }
```


B - Do you know the second highest mountain? 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/22368f5b-5028-7042-c387-497ecc045e0c.png)

map関数で<高さ, 名前>で連想配列に入力する。
高さ検索した方が楽なので、問題とは逆の入力配列にする。
高さでH[i]の配列作っといて、ソートして2番目の高さをゲット
そしてその高さで連想配列から名前を出力させる。

```php
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main() {
    int N;
    cin>>N;
    map<long,string>A;


    int max=0;
    int SECOND=0;//二番目に高い山の番地
    int HIGHEST=0;//一番高い山の番地

    long HIGH[1100];
    string S[1100];

    for(int i=0;i<N;i++){
        cin>>S[i]>>HIGH[i];
        A[HIGH[i]]=S[i];//map関数入力
    }
    sort(HIGH,HIGH+N);//高さだけソート
    int M=HIGH[N-2];//二番目の高さをゲット

    cout<<A[M]<<endl;//二番目高さの名前をmapから読み出し
  }
```

C - Secret Number
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/6ab2745c-fe2f-873c-847a-569830bb433e.png)

なんか高校の数学A系の大学入試っぽい問題。
うまいこと思いつかず、解説を参照。
https://blog.hamayanhamayan.com/entry/2021/05/15/235640

全数を調べるのではなく、ある組合せの時に何通りあるかを計算する。
まず○、×、？の数を数える。
？のままだとわけわからんので、？が○の時の場合をforで計算する。
？が3個なら、0個の時、1個の時、2個の時、3個の時てな感じ。？の数が3個なので当然ながらこの場合は3個まで。
これを含めた○の数で、場合分けして計算する。

○が0個の時：当然ながら0。
○が1個の時：1111とか3333とかなので1通り。ただし、？から化けた○の場合は、
　　　　　　？のうちどれから○に化けたかの組合せがある。要は？の数から1個を選ぶ"C"計算。
○が2個の時：1222みたいに1数：3数のｹｰｽと1122みたいな2数:2数のｹｰｽがある。
　　　　　　前者ｹｰｽは4位置のどこにおくかなので4通り×逆転した際の2通り
　　　　　　後者ｹｰｽは6通り。（うまく説明できないけど3!になる）
　　　　　　4×2+3!=14通り
　　　　　　これにさっきと同じく？の数から2個を選ぶC計算が組合せとして乗ずる。
○が3個の時：1233みたいなやつ。
　　　　　　二つの数をどれにするかで3通り。
　　　　　　残りの数の置き方が3通り×4通り
　　　　　　3×3×4=36通り
　　　　　　またまた？の数から3個を選ぶC計算が組合せとして乗ずる。
○が4個の時：1234的なやつ。
　　　　　　単純に4!になるので、24通り。
○が5個の時：4桁なので、5数を入れることはできない。よって解無し。
6以上も明らかに解無し。

○の数を？の数までインクリメントして、1-4のｹｰｽをそれぞれ計算。
C計算は冒頭でcomb(a,b)関数として定義しとく。

解けるととてもｽｯｷﾘする。

```php
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

long long comb(long long a, long long b){//aCbの関数作っとく
    long long c=1;
    long long d=1;
    for(long long i=0;i<b;i++){
        c=c*(a-i);
        d=d*(b-i);
    }
    long long e=c/d;
    return e;
}

int main() {
    string S;
    cin>>S;
    int maru=0;
    int batsu=0;
    int hatena=0;
    long long count=0;
    int ans=0;
    for(int i=0;i<10;i++){//○×?の数を数える。
        if(S.at(i)=='o'){
            maru++;
        }
        else if(S.at(i)=='x'){
            batsu++;
        }
        else{
            hatena++;
        }
    }

    for(int i=0;i<=hatena;i++){//？の数までインクリメント
        int count=maru+i;//?⇒○になったやつも含めた、○の数。
        if(count==1){
            ans=ans+1*comb(hatena,i);//1数字のみなので1通り×どの？を選ぶか                
        }
        else if(count==2){
            ans=ans+14*comb(hatena,i);//必ずどっちががある2数字の選び方は14通り×どの？を選ぶか？のcomb
        }
        else if(count==3){
            ans=ans+36*comb(hatena,i);//３数字のry
        }
        else if(count==4){//４数ry
            ans=ans+24*comb(hatena,i);
        }
    }
    cout<<ans<<endl;

  }

```