こんにちは、情報系大学生のハル（Blog_IT_haru）です。
今回は、C言語でのAtCoder Beginner Contest 242(ABC242)に参加したので、自分の復習を兼ねてまとめていきたいと思います。
なお、私は灰色coderで、まださほど参加したことがありません。
超初心者ですので、備忘録的にまとめていきます。
問題
入力として文字列Sが与えられるので、Sの各文字を並び替えて得られる文字列S’のうち、辞書順で最小のものを出力する。
制約：Sは英小文字のみからなる長さ1以上2×105以下の文字列
問題ページ：B - Minimize Ordering
正解率
まだ公開されていないため、公開され次第載せます。
私の考え方
Sを受け取り、辞書順で単純に並び替えて出力します。
以下のように条件がありましたが、辞書順で出力するだけと考え、無視しました。
公式での考え方でも、無視して良い旨が書かれていたので、正しいと思います。
私のソースコード
マージソートを使用しました。
マージソートのコードは以下のコードを参考にしました。
マージソートアルゴリズム（C言語で実装） - コードワールド
ちなみに、バブルソートにすると、TLEしますのでご注意を。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void merge(char *str,char *tmpstr,int start,int mid,int end)
{
int i=start,j=mid+1,k=start;
while(i!=mid+1 && j!=end+1)
{
if(str[i] <= str[j])
{
tmpstr[k++] = str[i++];
}
else
{
tmpstr[k++] = str[j++];
}
}
while(i != mid+1)
{
tmpstr[k++] = str[i++];
}
while(j != end+1)
{
tmpstr[k++] = str[j++];
}
for(i=start;i<=end;i++)
str[i] = tmpstr[i];
}
void msort(char *str,char *tmpstr,int start,int end)
{
int mid;
if(start < end)
{
mid = start + (end - start)/2;
msort(str,tmpstr,start,mid);
msort(str,tmpstr,mid+1,end);
merge(str,tmpstr,start,mid,end);
}
}
int main(int argc,char *argv[])
{
char str[200000];
scanf("%s",str);
char *tmpstr = NULL;
tmpstr = malloc(strlen(str)*sizeof(char));
msort(str,tmpstr,0,strlen(str)-1);
printf("%s\n",str);
free(tmpstr);
}
公式の解説・考え方
以下を参照ください。
Editorial - AtCoder Beginner Contest 242
ちなみに、C++とPythonはもっとスマートなコードでした…。
Cでも、↓などはスマートなコードでした。
Submission #29866885 - AtCoder Beginner Contest 242
必要な知識
以下の知識が必要です。
※各項目をクリックすることで、該当の部分に飛べます。
・配列
scanfで値を読み取る方法
今回は、整数なので、以下の様に読み取ります。
int a;
scanf("%d",&a);
intは、型の種類の一つで、整数を取り扱います。
簡単に言うと、大きさが大きくない整数を取り扱える型です。
int型を、scanfで読み取るときの変換指定子は、dです。
変換指定子を簡単に言うと、整数を読み取るためのものです。
scanf自体は、scanf(”書式文字列”, &変数名1, &変数名2…）というふうに使用します。
書式文字列の中に、%dなどの変換指定子を書きます。
使い方は以下のような感じです。
int a;
scanf("%d",&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文の中身である足し算を繰り返すという処理を行いました。
より詳しく知りたい方は、こちらからどうぞ。
配列
配列は、ちょっとわかりにくいかもしれませんが、分かればそんなに難しくはありません。
たとえば、int a[5];と宣言された配列があるとすると、これは、aというタンスに、番号が振られた引き出しが5つあることを示しています。
また、int a[5];と宣言されているので、その引き出しには、int型のものしか入りません。
Aというタンス↓
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言語のコードでは、int main(void)のみであると思いますが、今回は、関数を用いることで、コードをわかりやすくしています。
今回の問題では、距離を求めるための、int型を返す、dist_sqという関数と、YesかNoを判定する、solveという関数を用いています。
関数は、以下のような形で作ります。
たまに、型名をvoidとして、返り値が無いものもありますが、今回は、どちらも返り値があるものとなっています。
型名 関数名(引数1,引数2,....){
/*処理*/
return 型名の型の値;
}
他に必要な知識
他にも、今回は、以下のような知識を利用します。
- while→for文と似たような感じだけど、終了条件をwhileの中に書けるので、今回はwhileを使用しています。
- #include<string.h>、#include<stdlib.h>→includeすることによって、使うことができるようになるものが増えます。
- ポインタ→C言語独自のもの。説明するとめっちゃ長くなるので、各自で調べていただけると良いと思います。
おすすめな記事
ABC238の、A,B,C問題の解説の記事もありますので、ぜひ読んでみてください。
まとめ
いかがでしたか？
A問題はやっぱりそんなに難しくないですね。
＼ほんとの初心者の方は、本で学ぶのもおすすめ！／
以下の記事でおすすめ本紹介しています！
この記事がいいな、と思ってくれたら、SNSなどで拡散したり、
ブックマークやコメントなどしてくれると励みになります！
下の方とサイドバーにある、サポートもお待ちしています！
更に、読者になってくれたら、お返しに私も読者になります！
また、この記事の内容についてなにかありましたら、
お問い合わせ、コメント、TwitterのDMなどによろしくお願いします。
それでは。
