AtCoder Beginner Contest 042 by C

AtCoder Beginner Contest 042 について
C言語での回答

atcoder.jp

初めてAtCoderの問題を解きました。Ａ以外全然です。

できたもの
Ａ

できなかったもの
Ｂ
Ｃ
Ｄ

問題Ａ

#include <stdio.h>

int main(void){
 int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  
  if(a==7&&b==5&&c==5){
  	printf("YES");
  }
  else if(a==5&&b==7&&c==5){
  	printf("YES");
  }
  else if(a==5&&b==5&&c==7){
  	printf("YES");
  }
  else{
  	printf("NO");
  }
  
  return 0; 
}

数字の組み合わせが5,7,5であればOK。
a,b,cそれぞれに7が入力されると考えて条件わけ。

問題B

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void strSort(char **str, int n, int l){

    int i, j, k;

    char temp[1024];

    for (i=0; i<n-1; i++){
        for (j=i+1; j<n; j++){
            for (k=0; k<l; k++){
                
                if (str[i][k] > str[j][k]){ //k番目の文字を比較
                    strcpy(temp,str[i]);
                    strcpy(str[i],str[j]);
                    strcpy(str[j],temp);
                    break;
                }
                else if(str[i][k] == str[j][k]){
                    continue;
                }
                else {
                    break;
                }

            }
        }
    }

    for (i=0; i<n; i++){
        printf("%s", str[i]);
    }
    printf("\n");
}

int main(){

    int n, l, i;
    char **str;

    scanf("%d%d", &n, &l);

    str = (char **)malloc(sizeof(char *) * n);

    for (i=0; i<n; i++){
        str[i] = (char *)malloc(sizeof(char) * l);
    }

    for (i=0; i<n; i++){
        scanf("%s", str[i]);
    }

    strSort(str, n, l);

    for (i=0;i<n;i++) {
        free(str[i]);
    }
    free(str);

    return 0;
}

配列の要素数を入力で受け取るので宣言時に指定できません（C言語では残念ながら……）
そこでmalloc（エムアロック）なるものを利用します。
今回は二次元配列でn行l列（文字列n個、文字数l字）を作り、入力。

文字列を受け取った後は一文字ずつ比較して辞書順にし、出力。

問題C

#include <stdio.h>

int main(void){
    int n, k;
    int i, j;
    int str[10];

    scanf("%d %d", &n, &k);

    for(i=0;i<k;i++){
        scanf("%d", &str[i]);
    }

    int check = n;
    int flag = 0;
    while(check!=0){
        for(i=0;i<k;i++){
            if(check%10==str[i]){
                n++;
                check = n;
                flag = 1;
                break;
            }
        }
        if(flag==0){
            check/=10;
        }
        else{
            flag = 0;
        }
    }

    printf("%d", n);

    return 0;
}

%10をみれば1桁ずつ数字を確認できます。
ある桁の数が嫌いな数字になった場合は元のNに+1をして再度1からチェックし直し。
（入力例１について、最初の3回は%10が0で嫌いな数字に含まれていないのですが、4回目は1で嫌いな数字なのでN=1000に+1をして1001とし、再度%10を1の位から繰り返します。）
これを繰り返して嫌いな数字を含まないかつNより大きい値最小の値が得られます。

問題D

#include <stdio.h>

#define MOD 1000000007

//fac:n! finv:(n!)^-1 inv:
long long fac[200001],finv[200001],inv[200001];

void COMint(){
    int i;
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(i=2;i<200001;i++){
        //n!を計算
        fac[i] = fac[i-1]*i%MOD;
        //逆元を計算
        inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
        //(n!)^-1を計算
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

long long COM(long long n, long long k){
    if(n<k){
        return 0;
    }
    if(n<0||k<0){
        return 0;
    }
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int main(void){
    COMint();
    long long h,w,a,b,ans=0;
    int i;
    scanf("%lld %lld %lld %lld", &h, &w, &a, &b);

    for(i=1;i<=w-b;i++){
        long long ans_sub = COM(h-a+b+i-2,b+i-1)*COM(w-b+a-i-1,a-1)%MOD;
        ans += ans_sub;
        ans %= MOD;
    }

    printf("%lld\n", ans);

    return 0;
}

解説参照。
nCr は　n!/(r! * (n-r)!)　なので、あらかじめ以下を計算しておきます。
①　x! (mod 10^9+7)
②　(x!)^-1 (mod 10^9+7)

フェルマーの小定理より、②は以下のように書き換えられます
x^-1 ≡ x^(10^9+5(=10^9+5-2)) (mod 10^9+7)
②　(x!)^-1 ≡ (x!)^(10^9+5) (mod 10^9+7)

①x!はi=1から順にかけていきます。
②の二項係数（逆元の求め方）についてはこちらを参照
drken1215.hatenablog.com