ARC031-B 埋め立て(AtCoder精進記録)
AtCoder Regular Contest 031-B
〇問題
・'x' : 海、'o' : 陸
例:
xxxxxxxxxx xoooooooxx xxoooooxxx xxxoooxxxx xxxxoxxxxx xxxxxxxxxx xxxxoxxxxx xxxoooxxxx xxoooooxxx xxxxxxxxxx
で、一か所だけ海を埋め立て( 'x' -> 'o' )て陸地をすべて繋げるか。
〇方針
・今回も深さ優先探索
・考え方は以下の通り。
- 左上から順に、海が見つかるまで探す。海なら埋め立て 。
- つながっている陸地を数え上げる(深さ優先探索)。
- (元の陸地の数 + 1)まで数えられたら全ての陸地がつながっていると判断。陸地の数が少なければ、埋め立てた海を元に戻し、1.に戻る。
・前回(
ATC079-A 深さ優先探索(Atcoder精進記録) - 胡瓜のプログラミング日記
)のソースコードを流用。
#include <stdio.h> #include <stdbool.h> #define Row 10 #define Column 10 void dfs(int x,int y); void initialize( bool reached[Row][Column] ); int i,j; char A[Row][Column]; bool reached[Row][Column]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int flg = 0; int riku_count=0,srow,scolumn,count=0; int main(){ for(i=0;i<Row;i++){ scanf("%s",A[i]); } for(i=0;i<Row;i++){ for(j=0;j<Column;j++){ if( A[i][j] == 'o' ){ riku_count++; if( flg == 0 ){ srow = i; scolumn = j; flg++; } } } } if( riku_count == 100 ){ printf("YES\n"); return 0; } for(i=0;i<Row;i++){ for(j=0;j<Column;j++){ if( A[i][j] == 'x' ){ A[i][j] = 'o'; dfs(srow,scolumn); if( count == riku_count + 1 ){ printf("YES\n"); return 0; } A[i][j] = 'x'; count = 0; initialize(reached); } } } printf("NO\n"); return 0; } void dfs(int x,int y){ if( x < 0 || Row <= x || y < 0 || Column <= y || A[x][y] == 'x' ){ return; } if( reached[x][y] == true ){ return; } if( A[x][y] == 'o' ){ count++; } reached[x][y] = true; dfs(x+1, y); dfs(x-1, y); dfs(x, y+1); dfs(x, y-1); } void initialize( bool reached[Row][Column] ){ int a,b; for(a=0;a<Row;a++){ for(b=0;b<Column;b++){ reached[a][b] = false; } } }
〇所感
・深さ優先探索も、単純な奴は大丈夫そう。
・競プロ以外も勉強しているので、そのうち。
・「Atcoder」⇒「AtCoder」に修正。
〇参考記事
・AtCoder 版!蟻本 (初級編) (問題の選択)
ATC079-A 深さ優先探索(Atcoder精進記録)
Atcoder Typical Contest 001-A
〇問題
・'#' : 塀、's' : スタート、'g' : ゴール、'.' : 道
s#### ....# ##### #...g
で、スタートからゴールにたどり着けるか出力。
〇方針
・問題の名前通り、深さ優先探索
#include <stdio.h> #include <stdbool.h> #define Hmax 500 #define Wmax 500 void dfs(int x,int y); int i,j,H,W; char c[Hmax][Wmax]; bool reached[Hmax][Wmax]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int flg = 0; int main(){ scanf("%d%d",&H,&W); for(i=0;i<H;i++){ scanf("%s",c[i]); } for(i=0;i<H;i++){ for(j=0;j<W;j++){ if( c[i][j] == 's' ){ dfs(i,j); } } } if( flg == 1 ){ printf("Yes\n"); }else{ printf("No\n"); } return 0; } void dfs(int x,int y){ int a,b,k; if( x < 0 || H <= x || y < 0 || W <= y || c[x][y] == '#' ){ return; } if( reached[x][y] == true ){ return; } if( c[x][y] == 'g' ){ flg = 1; } reached[x][y] = true; for(k=0;k<4;k++){ a = x + dx[k]; b = y + dy[k]; dfs(a,b); } }
〇所感
・深さ優先探索自体は知っていたが、一から実装したことはあまりなかった。やはり知っているのと実装できるのは違う。
・今回は、四方向の探索にfor文を用いたが、変数kをi,jと同様にグローバル変数としてしまい、何度もWA。dfs(x+1,y)のように書くほうが無難かも。
・次回もDFS。
〇参考記事
・AtCoder 版!蟻本 (初級編) (問題の選択)
ABC079-C Train Ticket(Atcoder精進記録)
Atcoder Beginner Contest 079-C
〇問題
・0以上9以下の4つの整数の間に ’+’ か ’-’ を入れて計算式を作り、その値が 7 になるものを出力。
〇方針
・8通り全部試すほうが早いが、あえてbit探索を使う。
#include <stdio.h> #include <stdlib.h> int main(){ int A[4],i; char s[4]; scanf("%s",s); for(i=0;i<4;i++){ A[i] = s[i] - '0'; } int j,sum; char op[3]; for(i=0;i<8;i++){ sum = A[0]; for(j=0;j<3;j++){ if( i & ( 1 << j ) ){ op[j] = '+'; sum += A[j+1]; }else{ op[j] = '-'; sum -= A[j+1]; } } if( sum == 7 ){ break; } } for(i=0;i<3;i++){ printf("%d%c",A[i],op[i]); } printf("%d=7\n",A[3]); return 0; }
〇所感
・bit探索は理解したはず。
〇参考記事
・AtCoder 版!蟻本 (初級編) (問題の選択)
ABC045-C たくさんの数式(Atcoder精進記録)
Atcoder Beginner Contest 045-C
〇問題
・1以上9以下の数字からなる文字列Sについて、文字の間のうちいくつかに'+'を入れて作ることができる数式の値の総和を求める。
・1<= |S| <= 10
〇方針
・Sの文字の間それぞれについて、'+'を入れるか入れないかの2通り。
・文字の間('+'を入れることができる箇所)の数はn-1( n = |S| )
⇒通りの全探索
⇒今回は、bit探索を利用
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(){ char s[11]; scanf("%s",s); int i,j; long long ans=0; long long tmp; // ’+’で分割したものを代入 for(i=0;i<( 1 << ( strlen(s) - 1 ) );i++){ // S="125"なら、i=(00)_2~(11)_2まで。 // strlen(s) にすると、i=(111)_2までになる。 tmp = s[0] - '0'; // Sの1文字目を数値に変換して代入 for(j=0;j<( strlen(s) - 1 );j++){ if( i & ( 1 << j ) ){ // 例:(i,j)=(0,1) ⇒ (00) AND (10) ans += tmp; // ⇒ (10) ⇒ 12 + 5 tmp = 0; // 分割した分を足して、tmpを初期化 } tmp = tmp*10 + (s[j+1] - '0'); } ans += tmp; // 最後の分割部分を足す。 } printf("%lld",ans); return 0; }
〇所感
・コンテストでbit探索の問題が出たときは、よくわからなくて理解を諦めていた。今回で理解できたはず。
・'+'によるSの分割方法に苦労した。結局、ASCIIコードを用いて数値に変換することにした。
・String型ほしい……仕事ではJavaを使うし、そのうちC言語から移行するかも。
〇参考記事
・AtCoder 版!蟻本 (初級編) (問題の選択)
・bit全探索 - whileD'iary (実装方法)
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; }
プログラミングスクールに通っていたという話
こんにちは。
少し前に、プログラミングスクールの是非についてtwitterで話題になっていたようなので、私の経験から感じたことを書いていきます。
結論から言いますと、
「作りたいものがあるなら行ってみてもよい。『とりあえずプログラミングを学びたい』なら厳しい。通うなら、メンター・教材を徹底的に自分から使い尽くす気持ち・行動が必要」
だと思います。
私は、とある有料プログラミングスクールに1か月ほど通っていたのですが、結局、既存サイトの模倣版みたいなのをカリキュラムに沿ってつくるだけで終わりました。得るものもありましたが、値段ほどのものを回収することは(まだ)できていません…
詳しく見ていきます。
1.いわゆる「プログラミングスキル」を鍛えるのはほんの一部
私の場合、大学の授業で少しだけ触れたプログラミングが楽しかったのと、内定先でプログラミングスキルが必要になりそうだったので、今のうちにプログラミングスキルを高めておきたいと思って、通い始めました。何かを作りたいというのはあまりなくて、やっていくうちに見つかればいいかなという感じでした(そもそもそれが甘すぎた…)。今思うとほんとに適当ですね…
ガリガリコードを書いていくのかなぁと思ってカリキュラムを進めていったのですが、簡単な文法について学んだあとは、少しだけ練習問題を解いて終わりでした。そのあとは、実際にWebアプリをつくるために必要なフレームワークの説明に入りました。
明確に作りたいものがある人にとっては「いよいよか!」という感じだと思いますが、私の場合は、もっといろいろ問題を解きたいなと思っていたので、「え、もう?」と感じました(自分でやれよって話になりますが)。今思うと、下調べが足りなすぎますね。
開発における、いわゆるコーディングというのはあくまで一部分だということだと思います。
2.メンターは生徒を放置。質問・相談は全部自分から。
メンターとして、2~3人の学生アルバイトの方が教室にいましたが、基本は自分の作業をしていて、向こうから生徒に声をかけるということはなさそうでした。
今でこそ、独学で学んでいますし、わからないことは自分から聞く・調べるというのは当たり前という感覚です。エンジニアとして食べていくなら、身につけなければならない考えです。大学の授業なんかもそうですよね。
しかし、明確に「メンター」がいるという状況で、あそこまで完全に生徒任せというのは、完全初心者には厳しいのかなと…。全くの実務未経験からエンジニアになろうとしていて、プログラミングスクールに頼ろうという人に最初からそれを求めるのは酷じゃないかなあと感じています。そこでガンガン質問して、自分で調べて進めていける人は、おそらくプログラミングスクールに通わなくてもできちゃうひとではないかと。笑
少なくとも初期のうちはもう少しフォローがあってもいいと思います。ただ、それも結局、スクール側がどういう人をどのレベルまで育てたいのかによると思うので、単純に良し悪しを判断するのも難しいですね。
3.(人によっては)世界が広がる経験ができる
上の二つで、ネガティブなことを書いてしまったので、ここからはポジティブなことを。
表題の通りですが、「こういう人たちがいるんだ、こういう世界があるんだ」という気づきがありました。
twitterを始めてからもそうですが、なにも行動せずになんとなく暮らしているだけだと出会えない世界がありました。大袈裟ですかね……。
私自身が内気なのもあって、それまでは非常に狭い世界で満足していましたが、そこは「ベンチャーでインターン」や「個人でサービスをつくる」みたいなこととは無縁の世界でした。
しかし、このスクールに通ったのをきっかけにして、独学でプログラミングを学ぶ覚悟ができましたし、いずれは個人で食べていきたいと思うようになりました。twitterをはじめ、こうしてブログなんかも書いています。そういった意味では、得るものはあったのかなと思います。プログラミングスクールがきっかけである必要はないことばかりですが笑
というわけで、いろいろ書いてきましたが、結局は、
「自分がなにをしたいのか、なにをつくりたいのか」を明確にして、その手段としてプログラミングスクールを考える
というのが大切だということだと思います。
なにか作りたいサービスがあるのか、それともただガリガリコードを書いてみたいだけなのか。まずはそれを明確にすること。そしてそのために必要なスキル・環境を得るのに、自分でやるよりもプログラミングスクールを頼った方が効率がよいなら通う価値はあります。
なにをしたいのか明確にならないという人は、なんでもいいから少しだけ自分で勉強してみるのがいいかと思います。私の場合は(その勉強がプログラミングスクールそのものになってしまったわけですが笑)、自分は(今のところは)なにかを作りたいのではなく、コードを書くこと自体が好きなんだと気づくことができました。
「1か月でエンジニアに!」「無料で就職までサポート!」なんかの甘い言葉に誘われていくようなら絶対にやめたほうがいいです……
ではでは。