AtCoder Beginner Contest 056 by C

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

atcoder.jp

できたもの
A
B
C

できなかったもの
D

問題A

#include <stdio.h>

int main(void){
    char a,b;
    scanf("%c %c", &a, &b);

    if(a=='H'&&b=='H'){
        printf("H");
    }
    else if(a=='H'&&b=='D'){
        printf("D");
    }
    else if(a=='D'&&b=='H'){
        printf("D");
    }
    else{
        printf("H");
    }
    
    return 0;
}

HとDの組み合わせは4通り。それぞれの条件に合わせてHかDを出力する。

問題B

#include <stdio.h>

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

    int move;
    if(a<b){
        if(b<a+w){
            move = 0;
        }
        else{
            move = b - (a + w);
        }
    }
    else{
        if(a<b+w){
            move = 0;
        }
        else{
            move = a - (b + w);
        } 
    }

    printf("%d", move);

    
    return 0;
}

離れてる距離分移動する。
重なっていたら移動は0。
aとbの大小関係に注意。

問題C

#include <stdio.h>

int main(void) {
    long long x;
    int i;
    scanf("%lld", &x);

    long long sum = 0;
    for(i=1;i<x+1;i++){
        sum += i; 
        printf("%d\n", sum);
        if(sum >= x){
            printf("%d", i);
            break;
        }
    }

    return 0;
}

足し合わせて値を超えた場合が最短。
値は超えてしまっても、Xとの差はそこまでに足した値のどれかなのでそれを引けばちゃんとたどり着けます。

問題D

まだ

解説
https://img.atcoder.jp/arc070/editorial.pdf
公式

https://physics0523.hatenablog.com/entry/2019/01/01/182437
（C言語）

https://blog.hamayanhamayan.com/entry/2017/03/19/085701

https://atcoder.jp/contests/arc070/submissions/1172088
解答例（C＋＋）

解答例

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

int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}

int main(void){
    int i,j,n,k,a[8192];
    bool fl[8192]={0};
    int st,fi,te;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    qsort(a,n,sizeof(int),sortfncsj);

    st=0;fi=n-1;
    while(st<=fi){
        te=(st+fi)/2;
        if(a[te]>=k){
            fi=te-1;
            continue;
        }
        for(i=1;i<k;i++){
            fl[i]=0;
        }
        fl[0]=1;
        for(i=0;i<n;i++){
            if(i==te){
                continue;
            }
            for(j=k-1-a[i];j>=0;j--){
                if(fl[j]==1){
                    fl[j+a[i]]=1;
                }
            }
        }
        for(i=k-a[te];i<k;i++){
            if(fl[i]==1){
                fi=te-1;
                break;
            }
            if(i==k-1){
                st=te+1;
            }
        }
    }
    printf("%d\n",st);
    return 0;
}