AtCoder Beginner Contest 046 by C

AtCoder Beginner Contest 046 の問題について
C言語での回答。

atcoder.jp

できたもの

• A

• B

できなかったもの

• C

• D

問題A

#include <stdio.h>

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

    if(a==b&&a==c&&b==c){
        printf("1");
    }
    else if(a==b&&a!=c||a==c&&a!=b||b==c&&b!=a){
        printf("2");
    }
    else{
        printf("3");
    }

    return 0;
}

a,b,cが同じ値かで場合分け。
１．3つとも違う
２．2つが一緒で1つが違う
３．3つとも一緒

問題B

#include <stdio.h>

int main(void){
    int n, k;
    int i,j;
    scanf("%d %d", &n, &k);

    int sum = k;
    int sum_tmp;
    int color = k-1;
    if(n!=1){
        for(j=0;j<n-1;j++){
            sum_tmp = sum*color;
            sum = sum_tmp;
        }
    }

    printf("%d", sum);

    return 0;
}

n個ならんだボールのうち、一番左のボールの色の選択肢はk通り。
その右隣のボールは、左のボールとは違う色でなければならないので、選択肢はk-1通り。
その更に右のボールも左のボールと違う色なのでk-1通り。
よって組み合わせは k×(k-1)^(n-1)
プログラムではsum_tmpを使って計算時に値を一時的に保存しています。

問題C

説明はは3つのコードの下にあります。

#include <stdio.h>

int main(void){
    long int n, i, j;
    long int T, A, t, a, x;
    double calc;
    scanf("%ld", &n);
    scanf("%ld %ld", &T, &A);

    for(i=1;i<n;i++){
        scanf("%ld %ld", &t, &a);
        if((T-1)/t+1 > (A-1)/a+1){
            x = (T-1)/t+1;
        }
        else{
            x = (A-1)/a+1;
        }
        A = x*a;
        T = x*t;
    }

    printf("%ld", A+T);

    return 0;
}

まだ不完全燃焼中。
解決したら追記します。
少なくともint型ではなくlong int型を使う必要があるみたいです。
（答えが10^18以下～とあるようにものすごく大きくなるからかもしれませんが）
1を足しているのはceil（切り上げ）を行っていることに等しいと思うのですが、T/tではなく(T-1)/tが理解できていません……

やはりC言語における数値の切り上げが関わっているようです。
daeudaeu.com

こっちの方がちょっとわかりやすかった。
あまりがあるときに1を足すと良いようです。

#include <stdio.h>

int main(void){
    long long n, i, T, A, t, a, x;

    scanf("%lld", &n);
    scanf("%lld %lld", &T, &A);

    for(i=1;i<n;i++){
        scanf("%lld %lld", &t, &a);
	long long xt = (T%t==0 ? T/t : T/t+1);
	long long xa = (A%a==0 ? A/a : A/a+1);
	x = xt > xa ? xt :xa;
        A = x*a;
        T = x*t;
    }

    printf("%lld", A+T);

    return 0;
}

#include <stdio.h>

int main(void){
    long int n, i, j;
    long int T, A, t, a, x;
    scanf("%ld", &n);
    scanf("%ld %ld", &T, &A);

    for(i=1;i<n;i++){
        scanf("%ld %ld", &t, &a);
        x = T/t > A/a ? (T-1)/t+1 : (A-1)/a+1;

        A = x*a;
        T = x*t;
    }

    printf("%ld", A+T);

    return 0;
}

3つも載せましたがやってることは一緒。

現時点での票数をそれぞれTi、Ai、xは1以上の整数とします。
まず、次の票数は現時点の票数以上ですので、以下が成り立ちます。

Ti+1 >= Ti
Ai+1 >= Ai

また、i番目の票数はi番目の比率の整数倍なので、以下も成り立ちます。
Ti+1 = ti+1 * x
Ai+1 = ai+1 * x

以上二つの式から以下の関係が導けます。
ti+1 * x >= Ti
ai+1 * x >= Ai

x >= Ti/ti+1
x >= Ai/ai+1

したがって、どちらも満たす最小の整数がx、つまりより大きい値を切り上げれば求まります。

解けなかった原因

方針が全く立たず、ものすごい量の分岐を作成しようとした（当然うまくできず）。
分岐を作ってやること自体はできなくもないかもしれませんが……。

問題D

まだ