AtCoder ABC392へ参加した記録（A~C問題）

はじめて（たぶん）AtCoderのAtCoder Beginner Contest（ABC）に参加したので、その記録です。

三問しか解けてないし、かなりなんとなーくで解いているので、あんまり参考にならないと思いますが、素人はこんなふうに考えるんだの記録として捉えていただければと思います。

コンテスト開始から問題に取り組みました。
難易度を考え、順当に頭から解いていっています。

A - Shuffled Equation

3つのものから2つの組み合わせなので、普通に全例チェックしました。

#include <stdio.h>
int main(void){
    char buf[100];
    fgets(buf, sizeof(buf), stdin);
    
    int a1, a2, a3;
    sscanf(buf, "%d %d %d", &a1, &a2, &a3);
    
    int flag = 0;
    if( a1 * a2 == a3) flag = 1;
    if(a1 * a3 == a2) flag = 1;
    if (a2 * a3 == a1) flag = 1;
    
    if(flag == 1) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
}

2分27秒でACでした。

B - Who is Missing?

A の要素は相異なるため、個数はN - Mで求められます。

その後は、サイズの最大値はたかだか1000なので、二重ループでも間に合うと判断し、地道に検査。

これでACでした。（開始後10分時点）

#include <stdio.h>
int main(void){
    char buf[100];
    fgets(buf, sizeof(buf), stdin);
    
    int n, m;
    sscanf(buf, "%d %d", &n, &m);
    
    int a[1000];
    for(int i = 0; i < m; i++) {
        scanf("%d", &a[i]);
    }
    int ini = 1;
    int count = n - m;
    printf("%d\n", count);
    for(int i = 0; i < n; i++) {
        int flag = 1;
        for(int j = 0; j < m; j++) {
            if(a[j] == i + 1) {
                flag = 0;
                break;
            }
        }
        if(ini == 1 && flag == 1) {
            printf("%d", i + 1);
            ini = 0;
        }
        else if(flag == 1){
            printf(" %d", i + 1);
        }
    } 
}

C個の出力を横に並べるのがめんどくさかったです。

ひとまず、初期フラグiniを立てておいて、初期フラグが立っていれば"%d"で、立っていなければ" %d"で出力しています。

これって、もっと簡単に出力する方法あるのかな。

C - Bib

最初に以下を書いて提出、TLEになりました。（開始後43分時点）

TLEの誤答

#include <stdio.h>
int main(void){
    char buf[100];
    fgets(buf, sizeof(buf), stdin);
    
    int n;
    sscanf(buf, "%d", &n);
    
    int p[3*100000], q[3*100000];
    for(int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    
    int sorted[3*100000 + 1];
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < n ; j++) {
            if(q[j] == i) {
                sorted[i] = p[j];
            }
        }
    }
    
    int init = 1;
    for(int i = 1; i <= n; i++) {
        //printf("sorted[%d] = %d\n", i, sorted[i]);
        if(init == 1) {
            printf("%d", q[sorted[i]-1]);
            init = 0;
        }
        else {
            printf(" %d", q[sorted[i]-1]);
        }
        
    }
}

まあ、このサイズ感で二重ループしたらそうだよなあと思い、考え直します。

少し考えて、二重ループにする必要ないじゃんと気づき、以下で提出して、ACでした。（開始後54分時点）

#include <stdio.h>

int main(void){
    char buf[100];
    fgets(buf, sizeof(buf), stdin);
    
    int n;
    sscanf(buf, "%d", &n);
    
    int p[3*100000], q[3*100000];
    for(int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    
    int sorted[3*100000 + 1];
    for(int i = 1; i <= n; i++) {
        sorted[q[i-1]] = p[i-1];
    }
    
    int init = 1;
    for(int i = 1; i <= n; i++) {
        //printf("sorted[%d] = %d\n", i, sorted[i]);
        if(init == 1) {
            printf("%d", q[sorted[i]-1]);
            init = 0;
        }
        else {
            printf(" %d", q[sorted[i]-1]);
        }
        
    }
}

正答をとれたのはここまでです。
後はD問題がぴんとこなくて、沼りました。

終わりに

最終的な結果は3問ACでの600点で、Ratingは13になりました。

タイミングと気力が合えば、今後も挑戦していきたいと思います。

素人があがいているなあという状況を見たい方は、次の記事をお待ちください。

ここまで読んでいただきありがとうございました。