AtCoder Beginner Contest 071 by C

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

atcoder.jp

できたもの
A
B

できなかったもの
C
D

問題A

#include <stdio.h>

int abs(int n){
    return n < 0 ? -n : n;
}

int main(void){
    int x,a,b;
    scanf("%d %d %d", &x,&a,&b);

    if(abs(a-x)<abs(b-x)){
        printf("A\n");
    }
    else{
        printf("B\n");
    }
    
    return 0;
}

方針

xからa,bまでの距離の絶対値が小さい方が答え。
絶対値を求めるのはabs関数で、差が負だった場合にマイナスを付けて正にします。

問題B

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

int main(void){
    int i;
    char s[100001];
    scanf("%s", s);
    int size = strlen(s);

    int count[26] = {0};
    for(i=0;i<size;i++){
        count[s[i]-97]++;
    }

    for(i=0;i<26;i++){
        if(count[i]!=0){
            continue;
        }
        else{
            printf("%c\n", i+97);
            return 0;
        }
    }

    printf("None\n");
    
    return 0;
}

方針

出てきたアルファベットを配列でカウントすることで文字列に現れるか否かを判断します。
出力する際にやりやすいかと思い文字コードで判断しました。
最初にカウントが0である文字のアルファベットを出力します。
全部カウントがあった場合はfor文を抜けるのでNoneを出力します。

問題C

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

void merge_sort(int array[], int left, int right){
    int i,j,k,mid;
    int *work;

    if(left >= right){
        return;
    }

    work = (int*)malloc(sizeof(int)*right+1);

    mid = (left+right)/2;
    merge_sort(array,left,mid);
    merge_sort(array,mid+1,right);

    for(i=mid;i>=left;i--){
        work[i] = array[i];
    }
    for(j=mid+1;j<=right;j++){
        work[right-(j-(mid+1))] = array[j];
    }
    i = left; 
    j = right;

    for(k=left;k<=right;k++){
        if(work[i]<work[j]){
            array[k] = work[i++];
        }
        else{
            array[k] = work[j--];
        }
    }    
    free(work);

}

int main(void){
    int n,i,j;
    int max1 = 0,max2 = 0; 
    int a[100001];
    scanf("%d", &n);

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

    merge_sort(a,0,n-1);
  
    for(i=n-1;i>=0;i--){
        //同じ数字が2つあるか
        if(a[i]==a[i-1]){
            max1 = a[i];
            //同じ数字が4つあるか
            if(a[i-1]==a[i-2]&&a[i-2]==a[i-3]){
                printf("%lld\n", (long long)max1*(long long)max1);
                return 0;
            }
            break;
        }
    }

    //別に2つ以上ある数字があるか
    for(j=i-1;j>=0;j--){
        if(a[j]==max1){
          continue;
        }
        if(a[j]==a[j-1]){
            max2 = a[j];
            break;
        }
    }

    printf("%lld\n", (long long)max1*(long long)max2);


    return 0;
}

方針

まず4つ以上同じ数字があるか、2～3個ある数字が2組あれば長方形（正方形を含む）が作れます。
面積を最大にするにはその条件を満たす数字のうちより大きいものを使えばいいです。

大きい数字を使うためにまず配列を昇順でソートします。
数字の数が~10^5と大きいのでマージソートとやらを使う模様。

詳しくは↓
qiita.com

ソートしたら配列の後ろからまず同じ数字が2つあるか調べます。
2つ並んでいるものがあればついでにあともう2つないか調べてもしあれば4つあるということで正方形を作ります。
なければ次に大きくて2つ以上ある数値をしらべ、見つかればその2種類をかけ合わせます。

long long 型を用いることに注意。

問題D

#include <stdio.h>

#define divide 1000000007

int main(void){
    int n,i,t;
    long long ans = 1;
    int flag;
    char s1[53],s2[53];
    scanf("%d", &n);
    scanf("%s", s1);
    scanf("%s", s2);
    
    if(s1[0]==s2[0]){
        ans *= 3;
        flag = 0;
        t = 1;
    }
    else{
        ans *= 6;
        flag = 1;
        t = 2;
    }

    for(i=t;i<n;i++){
        if(flag==0){
            if(s1[i]==s2[i]){
                ans *= 2;
                ans %= divide;
                flag = 0;
            }
            else{
                ans *= 2;
                ans %= divide;
                flag = 1;
                i++;
            }
        }
        else{
            if(s1[i]==s2[i]){
                flag = 0;
            }
            else{
                ans *= 3;
                ans %= divide;
                flag = 1;
                i++;
            }
        }
    }

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

    return 0;
}

方針

文字列を左から順にチェック
以下のパターン①とパターン②の組み合わせでできています。

パターン①：一種類を縦に並べる
t
t

パターン②：二種類を横に並べる
ww
yy

これらについて、
パターン①
先頭：3通り
左隣がパターン①：2通り
左隣がパターン②：1通り
パターン②
先頭：6通り
左隣がパターン①：2通り
左隣がパターン②：3通り

これをかけ合わせていくと解が得られます。

割ったあまりを利用することを忘れずに。
今回は掛け算なので気にせず随時割っていけばＯＫ