二分探索について
今回もAtCoderの勉強です。
昨日の記事で書くと言っていた二分探索について今回は書きます。
ちなみに、昨日のABC166の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
二分探索とは
全体を2つに分けながら条件を満たすものを見つける探索方法です。
競プロの基本は全探索ですが、二分探索では全探索よりも高速に見つけることができます。
計算量はO(logN)とかなり高速に探索できます。
ただし、事前に探す対象の配列をソートしておく必要があります。
JavaではソートにArrays.sort()を用いることが多く、この計算量はO(NlogN)となるので、ソートされていない配列に対しては全体でO(NlogN)で見つけることができます。
どのように解くのか（Javaの場合）
二分探索の方法にはいろいろありますが、ここでは競プロ界隈で推奨されている「めぐる式二分探索」を使います。
めぐる式二分探索の説明はこちらを参考にさせていただきました。
qiita.com
いくつか実装方法を紹介しているサイトはあったのですが、いまいち自分にヒットするものがなかったので、元のサイトを参考にしながら、自分で実装してみたのがこちらです。
（バグが残っているかもしれません）
github.com
簡単に自分で実装したものの説明をします。
基本的にはisOKの条件を変えることで対応できます。
ただし、binary_searchメソッドの引数を一部変えています。
まず、配列をラッパークラスに変更しました。
これは、配列を逆順にソートしたものを引数として入れられるようにするためです。
次に、ngとokの引数を追加しました。
これは、配列の中の範囲を指定して探索できるようにするためです。
ng<okのとき、全体から探索したい場合は、ng=0, ok=a.lengthとします。（右側が真の場合）
ng>okのとき、全体から探索したい場合は、ng=a.length, ok=0とします。（左側が真の場合）
実装した自作のライブラリを使って、二分探索の問題を解いてみました。
解いた問題は、ABC077のC問題 Snuke Festival です。
atcoder.jp
この問題の肝は普通に全探索をAから順にやるとTLEしてしまうので、二分探索を使って計算量を減らしてやることです。
さらに、A→B→CとみていくとO(N^2logN)となってしまうので、Bを基準にしてAとCを二分探索していきます。
（全く気づきませんでした・・・）
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Integer[] A = new Integer[N]; Integer[] B = new Integer[N]; Integer[] C = new Integer[N]; for(int i=0; i<N; i++) { A[i] = sc.nextInt(); } for(int i=0; i<N; i++) { B[i] = sc.nextInt(); } for(int i=0; i<N; i++) { C[i] = sc.nextInt(); } Arrays.sort(A); Arrays.sort(B); Arrays.sort(C); long ans = 0; for(int i=0; i<N; i++) { int key = B[i]; int a_n = binary_search(A, key, 0, A.length); if(a_n <= 0 || a_n > A.length) continue; key++; int c_n = binary_search(C, key, 0, C.length); if(c_n < 0 || c_n >= C.length) continue; ans += (long)a_n * (N-c_n); } System.out.println(ans); } //okの条件（ここを問題ごとに変える）(int) public static boolean isOK(Integer[] a, int index, int key) { if(a[index] >= key) return true; else return false; } //めぐる式二分探索(デフォルトはkey以上を満たす最小のindexを返す)(int) public static int binary_search(Integer[] a, int key, int ng, int ok) { // int ng = -1; // int ok = a.length; if(ng < ok) ng--; else ok--; while(Math.abs(ok-ng) > 1) { int mid = (ok+ng) / 2; if(isOK(a, mid, key)) ok = mid; else ng = mid; } return ok; } }
ということで、二分探索に関する記事でした。
緑diffの問題が解けるようにこれからも勉強を続けていきます。
(茶色達成) AtCoder Beginner Contest 166 に参加しました！
昨日に引き続いてAtCoder Beginner Contest 166 に参加してきました！
晴れて茶色コーダーになりました！
ありがとうございます！
前回（といっても昨日ですが）の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
二分探索の問題を解き切って、ブログの記事にまとめようと思ったのですが、間に合いませんでした。
昨日よりも少しライブラリとして使えるようになったくらいです。
明日（か明後日）までにはまとめたいと思います。
経過
毎回、始まりの瞬間はサイトが重くならないかドキドキしますよね。
今回は杞憂でした。
A問題はすぐに解き、B問題もすぐにと思ったのですが、問題文の意味がいまいちわからず、理解するのが遅れ、15分くらいかかってしまいました。
焦ってC問題に取り掛かるとグラフの問題で、ライブラリを用意しておいてよかったと思いました。
（自分の成長を少しだけ実感しました）
確実に解き進め、開始30分後までに解き終わりました。
ここで、順位表を見ると、4000位くらいで、結構皆さんD問題を解いていたので、D問題に取り掛かることにしました。
D問題はしばらく悩みましたが、X=10^9でも、5乗根にすればせいぜいAとBは10^2=100くらいとなるので、全探索で十分間に合うのでは、と思いました。
解説に書いてあるほど、詳細に分析できていなかったので、-100<=x<=100の2重ループをして1回WAとなりましたが、範囲を広げることで通せました。
E問題は|i-j|=Ai+Ajとなるペアを数える問題でしたが、どう考えても2重ループでは通らないので、別の方法を考えましたが、時間切れとなりました。
参考になるかわかりませんが、C問題とD問題の解答を載せます。（Javaですけど）
C問題（自前のライブラリを使ってます。
ライブラリはGitHub - bpeldi2oerkd8/AtCoder_library: AtCoder用のライブラリーです（Java用）にあります。）
import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] H = new int[N]; for(int i=0; i<N; i++) { H[i] = sc.nextInt(); } Graph g = new Graph(N); for(int i=0; i<M; i++) { int A = sc.nextInt(); int B = sc.nextInt(); g.addEdge(g.getNode(A), g.getNode(B)); g.addEdge(g.getNode(B), g.getNode(A)); } int ans = 0; for(int i=1; i<=N; i++) { Node n = g.getNode(i); if(n.edges.size() == 0) { ans++; }else { boolean isGood = true; for(int j=0; j<n.edges.size(); j++) { Node to = n.edges.get(j).to; if(H[n.value-1] <= H[to.value-1]) { isGood = false; break; } } if(isGood) ans++; } } System.out.println(ans); } }
D問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long X = sc.nextLong(); int A = 0; int B = 0; for(int i=0; i<=1000; i++) { for(int j=-1000; j<=1000; j++) { long ans = (long)Math.pow(i, 5) - (long)Math.pow(j, 5); if(ans == X) { A = i; B = j; break; } } } System.out.println(A + " " + B); } }
結果
A～Dの4完です！まさかこんなに早く達成できるとは思っていなかったので、とても嬉しいです！
そして、3度目の緑パフォです！
これからは緑色になるために、4完を安定できるように勉強を続けます。
というわけで、ABC166の結果でした。
自分はどちらかというと数学的な問題が出たほうがパフォーマンスがいいみたいです。
他のタイプのD問題も解けるように頑張ります！
AtCoder Beginner Contest 165 に参加しました！
先ほど行われたAtCoder Beginner Contest 165 に参加してきました！
やっと茶色が見えてきたような気がします！
早速感想です。
ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
前回に引き続いてD問題の勉強を続けました。
前回から今回までで勉強した内容は以下の通りです。
- 貪欲法
- Mod計算
- 二分探索（の一部）
やはりライブラリを充実させていかないといけないのと、それを使いこなす力をつけることが必要だと感じました。
DPについては結構出て、やらなきゃいけないと思っているのですが、量が多いので後回しにしてしまっています。
経過
始まった後すぐにサイトが重くなって、とても嫌な予感がしましたが、なんとか10分遅れで始まりました。
A, B問題については、最近の中では比較的難しめだったので、今回は全体的に難易度が上がるなと思いました。
案の定、C問題は難しめで、この後のD問題のほうが解けている人が多かったですね。
C問題については全探索かなと思ったのですが、良い列挙の方法が思いつかず、苦戦しました。
なので、順位表を見ていると、D問題のほうが解けている人が多かったので、D問題を解くことにしました。
D問題ではそこそこ苦戦しましたが、A*[x/B]に注目し、[x/B]が０となるxの中で最大のものを取ればよいと気づいたので、何とか解けました。
初めてのD問題ACで嬉しかったです。
次は、４完を目指したいと思います。
参考になるかわかりませんが、JavaでのD問題でACになった自分の解答を載せておきます。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); long B = sc.nextLong(); long N = sc.nextLong(); long x = 1; if(B >= 2) { x = Math.min(B-1, N); } long ans = (long)Math.floor((double)A*x/B) - A * (long)Math.floor((double)x/B); System.out.println(ans); } }
結果
ABDの３完で65分で解きました。
AtCoderを始めてから、2度目の緑パフォです！
引き続き、努力を続けたいと思います！
というわけで、ABC165の結果でした。
次は4完を目指して勉強を続けたいと思います。
明日もあるので、今日は体調を整えて明日に備えたいと思います。
Mod計算について
今回はAtCoderの記事です。
以前から余りの問題をやりますと言っていたので、今回はMod計算全般についてやりました。
（大変でした・・・）
ちなみに、前回勉強した貪欲法についての記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
Mod計算とは
mod計算とは、modの後にくる数字（これを法という）の余りの計算を行うことです。
高校生の数学の1年で習うやつですね。
例えば、5を13で割った余りと18を13で割った余りは同じ5なので、13を法とする世界では合同である、という感じですね。
AtCoderでは（というか競プロでは）、1000000007を法とする問題がよく出てきます。
どのように解くのか（Javaの場合）
mod計算の具体的な解き方は以下に分かりやすい記事を貼っておきましたので、こちらを見てください。
（きっと私よりずっとわかりやすいので）
qiita.com
ここでは、実際にJavaでどのように解くのかについて書きます。
まずは、自分で上記の記事を参考にして、modの四則演算、組み合わせ、逆元などに関するライブラリを作ります。
（コンテストのたびに1から書くのは絶対無理）
ちなみに、私が作ったライブラリがあるのでよかったら参考にしてください。
（バグがあるかもしれませんが）
競プロでは、Javaは本当に情報が少ないですよね。
github.com
次に、自作のライブラリを使って問題を解き、バグがないかを確認します。
実際に、比較的最近出題されたABC156のD問題 Bouquet で試してみました。
atcoder.jp
実際に解いてみたのですが、TLEやOut of Memory Errorになりまくりです。
nが大きすぎると、上の記事に書いてあるnCrではOut of Memory Errorになってしまうので、以下の記事を参考にして新しいものをライブラリに追加しました。
こちらの記事では、n, rの大きさによってどの手法を使うべきかきれいに場合分けされています。
drken1215.hatenablog.com
ようやく、TLEやOut of Memory Errorにならない正解を見つけたのがこちらです。
自作のメソッドの仕様は上に貼ったライブラリの中身を見てもらえると嬉しいです。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); ComInit_bign(n, Math.max(a, b)); long ans = modpow(2, n); ans = sub(ans, Com_bign(n, 0)); ans = sub(ans, (Com_bign(n, a) + Com_bign(n, b))); System.out.println(ans); } }
四則演算（上のsubなど）は原則自作のメソッドを用います。
あと、累乗についても自作のmodpowというメソッドを用います。
（これを用いないとTLEします。二分累乗法を使っています）
解き方については、nC0+nC1+nC2+...+nCn=2^nになることを利用して、（二項定理）
そこからnC0とnCa、nCbを引きます。
a, b <= 2*10^5 なので、Out of Memory Errorにならずに解けます。
ということで、今回の記事は終了です。
やはり重かったですね。
とても疲れましたが、いよいよ明日（0時回ったので正確には今日）の21時からABC165が始まるので明日も頑張りたいです。
Web開発の勉強２- サーバーサイド開発の準備
書きます詐欺を繰り返していたWeb開発の勉強の記事を書きます。
第2回はサーバーサイド開発の準備です。
このシリーズの前回の記事はこちらです。（だいぶ前ですが（汗））
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
コロナの期間中は無料で提供していただけているので、本当に感謝です。
（決して回し者ではありません）
www.nnn.ed.nico
今回はこの第2章が終わりました。
内容としては、次のような感じです。
中途半端に知識はあるので、知っていることも多かったのですが、意外と穴がありました。
あと、こちらで紹介されている手法は、Vagrantなどを使うのですが、ファイヤーウォールをオフにしたり、セキュリティの警告が出たので、別の方法でやりました。
時間がかかってしまったのはそのためです。
感想
とりあえずこれでサーバーサイドの開発に向けた知識は習得できたと思います。
正直何か具体的に目に見えるものを作るとかはあまりないので、つまらなかったのですが、この後の章のために重要な知識だったと思います。
個人的には、シェルプログラミングを学べたのがよかったです。
定期的に自動でメールを配信するプログラムを作りたかったので、いつか学ぼうと思っていたのですが、この機会に学べたので良かったです。
次回はいよいよNode.jsを用いたサーバーサイドの開発とのことなので、今から楽しみです。
というわけで、久しぶりのWeb開発の記事でした。
予定では4月にすべて終わらせる予定だったのですが、終わらなかったですね・・・
GW中には頑張って入門コースを終わらせたいと思います。
貪欲法について
今回もAtCoderについての記事です。
D問題がまだ本番で1問も解けていないのが悔しいので、今週末のABC2連に向けて頑張ります。
前回に引き続き、AtCoderの勉強をしました。
ちなみに前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
前回のABCの参加記録はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
貪欲法とは
貪欲法とは、あるルールに従ってその都度最適なものをとっていく手法です。
例えば、有名なA - おつりのようなコインの問題では、コインの枚数が少なくなるように、コインの額が大きいほうからおつりをコインに変えていくというルールに従って、最小のコインの枚数を求めます。
アルゴリズムとしては単純なほうなので分かりやすいです。
基本的には決まったアルゴリズムはありませんが、いくつ決まったパターンがあります。
それが、以下のようなものです。
- 区間スケジューリング問題
- 辞書順の問題
今回は決まった解法があるこの2種類の問題に対する解き方を次の項目に書きます。
どのように解くのか（Javaの場合）
参考にしたサイトは以下のサイトです。
ここに記載されている問題のうち、2問をJavaで解いたものを載せます。
（コードが拙いのは見逃してください）
qiita.com
区間スケジューリング問題
区間スケジューリング問題は終端をソートしていくものです。
これは知らないとなかなか出ない発想なので、勉強してよかったです。
解いた問題はABC103のD問題 Islands Warです。
atcoder.jp
Atcoder Problemsというサイトで水色diffとなっていますが、おそらくこれを区間スケジューリング問題だと気付けるかが難しいと思います。
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] desire = new int[M][2]; for(int i=0; i<M; i++) { desire[i][0] = sc.nextInt(); desire[i][1] = sc.nextInt(); } Arrays.sort(desire, (a, b) -> a[1] - b[1]); int index = 0; int ans = 0; while(index < M) { int end = desire[index][1]; ans++; index++; while(index < M && desire[index][0] < end) index++; } System.out.println(ans); } }
辞書順の問題
辞書順とは、早く辞書に出てくる順番のことです。
a-zだとaのほうに近いほど早く出てきます。
文字が途中まで同じ場合は、文字数が少ないほうが優先されます。
解いた問題はABC076のC問題 Dubious Document 2です。
atcoder.jp
この問題のポイントは辞書順で最小にするために、後ろのほうから一致するか見ていくところだと思います。
あとは、?の部分をaに変えるだけで辞書順が最小にできます。
一致するかの確認方法は後ろから一文字ずつ順にみていけばいいです。
ここで気づいたのですが、JavaのString.replaceとStringBuilder.replaceは中身が全く違うんですね。
indexを指定して決まった範囲を別の文字列に置き換えたいときはStringBuilder.replaceを使うそうです。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String S = sc.next(); String T = sc.next(); StringBuilder sb = new StringBuilder(S); boolean matchAnswer = false; for(int i=S.length()-T.length(); i>=0; i--) { boolean isMatch = true; for(int j=i; j<i+T.length(); j++) { if(!(S.charAt(j) == T.charAt(j-i) || S.charAt(j) == '?')) { isMatch = false; break; } } if(isMatch) { sb.replace(i, i+T.length(), T); matchAnswer = true; break; } } String ans = "UNRESTORABLE"; if(matchAnswer) { ans = sb.toString(); ans = ans.replace("?", "a"); } System.out.println(ans); } }
フラグを使いまくっていますね。
（もっときれいに書けた気もします。）
ということで、今回の記事は終了です。
個人的には週末のAtCoder Beginner Contest 2連続はチャンスだと思っているので、どちらかでD問題が解けるようにしっかり準備していきたいと思います。
BFSについて
こんにちは。
今回もAtCoderの記事です。
前々回のDFSに続いて、BFSについて書きたいと思います。
ちなみに、DFSについての記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
また、前回のAtCoder Beginner Contestの参加記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
BFSとは
BFSとは「幅優先探索」の略です。
幅優先探索は、グラフなどの深さが浅いほうから均等にたどっていく方法です。
DFSについて - bpeldi2oerkd8の開発日誌でも書いたように、「最短」などのワードがあったときに使います。
DFSとの使い分けは、前回の記事を見てもらえると嬉しいです。
どのように解くのか（Javaの場合）
基本的にDFSとの違いはスタックを使うか、キューを使うかの違いです。
スタックでは、あるノードを取り出した時、そのノードにつながっているものは次にすぐ取り出されますが、キューでは最後に取り出されるので違いが生まれます。
実際に書いてみて、つまづいた点は!queue.contains()を入れ忘れてしまうことですね。
(DFSにも言えることですが)
これを入れないと同じノードを複数回キューに入れてしまうので、おかしなことになります。
以下のコードは迷路の例です。
全体は下にあるgithubにあるので、もし見たいという方がいましたら、目を通していただけると嬉しいです。
github.com
Queue<Point> queue = new ArrayDeque<>(); queue.add(スタート地点); while(!queue.isEmpty()) { Point p = queue.poll(); int h = p.x; int w = p.y; if(終了条件) { //処理 break; } //訪問済み visited[h][w] = true; 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(!queue.contains(n_p) && !visited[n_h][n_w] && 壁でない) { queue.add(n_p); distance[n_h][n_w] = distance[h][w] + 1; } } }
ということで今回もAtCoderの記事でした。
どうやら今度の土日に2回ABCがあるみたいですね。（本当にありがとうございます）
次回までに、2分探索と最近頻出の余りの問題はやっておきたいですね。
個人的にまだ書きたいことが2つほどあるので、早いこと記事にしたいです。
Web開発のほうについても早いうちに記事にしたいと思います。
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は再開のめどが立っていないので、ひとまず置いておきます。
個人的に、サーバーの負荷対策、アプリのレスポンス改善、高度な機械学習の知識がまだ十分ではないので、勉強してこのブログの記事にできたらいいなと思います。
これから、勉強を重ねてよりレベルの高いエンジニアを目指したいと思います。
みなさん、これからよろしくお願いします！
