はるのぶろぐ。

情報系大学生ハルが、ゆるゆるとIT関係についてや日々の雑記を綴ります。ちょっとだけ、あなたの役に立てる、そんなブログを目指しています。

【AtCoder】超初心者のためのAtCoder Beginner Contest 245B問題の解説【C言語】【ABC245】

参加してます!ポチッとお願いします

記事名と
URLをコピー

こんにちは、情報系大学生のハル(Blog_IT_haru)です。

今回は、C言語でのAtCoder Beginner Contest 244(ABC244)に参加したので、自分の復習を兼ねてまとめていきたいと思います。

なお、私は灰色coderで、まださほど参加したことがありません。

超初心者ですので、備忘録的にまとめていきます。

f:id:Blog_IT:20220327203603p:plain

問題

B問題

入力として、長さ N の整数からなる数列 A=(A1,…,AN)が与えられる。

A1​,…,ANに含まれない最小の非負整数を求め、出力する。

制約:1≤N≤2000、0≤Ai​≤2000、入力は全て整数である。

問題ページ:B - Mex

正解率

まだ公開されていないため、公開され次第載せます。

私の考え方(AC取れず)

コンテスト中に、AC取れなかったので、コードは載せませんが、考え方のみ載せておきます。

※私の備忘録なため、公式の考え方を知りたい方は、飛ばしてくれて構いません。

配列aを入力として受け取り、整数を比べるため、for文で0~2000までの配列bを作る。

aをソートし、0を1つのみ残して、重複がある数字も削除する。

その後、bと比べて、該当する数を探す。

公式の解説・考え方

0,1,…,Nに整数はN+1個あるので、答えの上限はNであるため、ans=0,1,2,…,NについてA にansは含まれるか?という問題を順番に解いていき、最初に含まれない値が見つかった時、その値を答えとすれば良い。(Editorial - AtCoder Beginner Contest 245

公式の考え方、C++のサンプルコードは、Editorial - AtCoder Beginner Contest 245からご確認ください。

以下は、サンプルコードを参考に、C言語でACをとったコードになります。

公式の考え方のコード

#include <stdio.h>
#include <stdbool.h>
typedef long long ll;
int main(void){
    ll n;
    scanf("%lld",&n);
    ll a[n];
    for(ll i=0;i<=n-1;i++) scanf("%lld",&a[i]);
    for(ll ans=0;ans<=n;ans++){
        bool ok=true;
        for(ll i=0;i<=n-1;i++){
            if(a[i]==ans) ok=false;
        }
        if(ok){
            printf("%lld",ans);
            return 0;
        }
    }
    return 0;
}

必要な知識

以下の知識が必要です。

※各項目をクリックすることで、該当の部分に飛べます。

scanfでの値の読み取る方法

if文の使い方

printfの使い方

for文の使い方

配列

その他必要な知識

scanfで値を読み取る方法

整数の場合、以下の様に読み取ります。

    int a;
scanf("%d",&a);

intは、型の種類の一つで、整数を取り扱います。

簡単に言うと、大きさが大きくない整数を取り扱える型です。

int型を、scanfで読み取るときの変換指定子は、dです。

変換指定子を簡単に言うと、整数を読み取るためのものです。

scanf自体は、scanf(”書式文字列”, &変数名1, &変数名2…)というふうに使用します。

書式文字列の中に、%dなどの変換指定子を書きます。

※今回は、long long型なので、%lldですね。

使い方は以下のような感じです。

long long a;
scanf("%lld",&a);

if文の使い方

過去に、if文について書いていた記事がありましたので、一部引用しました。

ifという文字通り、「~なら~する」という、条件で処理を実行するか否か決めることができます。

次のように使います。

if (条件式) 処理 ;

または、

if(条件式){
  処理;
}

です。

(引用元:C言語で最大値を求める - ハルの初心者プログラミング部

ただ、私の考え方で解く場合はelse ifの知識も必要です。

以下のように使用します。

ifは最初の1つだけ、elseも最後の1つだけですが、else ifは何回でも使用することができます。

    if(条件式){
        /*実行すること*/
    }
    else if(条件式){
        /*実行すること*/
    }
    else{
        /*実行すること*/
    }

printfの使い方

過去に、printfについて書いていた記事がありましたので、一部引用しました。

printfは、文字列を表示するための関数です。

普通は、以下のように、文字列を記述するのですが、今回は整数の計算結果を記述したいので、少し違う書き方になりましたね。

普通の文字列の場合

printf("tameshi");

整数の場合

printf("%d",sum);

このとき出てきた、%dのdが、変換指定子dです。

%d

printf内で使います。

整数を10進数で出力します。

int型に対応します。

使用例

printf("%d",10);

この場合、10と出力されます。

\n

printf内で使います。

改行を行います。

先程の変換指定子の前か後に記入します。

前に記入した場合は前が改行され、後ろに記入した場合は後ろが改行されます。

今回も、見やすく出力するために、使用しました。

printf("\n%d",sum);

こんな感じですね。

(引用元:C言語で合計値を求める - ハルの初心者プログラミング部

for文の使い方

同じ処理を繰り返したいときに使用する関数です。

似たような機能をもつ関数として、while文もありますが、今回は、省略します。

for文は、以下のように記述します。

for(初期値;繰り返し条件;変化式){
繰り返したい動作
}

今回はi=0から、i<5のときfor文の中身である足し算を繰り返すという処理を行いました。

より詳しく知りたい方は、こちらからどうぞ。

繰り返しを行う文 - 苦しんで覚えるC言語

配列

配列は、ちょっとわかりにくいかもしれませんが、分かればそんなに難しくはありません。

たとえば、int a[5];と宣言された配列があるとすると、これは、aというタンスに、番号が振られた引き出しが5つあることを示しています。

また、int a[5];と宣言されているので、その引き出しには、int型のものしか入りません。

Aというタンス↓

f:id:Blog_IT:20220207105015p:plain

a[0]~a[4]と添字が書かれた配列が存在します。

int a[5];と宣言しているので、添字は0,1,2,3,4です。

5つの引き出しがありますが、a[5]という添字の入れ物は無いことに注意しましょう。

int a[5] = {1,2,3,4,5};と宣言した場合、a[0]には1が、a[1]には2が、といった感じでそれぞれ値が入っています。

ただし、AtCoderなど、入力する値がある場合は、{}のように事前に値を入れずに、以下のようにして配列を使うことが多いです。

事前に値を入れておくことを、初期化と言います。

    int a[5];
for(int i=0;i<5;i++){
scanf(“%d”,a[i]);
}

これはfor文でi、すなわち添字を0から4まで増やしていき、値を入れているということです。

この場合、入力が1 2 3 4 5とされていれば、値がそれぞれ入っていきます。

ただ、スペースが有る場合、scanfの%dの後ろにスペースを開けないといけませんのでご注意を。

配列について、もう少し詳しい説明が知りたい方は、以下のサイトがおすすめです。

配列の使い方 - 苦しんで覚えるC言語 [MMGames]

その他必要な知識

他にも、今回は、以下のような知識を利用します。

  • long long→intより大きい値もOKなものです。
    オーバーフローするほど大きい値を使っているときなどは、intだとだめなため、利用します。
  • #include <stdbool.h>でincludeし、bool型を用いています。
    boolは簡単にいうと、trueやfalseの型のものになります。
    詳しく知りたい方は、以下のサイトがおすすめです。

    H - 1.07.条件式の結果とbool型

  • typedefは、既存のデータ型に新しい名前を付けるために用いています。
    long longをいちいち書くのがめんどくさいので、llとしている、ということになりますね。

おすすめな記事

ABC238~245の、A,B,C問題の解説の記事もありますので、ぜひ読んでみてください。

※A問題のみやA問題とB問題のみの場合もあります。

blog-it.hatenablog.com

まとめ

いかがでしたか?

B問題でしたが、少し複雑だったかな、という印象です。

\ほんとの初心者の方は、本で学ぶのもおすすめ!/

以下の記事でおすすめ本紹介しています!

blog-it.hatenablog.com

この記事がいいな、と思ってくれたら、SNSなどで拡散したり、

ブックマークやコメントなどしてくれると励みになります!

下の方とサイドバーにある、サポートもお待ちしています!

更に、読者になってくれたら、お返しに私も読者になります!

また、この記事の内容についてなにかありましたら、

お問い合わせ、コメント、TwitterのDMなどによろしくお願いします。

それでは。