AtCoder Beginner Contest 202 備忘録

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

A - Three Dice

ｽﾏｰﾄじゃないけど、力技で各目が出た時の逆値を返す関数を作って計算。
よくよく考えると、7から引くだけでええやん。。。
まぁあってるので良し。

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

int dice(int a){
    int ans;
    if(a==1){
        ans=6;
    }
    else if(a==2){
        ans=5;
    }
    else if(a==3){
        ans=4;
    }
    else if(a==4){
        ans=3;
    }
    else if(a==5){
        ans=2;
    }
    else if(a==6){
        ans=1;
    }
    return ans;
}

int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    int ans=dice(a)+dice(b)+dice(c);
    cout<<ans<<endl;

}

B - 180°

文字列を180°回転させるやつ。
・文字をreverseでまず反転させて、
・6は9へ、9は6へreplaceで置き換える
わりと簡単。

# include <stdio.h>
# include <bits/stdc++.h>
# include <math.h>
# include <iostream>
using namespace std;

int main(void){
    string S;
    cin>>S;
    reverse(S.begin(), S.end());
    long long num=S.size();
    for(int i=0;i<num;i++){
        if(S.at(i)=='6'){
            S.replace(i,1,"9");
        }
        else if(S.at(i)=='9'){
            S.replace(i,1,"6");
        }
    }
    cout<<S<<endl;
}

C - Made Up

問題文わかりづらい。
B配列のうち、C配列の番号だけ抽出し、A配列と一致するものの数を数えるってこと。
一致するものの個数を比較なので、map関数使えばいいかなと思いつく。

具体例の方が思いつきやすいので、下記のような配列で考える。

この場合のA,Bの個数をカウントした連想配列AA,BB'は、

となる。(故あってBB’としておく)
題意より、必要となるのは配列Bの情報ではなく、BのうちのC番目のものだけ。
なのでBB’からC番目のものだけを抜き出す。

イメージとしてはこんな感じ。
この部分を

BB[B[C[i]]]++;

と表現。
i=1のとき
C[1]=2　⇒　B[2]=3 ⇒BB[3]がインクリメントされる。(=1)
i=2のとき
C[2]=2　⇒　B[2]=3 ⇒BB[3]がインクリメントされる。(=2)
こんな感じで、C要素番目のB配列が連想配列BBに格納されていく。
これでB配列からの抽出は完了するので、あとはA配列との比較をする。
どっちも1以上（=存在する）場合を抽出し、複数個数がある場合は、組み合わせを考慮して、掛け算して…とひたすら積算。
これでオッケー。

# include <stdio.h>
# include <bits/stdc++.h>
# include <math.h>
# include <iostream>
using namespace std;

int main(void){
    long long N;
    long long A[110000];
    long long B[110000];
    long long C[110000];
    map<long long,long long>AA;
    map<long long,long long>BB;
    map<long long,long long>CC;    
    long long ans=0;

    cin>>N;
    for(int i=1;i<=N;i++){//1番目からN番目で数えた方が間違いなさそうなので、1~Nにする
        cin>>A[i];
        AA[A[i]]++;//A配列の要素の個数をカウント
    }
    for(int i=1;i<=N;i++){
        cin>>B[i];
    }
    for(int i=1;i<=N;i++){
        cin>>C[i];
        BB[B[C[i]]]++;//B配列のうち、C配列要素の番号の数だけカウント
    }    
    for(int i=1;i<=N;i++){//最大でもNまで
        if(AA[i]>0&&BB[i]>0){//同じ番号で同時に1以上がある場合が該当
            ans=ans+AA[i]*BB[i];//組み合わせを考慮して要素の数で掛け算し、積算
        }
    }   
    cout<<ans<<endl;
}

D - aab aba baa

A個のaとB個のbから作られる文字列について、辞書順でK番目を求める問題。
解説通り一番上の文字から考えると、解説通りに実施。
コンビネーションについてはおーばーふろー対策で二項定理を使うが後述。

↓参考解説
https://blog.hamayanhamayan.com/entry/2021/05/22/225424

まず組合せの考え方。
総文字数はA+B。
文字列の組合せは、
「どこにBを入れるか」
さえ決まれば、Aは勝手にきまるので、
A+B C B通りある。よって、順序も同じ数だけある。
ここでｱﾀﾏがaだったと仮定する。
aをfixすると残りはA+B-1 C B通りある。先ほどと同じように、順序も同じだけある。
よって求めるK番目が1~ A+B-1 C B以内であれば、ｱﾀﾏaが真となる。
そしてさらに一個下の文字をaと仮定して、Kより高いか低いか…を繰り返していく。
逆にKがA+B-1 C Bより大きい場合は、ｱﾀﾏがbとなるが、その場合次のけたはb以下の検索になるので、少し変わる。
この場合、飛ばした分を引く必要があるのでKからA+B-1 C Bから引いて、次の順序大小を比較する。
言葉でかくとむずかしい。

以上以下の境界に気を付けて実装すれば、理屈は追える。

ただし、この後ﾈｯｸになるがaCbの計算。
これまで分母/分子で計算してたがa=20とかあたりで、longlongでもｹﾀがｵｰﾊﾞｰﾌﾛｰする。
なので、ここでコンビネーションの計算に二項定理、パスカルの三角形を使う。
https://www.studyplus.jp/386

・(x+y)^nを展開した時の各項の係数を考える。
　係数は「x,yを○○個取ったときの組合せがいくつあるか」で決まるので、
　例えばn=3の時は、x^2・yの組合せは、xxy,xyx,yxxの3通りだから、係数は3になる。
　ってのが二項定理
・二項定理の定数は、パスカルの3角形で表せる。n+1Ck=nCk−1+nCk　ってやつ。
　これなら和計算だけでCを算出可能。
　これを実装したのが、comb関数。色々ｺｰﾄﾞ例あったので、参考にして行列じゃなくて直接数値入力⇒数値出力の形に変更。

コンビネーション計算は二項定理必須。
テキトーにやるとすぐ地球滅亡ﾚﾍﾞﾙの計算量になっちゃうんだなと理解。

# include <stdio.h>
# include <bits/stdc++.h>
# include <math.h>
# include <iostream>
using namespace std;

long long comb(long long a, long long b){//二項定理から算出する関数
    vector<vector<long long> > v(a+1, vector<long long>(a+1));
    for(int i = 0;i <v.size(); i++){//パスカルの３角形の外側=1になる部分を定義
        v[i][0]=1;
        v[i][i]=1;
        }       
    for(int k = 1;k <v.size();k++){
        for(int j = 1;j<k;j++){
            v[k][j]=(v[k-1][j-1]+v[k-1][j]);//パスカルの3角形をチマチマ計算
            }
        }
    long long T=v[a][b];
    return T;
}

int main(void){
    int A,B;
    long long K;
  	cin>>A>>B>>K;
    long long t;
    t=comb(A+B-1,B);
    string S="";
  	long long j=A+B;
    
    for(int i=0;i<j;i++){
        t=comb(A+B-1,B);
        if(A==0){
            S=S+'b';
            B--;          
        }
        else if(B==0){
            S=S+'a';
            A--;
        }
        else{
          if(t>=K){
            S=S+'a';
            A--;
          }
          else{
            S=S+'b';
            B--;
            K=K-t;
          }
        }
      }
    cout<<S<<endl;
}