AtCoder Beginner Contest 180 by C

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

atcoder.jp

できたもの
A
B
C

できなかったもの
D以降

問題A

#include <stdio.h>

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

    printf("%d\n", n-a+b);
    
    return 0;
}

方針

元々入ってた数(n)からA個を取り出し(-A)、B個入れる(+B)というのを出力。

問題B

#include <stdio.h>
#include <math.h>

double abs(double a){
    return a < 0 ? -a : a;
}

double max(double a,double b){
    return a > b ? a : b;
}

int main(void){
    int n,i;
    double x[100001];
    scanf("%d", &n);

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

    //マンハッタン距離
    long long dm = 0;
    for(i=0;i<n;i++){
        dm += abs(x[i]);
    }
    printf("%lld\n", dm);

    //ユークリッド距離
    double de = 0;
    for(i=0;i<n;i++){
        de += x[i]*x[i];
    }
    double d = sqrt(de);
    printf("%.15lf\n", d);

    //チェビシフ距離
    long long dc = 0;
    int maxnum = 0;
    for(i=0;i<n;i++){
        maxnum = max(maxnum,abs(x[i]));
        dc = maxnum;
    }
    printf("%lld\n", dc);


    return 0;
}

方針

マンハッタン距離は絶対値を返す関数を(abs関数)、チェビシェフ距離は大きい値を返す関数を(max関数)つくってやり、それを利用して指示通りに計算。
ユークリッド距離は平方根を計算しないといけないため、math.hを読み込みsqrtを使います。
このとき、表示する小数点の桁数を増やしておかないと誤差の関係で弾かれるようなので要調整。
%.15lf　と指定子の前に数字を付けるとその桁だけ表示。

合計が大きくなるので型に注意。
xの型をintにしてると上手くいかないのでdouble型でやりました。

オーバーフローについての解説（この問題の解説についてる補足）
atcoder.jp

問題C

#include <stdio.h>

int main(void){
    long long n,i;
    scanf("%lld", &n);
    long long a1[1000001];
    long long a2[1000001];

    long long j = 0,k = 0;
    for(i=1;i*i<=n;i++){
        if(n%i==0){
            a1[j] = i;
            j++;
            if(i*i!=n){
                a2[k] = n/i;
                k++;
            }
        }
    }

    for(i=0;i<j;i++){
        printf("%lld\n", a1[i]);
    }
    for(i=k-1;i>=0;i--){
        printf("%lld\n", a2[i]);
    }

    return 0;
}

方針

約数全列挙問題。
iからNまでやると10^12で時間が足りなくなるため、積の交換法則をここでも使うとn/2で解けます。
0で割らないようiは1から始めてください！！

0で割ってるのがエラーの原因と気づかず、配列が大きいのがダメか？とmallocで作ったのが下。
mallocでは1e8はいいが1e9あたりからエラーになる（終了コード139で多分メモリ周りがよくない）

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

int main(void){
    long long n,i;
    scanf("%lld", &n);
    //long long a1[1000001],a2[1000001];
    long long *a1;
    long long *a2;
    a1 = (long long*)malloc(sizeof(long long)*n/2);
    a2 = (long long*)malloc(sizeof(long long)*n/2);

    long long j = 0,k = 0;
    for(i=1;i*i<=n;i++){
        if(n%i==0){
            a1[j] = i;
            j++;
            if(i*i!=n){
                a2[k] = n/i;
                k++;
            }
        }
    }

    for(i=0;i<j;i++){ 
        printf("%lld\n", a1[i]);
     } 
    for(i=k-1;i>=0;i--){
        printf("%lld\n", a2[i]);
    }

    free(a1);
    free(a2);

    return 0;
}

問題D

#include <stdio.h>

typedef long long ll;

int main(void){
    ll x,y,a,b;
    scanf("%lld %lld %lld %lld", &x,&y,&a,&b);

    ll exp = 0;
    while(x<=(x+b)/a&&a*x<y){
        x *= a;
        exp++;
    }

    printf("%lld\n", exp+(y-1-x)/b);
    
    return 0;
}

方針

より多くトレーニングできる方が多く経験値を得られるので、カコモンジムに通う場合とAtCoderジムに通う場合のうち、値が小さいほうを選べばいいです。
ただし、1e18なのでそれを逐次やるとTLEします（した）。

よって上の方針を言い換える必要があります。
まずaを何回するかを決め、残りの回数b回足すことにします。
よってaの回数を求めます。
ある数zについて、z*a <= z+bを計算しますが、これはz <= (z+b)/aと書き換えることができます。

あとはこの条件を満たす回数がaの回数、
bの回数はy未満かつaによって増えた経験値を引いた残りを割れば出ます。

問題E

まだ