AtCoder Beginner Contest164 に参加しました！
先ほど行われたAtCoder Beginner Contest 164に参加してきました。
結果は今回も茶色にはなれず・・・
今回も解いた感想を書いていきます。
ちなみに前回の記録です。
developer-bpeldi2oerkd8.hatenablog.com
準備
まだ、ブログの記事にはできていないのですが、前回からはDFSとBFSの問題を複数解いてABC164に臨みました。
前回の反省から、D問題を解くことが重要だと思っていたので、その中でも重要なBFSとDFSを勉強していきました。
（本当は他にも勉強していきたかったんですけど、バタバタしていたので・・・）
またもや、今回出ませんでした。
経過
今回はしっかり対策してくださったのか、出だしがかなりスムーズに動いていました。
（AtCoder社さんありがとうございます）
いつものようにA問題をさっと解き、B問題にとりかかったのですが、なぜかB問題で手間取りました。
（ブランクでしょうか、悲しい）
ここで、C問題を早解きすることで挽回しようと思ったのですが、今回のC問題はSetを使えばすぐ解ける問題だったので、
B問題の遅れが足を引っ張ってしまったままになってしまいました。
D問題は半分以上のテストケースを通したのですが、2019の倍数が文字列の長さ20万までだとlongに収まらないことに途中で気づき、BigIntegerを使って書き直しましたがTLE・・・
解答を見ると、数学的知識＋DP出ないと解けなかったらしく、正解者も今回少なかったみたいですね・・・
結果として、B問題の遅れがかなり足を引っ張る結果となってしまいました。
結果的に順位表を見る限り、ほとんどの人にとっては今回はA～C問題のスピード勝負だった感じがします。
結果
A～C問題の3完で、20分で解きました。
今回は順位表を見る限りかなりの団子状態のようです。
今回、D問題を解けなかったのは難しかったのでしょうがないですね。
こういう回もだいぶまれだと思うので、引き続きD問題の勉強をしていきます。
というわけで、ABC164の結果でした。
ところで、なぜ毎回茶パフォ出してるのに、こんなに上がり方が緩やかなんですかね？
とにかく、まだコンテストでD問題を解けた経験がないので、解けるように頑張ります。
DFSについて
お久しぶりとなってしまいました。
最近バタバタしていて、ブログに手が付きませんでしたが、これから元のペースに戻したいと思います。
さて、今回はずいぶん前に書くと言っていたDFSについて書きたいと思います。
ちなみに前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
DFSとは
DFSとは「深さ優先探索」の略です。深さ優先探索は、グラフなどの深いところを優先してたどっていく方法です。
よくBFS（幅優先探索）と比較されます。
この2つの使い分けなんですが、ただ探索の順番が違うだけなので、極論どちらでも解けると思います。
ですが、明らかにBFSにしたほうがいいという問題があります。
それが、最短距離を求める問題です。
ほかにも、メモリの使用量などの違いがあるみたいです。
(https://pyteyon.hatenablog.com/entry/2019/03/01/211133より)
とにかく、基本はDFSで解き、「最短」などのワードが出たときはBFSで解けばいいようです。
どのように解くのか（Javaの場合）
DFSを使う問題は主に2種類あります。１つが、配列を使う問題、もう1つがグラフを使う問題です。
配列を使う問題は下の図にあるような格子状の環境の時に使います。
このときにint env = new int[height][width]という風にして、情報を保存します。
この問題の解き方は、下のような感じです。
DFSでは、スタックを使います。
Deque<Point> stack = new ArrayDeque<>(); stack.push(スタート地点); List<Point> direction = new ArrayList<>(); Point down = new Point(-1, 0); Point left = new Point(0, -1); Point up = new Point(1, 0); Point right = new Point(0, 1); while(!stack.isEmpty()) { Point p = stack.pop(); int h = p.h; int w = p.w; //訪問済み visited[h][w] = true; //終了条件 if(条件) { //処理 break; } direction.clear(); if(h-1 >= 0) direction.add(down); if(w-1 >= 0) direction.add(left); if(h+1 < H) direction.add(up); if(w+1 < W) direction.add(right); for(Point dir : direction) { int n_h = h + dir.x; int n_w = w + dir.y; Point n_p = new Point(n_h, n_w); if(!stack.contains(n_p) && !visited[n_h][n_w] && 壁などの条件) { stack.push(n_p); //処理 } } }
グラフを使う問題はグラフと問題文に書いてあったり、図が載っているのですぐにわかります。
下のようなグラフの時、自分で作ったグラフクラスを用いて、Graph g = new Graph(N)のようにし、情報を保存します。
この問題の解き方は、下のような感じです。
使ったライブラリについては、後で紹介します。
ちなみに、これはB - バウムテストのACした自分の解答の一部です。
while(n.size() > 0) { Deque<Node> stack = new ArrayDeque<>(); stack.push(n.get(0)); boolean isTree = true; //ここが深さ優先探索 while(!stack.isEmpty()) { Node node = stack.pop(); //訪問済み node.visited = true; n.remove(node); for(int i=0; i<node.edges.size(); i++) { Node toNode = node.edges.get(i).to; if(!stack.contains(toNode)) { if(!toNode.visited) { stack.push(toNode); toNode.root = node; }else if(!node.root.equals(toNode)) { //閉路判定 isTree = false; } } } } }
やはり、深さ優先探索の本体を書くのは慣れればすぐなんですが、条件と中の処理で高確率でバグりますね・・・
ここら辺は練習が必要なようです。
使ったライブラリ
使ったライブラリは自作のものです。
いろんなサイトを参考にして、自分で作りました。
こちらのサイトに載せてあるので、よかったら目を通してください。
github.com
今後もこちらに載せていこうと思います。
webの作った作品もこちらに載せようと思います。
ということで、今回もatcoderの記事でした。
正直、書きたいことがたまっていて、あとBFSとWeb開発のことを書きたいです。
このあと、21時からABCが始まるので、結果を残せるように頑張ります。
ABCの結果はこの後載せる予定です。
AtCoder Beginner Contest 163に参加しました
先ほど行われたAtCoder Beginner Contest 163に参加しました。
今回はなんとUnratedと言って、contest自体が無効になってしまいました・・・。
やはり最近急速にAtcoderをしている人が増えているなと感じてます。
なので、サーバー自体が耐えられなくなってきているのだと思います。
（Atcoder社さんにはサーバーの増強を頑張ってほしいです！）
Unratedと分かった瞬間に急速にやる気がなくなってしまって、今回のD問題はまだ勉強していない余り系の問題だったこともあり、そこで終えたのですが、そこに至るまでの経過とかを今回は振り返ります。
準備
前回は安定のC問題までは解けたのですが、C問題までの早解きだけでは限界を感じたので、D問題に向けた勉強が必要だと感じました。
なので、まずは基本である全探索から学習し、DFSの一部まで取り組みました。
DFSについては次回（か次々回）記事にまとめるつもりなので、見てもらえると嬉しいです。
まとめると、前回から今回の間までに勉強したのは以下の3つです。
・bit全探索
・順列全探索
・DFS（の一部）
経過
まず、問題ページを開こうとした瞬間、500のサーバーエラーが出ました。
焦ってAtCoderのサイトに入りなおそうとしたところ、502のサーバーエラーが出ました。
この時点で今回はUnratedかな・・・と思いつつ、5分後くらいに再び入れたので、A～C問題を早解きしました。（全部で20分くらい）
しかし、C問題が終わってA問題の結果を見ると、IE（内部エラー）と出ていました。
Aの各テストケースはすべてAC（正解）なのにおかしいなと思って、質問タブを見たところ、Unratedのお知らせがありました。（悲しい）
D問題を見てもまだ勉強していない余り系の問題で、Unratedだったこともあり、早めに退散しました。
順列全探索について
今回は再びAtCoderの記事。
いよいよAtCoder Beginner Contest 163が近づいてきたので、AtCoderの勉強をしてました。
前回のbit全探索に続いて、今回は「順列全探索」です。
ちなみに、前回のAtCoderの記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
順列全探索とは
決まった数字や文字の列のすべての順列を洗い出す方法のこと。
すべての並び方を用いて何かしたいときに使います。
全部でn!通りあるので、nが大きくなると使えません。
問題の見分け方は、bit全探索よりも簡単かなと思いました。
どのように解くのか（Javaの場合）
基本的に競プロの参加者はC++を使っているので、std::next_permutationが使えます。
これは辞書順で次の順列を返してくれる便利なものです。
しかしこれはJavaにはありません。
ないので、仕方なく自作します。
他のサイトを参考にして作ったのがこちらです。
（ついでに、階乗も作りました。いらないとは思いますが、念のため。）
//階乗 static int factorial(int n) { if(n == 0) return 1; return n * factorial(n-1); } //次の順列を生成する static boolean next_permutation(int[] array, int start, int end) { if(array == null || start > end || start < 0 || end > array.length) { System.out.println("Error: 引数が正しくありません。"); return false; } for(int i=end-2; i>=start; i--) { if(array[i] < array[i+1]) { int j = end - 1; while(array[i] >= array[j]) { j--; } //swap int tmp = array[j]; array[j] = array[i]; array[i] = tmp; Arrays.sort(array, i+1, end); return true; } } return false; }
このnext_permutationを呼び出すことで次の順列を呼び出せます。
具体的には、次のように使います。
//順列全探索 for(int i=0; i<factorial(n); i++) { //ここに問題に応じた処理を入れる next_permutation(array, 0, array.length); }
なぜこれで解けるのか
こちらのサイトがわかりやすいです。C++ですが、こちらのサイトを参考にして上のライブラリを作りました。
qiita.com
というわけで、今回は順列全探索の勉強でした。
ひとまずこれで全探索の勉強は終わりです。
bit全探索もそうですが、こういうのは知らないと絶対解けないですよね。
こちらのサイトによれば、これで茶色コーダーになるための勉強はひとまず終わりのようです。
（この方は高校生でレッドコーダーまで行っていてすごいですよね。若いってうらやましい。）
qiita.com
ですが、これだけではD問題は解けないと思うので、次はBFS/DFSを勉強したいと思います。
これから、地道に勉強していくので、応援よろしくお願いします。
Web開発の勉強１- HTML, CSS, Javascriptの復習
前回の終わりに、次回は対戦ゲームに関する説明をするといったのですが、特定される可能性があるのでやめることにしました。(見る人が見れば一発でばれる恐れがあるため)
ちなみに、前回の記事はこちらです↓
developer-bpeldi2oerkd8.hatenablog.com
代わりに最近始めたWeb開発の勉強の記録をシリーズ化し、このブログに定期的に載せていきたいと思うので、よろしくお願いします。第1回は、HTML, CSS, Javascriptの復習です。
使う教材
「N予備校」というサイトを使うことにしました。最近のコロナの影響で期間限定で無料で公開しています。
そのサイトはこちらです↓
（アフィリエイトではないので、そこのところご承知ください。）
www.nnn.ed.nico
コロナの影響で暗い話題が多いですが、こういう教材を無料で提供していただけるのはありがたいですよね。
このサイトの教材の通り、進めていく予定です。（教材の中身は詳細には明かせないので、まとめと感想が中心になると思います。）
これからしばらくの間は、ここにある「プログラミング入門 Webアプリ」を勉強していきます。
入門といっても、HTML, CSS, Javascriptの初歩の初歩のところから、Node.jsのことやwebアプリのセキュリティ対策、フレームワークを使った開発などまで網羅していて、非常に充実した内容になってます。
感想
全部で4章に分かれているのですが、そのうちの1章を終わらせました。
内容としてはHTML, CSS, Javascriptの体系的な復習を簡単なWebアプリを開発しながら、学習していく感じです。
一応Web掲示板の制作経験はあるので、HTML, CSSについては本当に復習でしたが、今まで虫食いみたいに勉強していたこともあり、体系的に勉強したことはなかったので、勉強になりました。
Javascriptに関しては簡単な経験はありますが、深く触ったことはなかったので非常に勉強になりました。
先の章もチラ見しましたが、このコースが終われば基本的なweb技術は習得できそうなので、このコースが終わった後に新しく何か作ってgithubに上げたいと思います。
ということで、Web開発の勉強を始めましたという記事でした。
このコースをすぐに終わらせて、その知識を生かして早く新たに何か作りたいです。
これからシリーズ化していくつもりなので、温かく見守っていただけると嬉しいです。
（このペースだとこのコースは4月中に終わりそうですね。）
bit全探索について
前回の終わりに、今回は自作した対戦ゲームについて書くと書いたのですが、予定を変えて忘れないうちにメモをしておきます。
今回はAtCoderについての記事です。
前回の参加記事はこれです。
これから地道に勉強していくので、温かく見守っていただけたら嬉しいです。
developer-bpeldi2oerkd8.hatenablog.com
bit全探索とは
部分集合の全列挙や、2種類の選択のすべての組み合わせを調べる方法のこと。
とにかく2択の選択をn回繰り返すときに使います。
全部で2^n通りあるので、計算が間に合う場合にのみ使います。（間に合わない場合はbitDPなどを使うらしい）
2択はそれを選択するか選択しないかというシチュエーションでよく出てきます。（有名なものだと、数字の間に+を入れるか入れないかなど）
どのように解くのか(Javaの場合)
次のように書く。注意しないといけないのは、JavaではC++と違って、フラグが立っているかの判定を下のようにしないとエラーが出ること(よくネットで見るC++だと、if(i & (1 << j))となっているがこれではエラーが出る)
for(int i=0; i<(1 << N); i++) { for(int j=0; j<N; j++) { //フラグが立っているか if((1 & (i >> j)) == 1) { //ここに処理を書く(あるなしでいうとある場合) }else { //ここに処理を書く(あるなしでいうとない場合) } } }
なぜこれで解けるのか
先ほど書いたように、2択をn回行うので全部で2^n通りになる。
このすべてについて2進数で表現すると、すべての場合を全列挙できる。
例えば、1~3の数字の集合の部分集合は、各数字を選択する・選択しないの2択で考えると、2^3=8通りになる。
そこで0~7の数字を2進数で表現すると下のようになる。一番最初の行は各列がどの数字に対応するかを表している。（1のとき集合に入れる）
3 2 1
0 0 0 -> {}
0 0 1 -> {1}
0 1 0 -> {2}
0 1 1 -> {1,2}
1 0 0 -> {3}
1 0 1 -> {1,3}
1 1 0 -> {2,3}
1 1 1 -> {1,2,3}
このようにすべての部分集合を全列挙できている。
誰が考えたのか知らないが、頭良すぎです。
次回こそは、対戦ゲームの説明ができるかなと思います。
（このままだと、Atcoderだけのブログになってしまうので）
AtCoder Beginner Contest 162 に参加しました！
先ほど行われたAtCoder Beginner Contest 162に参加してきました！
結果は写真のような感じで、まだ茶色には行けず...
これから復習したいと思いますが、とりあえず解いた感想を書きたいと思います。
準備
今回から使用言語のバージョンが変わるとのことで、私の使っているJavaも今回からOpenJDK11になっていました。なので、使っている開発環境のEclipseのAtCoder用プロジェクトのバージョンをアップして臨みました。（初めて知ったんですけど、Java11で自動で作られるmodule-info.javaを削除しないとエラーが出るんですね）
加えて、前回D問題レベルの知識が足りないとわかり、時間がなかったのでとりあえずbit全探索だけ軽く勉強していきました。（今回出ませんでした）
経過
今回、なぜか最初だけジャッジが異様に遅いというトラブルがありながらも、いつもの通りA・B問題をすぐに解き、C問題に入りました。今回C問題はgcdが出たのですが、ライブラリを作っていなかったので、調べながら書きました。次回までに、よく使うものをライブラリにしてまとめておきたいと思います。正直、gcdは結果を保存しないで、その都度計算する形で提出してしまったので、TLEが出るかなと思ったのですが、出ませんでした。
ここで、安心していたところ、やっとのことで結果が出たB問題が間違っていました。1からNまでのところを0からN-1までとしてしまう凡ミスですぐに修正して再提出しました。
ここから、D問題を考えましたがDPっぽかったので（間違ってるかもしれない）、解くのを諦めました。来週までにD問題で出そうな典型問題を解けるようにしたいです。（どこまでできるかはわかりませんが）
結果
A・B・Cの3完で約40分で解きました。やはりA~Cの3問はスピード勝負ですね。
前回は15分ほどで解けたので緑パフォでしたが、今回はそこそこ長かったので茶パフォでした。
やはり、安定して順位を上げるにはD問題を解けるようにするしかないようです。
とりあえず、A~C問題はどんなにコンディションが悪い時でも安定して解けるようになったので、D問題レベルの問題を多く解いて、早く茶色に行きたいです。
勉強した内容についても記事にしたいと思います。
次回は、自分で作った簡単なゲームについて記事にしたいと思います。
はじめに
みなさんはじめまして。とある大学院生のbpeldi2oerkd8です。
今まで、多くの人の目に触れるSNS系(TwitterとかInstagramとか)は一切やってこなかったのですが、いよいよ就活が近づく中で、アウトプットの重要性に気付いたので始めました。
このブログでは、最近始めた競技プログラミングとか、githubに上げるような作ったプログラミングの作品とかについてゆるーく書いていけたらいいかなと思ってます。
簡単に自己紹介をさせてもらいます。
経歴について
特定が怖いのでおおざっぱに。
地元の小学校・中学校を卒業後、普通科の高校に進学。
そこから、情報系の大学に行きました。
情報系を選んだのは、もともとスマホとかに興味があったからです。
入って思ったのは自分はプログラミングの考え方にあっているということ。
プログラミング未経験のまま、情報系の大学に入ったのですが、1年の時のプログラミングの授業スタイルが自分に合っていたからなのか、プログラミングが好きになりました。
研究室はいろいろ見て回ったのですが、研究室の雰囲気を見て、今の人工知能の研究室に入りました。
昔から自分に合った場所を見つけるのが上手だと思っていて、直観で合ってると思ったところはほぼ100％実際に合っています。（研究室、部活やサークルなど）
ただ、実際にそこに行ってみないとわからないので、就活ではいろいろな企業さんを見て回って判断したいと思っています。
趣味
趣味は、運動することです。
とにかく煮詰まったときに体を動かしてストレスを発散してます。
毎日のジョギングは欠かせません。
最近は行っていないですが、水泳も好きで得意です。
水泳は習い事・部活を含めて10年近く続けていました。
得意な泳ぎは平泳ぎです。
研究
あまり詳しく書くと、特定されそうなので書けません。
使えるプログラミング言語
Java、PHP、Python、C、HTML、CSS、Javascriptです。
特に、Javaは研究で使っていることもあり、主に使っている言語です。競技プログラミングもJavaで参加しています。
PHPは、インターンでweb掲示板を作っていたこともあり、一通りの知識はあるつもりです。
Pythonは研究で使っているほか、機械学習の勉強をしているので、最近頑張っている言語です。
どの言語だからできないということはなく、基本的に必要になった言語を覚えて使っています。（研究では、先輩のプログラムがC#で書かれていたので、読めるようになりました。）
興味のあること
興味があることは、Web系（特にサーバーサイド）の開発、アプリ開発（特にAndroid）、機械学習です。
Web系の開発は、昨年インターンに参加して、作ってみて楽しいと思ったのがきっかけです。最近も、自作のweb掲示板にパスワードの再設定機能を追加しました。
アプリ開発も興味があります。私が主にJavaを使っていることもあり、特にAndroidアプリの開発に興味があります。授業の時に、何人かで協力して、ATM検索アプリを開発した経験があります。
機械学習については、研究のほか、データ分析・画像認識・音声認識の分野に興味があるので、勉強したいです。
最近興味が出ているのが競技プログラミングです。
Atcoderを今年の3月からやっていて、まだ灰色（1番下）ですが、C問題まではどの回でも確実に正解できるようになったので、D問題が解けるように頑張りたいです。
BFS、DFSなどのアルゴリズム系を勉強すればレートが上がると思うので、その勉強の経過についてもここに記述したいなと思っています。
持っている資格
資格というほどたいそうなレベルのものはありませんが、念のため書いておきます。
応用情報技術者試験とTOEICをこの4月に受ける予定でしたが、ご存じの通りコロナの影響で消えてしまいました。
これらの資格取得をした時にも、ここに書けたらいいなと思っています。
これからの予定
とりあえず、Atcoderについては茶色を目指したいと思います。
応用情報技術者試験とTOEICは再開のめどが立っていないので、ひとまず置いておきます。
個人的に、サーバーの負荷対策、アプリのレスポンス改善、高度な機械学習の知識がまだ十分ではないので、勉強してこのブログの記事にできたらいいなと思います。
これから、勉強を重ねてよりレベルの高いエンジニアを目指したいと思います。
みなさん、これからよろしくお願いします！
