Atcoder茶色の初心者が初心者でもわかるようにA~C問題を解説(しようと)してみた(ABC098)
こんにちは。
内定者研修~新人研修で学んだC言語を配属先の業務で一切使わない(どころか使う部署はほぼない)ことが判明しました。
Javaを勉強中な胡瓜です。
内定者時代からちょこちょこC言語で取り組んでいたAtcoderですが、C問題まではいつも解ける程度に落ち着いてきました。
しかし、いつまでたっても、C問題を解き終えるころには時間ギリギリという状況からは抜け出せず、D問題の時間内ACはまだまだ難しそうです。
そんななか、Atcoderの解説が分かりづらい的な話をtwitterで見まして。
私自身も「省略し過ぎ……」と思うときもあり、本当に初心者だと全然わからないこともあるのではと(それをググって調べるのも勉強の一部だとは思いますが)。
ということで、C問題までの自分の思考を整理するついでに解説的なことができればと思いまして、久々に更新します。
変なところがあればどしどし指摘頂きたいです。
1.筆者の実力
コンテスト参加回数:9回(Ratedのみ)
レート :594(2018/05/29現在)
最高パフォ:1129(ABC097)
レート推移
〇A問題
この問題は、2つの整数AとBの足し算、引き算、掛け算を計算して比較すればよいです。
やり方はいろいろありそうですが、私は何も考えずそのまま比較してしまっています。
#include <stdio.h> int main() { int A,B,max; scanf("%d%d",&A,&B); if( A*B >= A+B ){ if( A*B >= A-B ){ max = A*B; //(1) }else{ max = A-B; //(2) } }else{ if( A+B >= A-B ){ max = A+B; //(3) }else{ max = A-B; //(4) } } printf("%d\n",max); }
順に説明していきます。
まず、最初のif文でA*B と A+B を比較します。
例えば、 A*B > A+B だったら、次の行のif文で A*B と A-B を比較します。
そこで A*B > A-B であったら、A*B を int型の maxに入れます。その後、最後のprintf文までとんで、maxを出力します。変数に入れず、そのまま出力してもよいでしょう。
ポイントは、あくまで最大値さえわかればよいというところでしょうか。
上の例でいうと、A-B と A+B の大小の比較は必要がありません(3つの数の大小関係自体は6通りあります(※6=3×2×1)が、例えば上の(1)は、A*B > A-B > A+B と A*B > A+B > A-B の2通りを含んでいます。同様に、(3)も2通り含んでいますので、合計6通りで、すべての場合を考慮できていることになります)。
※大小関係が6通り
3つの数x、y、zを並べ替えるとき、3つのうちひとつを先頭に並べるのは3通り。2番目に並べるものは残りの2つからひとつ選ぶ2通り。3番目は残ったひとつで1通り。
〇B問題
この問題は、最初に見たとき「B問題にしては実装量多くならん?」と考えてしまい、余計に時間を使ってしまいました。
解説からは外れますが、B問題までは、愚直にやれば多分問題ありません。余計なことを考えずにいきましょう(と自分に言い聞かせる)。
さて、長さNの文字列Sを切断し、文字列Xと文字列Yにしたとき「XとYのどちらにも含まれている文字」の種類数の最大値を求めよ、という問題です。
なにかうまい数え方があるのかなーと思ってしまいますが、思い出しましょう、これはB問題です。愚直にやればおーけーです。つまり、前から順に切断して、その都度文字を調べるというやり方です。上記URLにある「入力例1」を例にして考えます。
入力例1
6 aabbca
まず、1番目のaと2番目のaの間で切りましょう。
a | abbca
このとき、左の文字列にも右の文字列にも含まれている文字は 'a' のみです。したがって、この場合の「XとYのどちらにも含まれている文字」は1種類となります。
次に、2番目のaと3番目のbの間で切り、もっと細かく考えていきましょう。
aa | bbca
順番に行きます。
まず、右側の文字列(Y)の1番目、すなわち 'b' と一致するものが、左側の文字列(X)の中にないかを調べます。
Xの1番目は 'a' 。一致しません。
Xの2番目は 'a' 。これも一致しません。
Xの文字列は長さが2しかないので、この 'b' との比較は終了です。
次は、Yの2番目の 'b' とXを比較して……というように考えていきます。
↓ ↓ // 右側の文字列Yの1番目と左側の文字列Xの1番目を比較。 aa | bbca
↓ ↓ // 右側の文字列Yの1番目と左側の文字列Xの2番目を比較。 aa | bbca
↓ ↓ // 右側の文字列Yの2番目と左側の文字列Xの1番目を比較。 aa | bbca
比較が進み、文字列Yの最後、'a' と文字列Xの比較に入ったとしましょう。
↓ ↓ // 右側の文字列Yの4番目と左側の文字列Xの1番目を比較。⇒文字が一致! aa | bbca
このとき、どちらも 'a' で一致しました。次に、最後の比較に移ります。
↓ ↓ // 右側の文字列Yの4番目と左側の文字列Xの2番目を比較。⇒文字が一致!でもカウントしない aa | bbca
こちらも二つの文字が一致しました。しかし、'a' はすでにひとつ前の比較でカウントしています。今回は文字の「種類数」をきかれているので、ここではカウントせず、一致した文字の種類数は1種類のままとなります。
ここまでの手順をまとめましょう。
(1) 文字列を左端で分割 (2) 文字列Y(右側)の先頭文字に着目 (3) 文字列Xの1番目の文字と文字列Yの先頭文字を比較⇒文字列Xの2番目の文字と文字列Yの先頭文字を比較⇒……⇒文字列Xの最後尾の文字と文字列Yの先頭文字を比較 (4) 文字列Yの2番目の文字に着目 (5) 文字列Xの1番目の文字と文字列Yの2番目の文字を比較⇒文字列Xの2番目の文字と文字列Yの2番目の文字を比較⇒……⇒文字列Xの最後尾の文字と文字列Yの2番目の文字を比較 : : (6) 文字列Yの最後尾の文字に着目 (7) 文字列Xの1番目の文字と文字列Yの最後尾の文字を比較⇒文字列Xの2番目の文字と文字列Yの最後尾の文字を比較⇒……⇒文字列Xの最後尾の文字と文字列Yの最後尾の文字を比較 (8) 分割位置をひとつ右にずらす。 以下、繰り返し
となります(丁寧に書き過ぎましたかね…)。
これらをコードで書いたものがこちら。
#include<stdio.h> int main() { char s[100]; int N; scanf("%d",&N); scanf("%s",s); int alpha[1000]; //既にカウントしたアルファベットかの判定用(1000は多すぎ) int i,j,k,count=0,count_max=0; for(i=1;i<N;i++){ // 分割位置を左端(1番目と2番目の間)から count=0; // 右端(最後尾の手前)まで。 for(j=0;j<1000;j++){ // カウントしてないアルファベットは alpha[j]=0; // alpha=0になるように初期化。 } for(j=i;j<N;j++){ // 文字列Yの先頭から最後尾。 for(k=0;k<i;k++){ // 文字列Xの先頭から最後尾。 if(s[j]==s[k] && alpha[s[j]]==0){ // s[j]:Yの文字 s[k]:Xの文字 count++; // alpha[Yで着目中のアルファベット]=0 ⇒未カウント。 alpha[s[j]] = 1; //カウント済み(alpha[]=1)に変更。 } } } if(count>=count_max){ count_max=count; } } printf("%d\n",count_max); return 0; }
for文での処理自体は、上に記した手順と見比べてもらえばわかると思います。
ここでは、解説pdfで少しだけ触れていたASCIIコードを用いた部分を解説します。
ASCIIコードというのは、簡単に言えば、’A'⇔65、'a'⇔97 というように、数字と文字・記号を対応させたものです。
したがって、上のコードの「 if(s[j]==s[k] && alpha[s[j]]==0)」で、s[j]='a' だったとすると、
s[j]==s[k] && alpha[s[j]]==0
⇔ 'a'==s[k] && alpha['a']==0
⇔ 97==s[k] && alpha[97]==0
となります。つまり、alpha[1000]のうち、各アルファベットに対応した数字を添え字にもつ要素が0か1かで、そのアルファベットが一致したときにカウントするかどうかを判断しているのです。
このようにASCIIコードを使うと処理が簡単になる問題というのはたびたび見かけるので、理解しておきましょう(アルファベット毎に個数を数える など)。
〇C問題
N人のひとがそれぞれ東('E')か西('W')のどちらかを向いて一列に並んでいます。誰かひとりを指名したとき、残りの人は、リーダーの方を向くように向きを変えます。その最小人数を求めよ、という問題です。
入力例1を例に考えてみます。
↓ WEEWW
素直に考えてみます。左端(一番西)の人をリーダーとすると、他の4人は全員西('W')を向く必要があります。したがって、向く方向を変える人は、'E'を向いている2人となります。
次に、西から2番目の人をリーダーにします。このとき、西から1番目の人は東を向く必要があり、東から3番目の人は西を向く必要があります。したがって、向く方向を変える人は2人となります。
というように、「西から順にリーダーに任命していき、その都度方向を変える人を数えて」いけばよいと考えられます。B問題に似てますね。
この考えにもとづいたコードがこちら。
#include <stdio.h> int main() { int N; scanf("%d",&N); char s[N]; scanf("%s",s); int i,j,count_w,count_e,count_min=4000000; for(i=0;i<N;i++){ //「西から順にリーダーに任命していき」 count_w = 0; count_e = 0; for(j=0;j<i;j++){ //「方向を変える人を数えて」リーダーより西 if( s[j] != 'E' ){ count_w++; } } for(j=i+1;j<N;j++){ //「方向を変える人を数えて」リーダーより東 if( s[j] != 'W' ){ count_e++; } } if( count_min >= ( count_w + count_e ) ){ count_min = count_w + count_e; } } printf("%d\n",count_min); return 0; }
そして提出結果は……
TLE
つまり、時間切れです。
経験上、C問題は素直にやるだけではTLEになることが多い気がします。
この場合の修正方針は、N^2 ⇒ N です。簡単に言うと、「二重ループをなくそう」です。計算量の細かい話は省略しておきますが、for文をi=1~Nで回すとすると、二重ループは計算量がN^2となり、Nの増加によって計算量が爆発的に増えてしまいます。
それでは、先ほどの考え方で二重ループを生じさせているところはどこでしょうか。
まず、「西から順にリーダーに任命していき」です。リーダーを西から順に指名していくので、for(i=0;i
↓ //リーダーは'W'、右隣は'E' WEEWW
↓ //リーダーは'E'(東側から'E'がひとり減少)、西側に'W'がひとり増加。 WEEWW
つまり、リーダーを東にひとり分ずらしたとき、リーダーとそのすぐ東にいる人の向きしか変わりえないことになります。したがって、最初に'W'の人と'E'の人それぞれの人数を求めれば、あとは足し算引き算で計算できます。
#include <stdio.h> int main() { int N,i; scanf("%d",&N); char s[N]; scanf("%s",s); int c_w=0,c_e=0; for(i=0;i<N;i++){ if(s[i]=='E'){ c_e++; //東を向いている人の合計 }else{ c_w++; //西を向いている人の合計 } } int change_min=4000000; //change_w:リーダーの西側で向きを変える人数 int change_w = 0; //最初は全員リーダーよりも東にいると仮定 //change_e:リーダーの東側で向きを変える人数 int change_e = c_e; // for(i=0;i<N;i++){ if(s[i]=='E'){ change_e--; //リーダーが'E'の場合、東側から'E'が1人減る } if(change_e+change_w <= change_min){ change_min = change_e+change_w; } if(s[i]=='W'){ change_w++; //リーダーが'W'の場合、西側に'W'が1人増える } } printf("%d\n",change_min); return 0; }