累積和について
AtCoderの記事です。
今回は累積和について学習しました。
前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
なかなか思うように進まないことも多いですが、焦らず着実に進めていきます。
累積和とは
累積和とは、その名の通り、配列などで初めの値からそこまでの和を記録するものです。
使い方としては、ある区間の和を複数回求める必要があるときに使います。
これを行うと前処理にO(N)かかりますが、値を取り出すときはO(1)で取り出せるので、計算量の削減ができます。
どのように解くのか（Javaの場合）
基本的には累積和を格納する用の配列を用意し、あらかじめ累積和を格納します。
このとき、配列の大きさはN+1にしないといけないことに注意が必要です。
大まかなテンプレは次の通りです。
//前処理 int[] a = new int[n]; int[] sum = new int[n+1]; sum[0] = 0; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); sum[i+1] = sum[i] + a[i]; } //最大値を求める int max = 0; for(int i=1; i<=n-k+1; i++) { //取り出し int s = sum[i+k-1] - sum[i-1]; max = Math.max(max, s); } //処理
テンプレは正直問題によって違うので難しいですね。
これを応用した2次元累積和もあります。
実際に問題を２つ解いてみました。
１つめは AGC023のA問題 Zero-Sum Ranges です。
atcoder.jp
解法は分かったのですが、nCrの求め方をライブラリで求めようとしてはまりました。
今回はr=2なので、公式通りに計算すればエラーなく通ります。
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[] sum = new long[N+1]; int max = 0; sum[0] = 0; Map<Long, Integer> count = new HashMap<>(); count.put(0L, 1); for(int i=1; i<=N; i++) { sum[i] = sum[i-1] + sc.nextLong(); if(count.containsKey(sum[i])) { int new_c = count.get(sum[i])+1; count.put(sum[i], new_c); max = Math.max(max, new_c); } else { count.put(sum[i], 1); max = Math.max(max, 1); } } long ans = 0; for(int value : count.values()) { ans += (long)value * (value-1) / 2; } System.out.println(ans); } }
もう1つは、2次元累積和の問題で、ABC005のD問題 おいしいたこ焼きの焼き方 です。
atcoder.jp
やはり難しい。
水色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[][] D = new int[N][N]; int[][] sum = new int[N+1][N+1]; sum[0][0] = 0; sum[0][1] = 0; sum[1][0] = 0; //2次元累積和 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { D[i][j] = sc.nextInt(); sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + D[i][j]; } } //面積がN*N以下のたこ焼きの美味しさの合計の最大値 int[] delis = new int[N*N+1]; Arrays.fill(delis, 0); for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { int max = 0; int area = i * j; for(int k=0; k<=N-i; k++) { for(int l=0; l<=N-j; l++) { int deli = sum[k+i][l+j] - sum[k+i][l] - sum[k][l+j] + sum[k][l]; max = Math.max(max, deli); } } delis[area] = Math.max(delis[area], max); //面積がarea以上の値について最大値を更新 for(int k=area+1; k<=N*N; k++) { delis[k] = Math.max(delis[k], delis[area]); } } } int Q = sc.nextInt(); int[] ans = new int[Q]; for(int i=0; i<Q; i++) { int P = sc.nextInt(); ans[i] = delis[P]; } for(int i=0; i<Q; i++) { System.out.println(ans[i]); } } }
ということで、累積和についてでした。
2次元累積和についてはまだ練習が必要ですね。
いもす法やしゃくとり法についてはまた今度やります。
このあと、21:00からABCがあるので、頑張ります。
Web開発の勉強３- サーバーサイドプログラミング入門１
お久しぶりのWeb開発の記事です。
前回からだいぶ空いてしまいましたが、
第3回はサーバーサイドプログラミング入門ということで、
いよいよNode.jsを使った開発に取り組みました。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
前回に引き続き、教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
5月末までは無料ですが、そこからは有料になってしまいます。
www.nnn.ed.nico
ただ、5月20日までのキャンペーンとして、
TwitterでフォローとRTをすると、
全員が1年間無料になるキャンペーンをやっているらしいです。
私もこの後やる予定です。
（念のためですが、これはステマとかではなく、親切心で紹介しています。）
今回はこの3章の11. 例外処理まで終わりました。
内容としては、次のような感じです。
- Node.jsの使い方
- yarnについて
- Slackのボット開発
やはり、自分の作ったプログラムが実際に動くと感動しますね。
結構バグがでたり、エラーが出たりして大変だったのですが、何とか形になりました。
感想
結構重いですね。
入門だからとなめてかかると、結構驚きます。
ただ、中身としては濃いですね。
今まで何となくの知識だったJSONが出てきたとき、
なるほどJavascriptのオブジェクトだからあの形式なんだ、
と発見がありました。
（知ってる方からすれば、何を今更と思うでしょうが）
進みが遅いので、もう少しスピードアップしないとやばいですね。
というわけで、Web開発の記事でした。
やはり、yarn周りでエラーが頻繁に出るのが謎ですね。
再インストールで治ることも多いのですが、原因がよくわかりません。
スピードを上げるため、1日の目標を決めて頑張りたいと思います。
AtCoder Beginner Contest 167 (ABC167) に参加しました！
AtCoder Beginner Contest 167 (ABC167) に参加しました。
うーん、ちょっと悔しいですね。
感想を書いていきます。
ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
経過
今回もスタートがスムーズでした。
（AtCoder社さんありがとうございます。）
A・B問題についてはスムーズに解けました。
C問題はちょっと時間がかかりました。(40分くらい)
見た感じ、重み付きナップザック問題かなと思ったのですが、まだやってないのでやばいなと思いました。
ただ、どこかのサイトでC問題までは全探索で何とかなるという風に書いてあったのを思い出し、なんとかbit全探索で通しました。
そのコードがこちらです。（汚いかもしれませんが）
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 X = sc.nextInt(); int[] C = new int[N]; int[][] A = new int[N][M]; long C_sum = 0; long[] A_sum = new long[M]; for(int i=0; i<N; i++) { C[i] = sc.nextInt(); C_sum += C[i]; for(int j=0; j<M; j++) { A[i][j] = sc.nextInt(); A_sum[j] += A[i][j]; } } //すべて選ぶ for(int i=0; i<M; i++) { if(A_sum[i] < X) { System.out.println(-1); return; } } long ans = C_sum; for(int i=0; i<(1<<N); i++) { long sum = C_sum; long[] Ai_sum = new long[M]; System.arraycopy(A_sum, 0, Ai_sum, 0, A_sum.length); for(int j=0; j<N; j++) { //選択しない if((1 & (i >> j)) == 0) { sum -= C[j]; for(int k=0; k<M; k++) { Ai_sum[k] -= A[j][k]; } } } boolean ok = true; for(int j=0; j<M; j++) { if(Ai_sum[j] < X) { ok = false; break; } } // System.out.println("ans: " + ans); if(ok) { ans = Math.min(ans, sum); // System.out.println("ans_change: " + ans); } } System.out.println(ans); } }
D問題は、そのまま順にたどっていくとTLEになるのは見えていたので、loopを作り、loopの余りをとることで計算時間を短縮しようとしましたが、TLE・・・。
原因は今の段階ではわかっていません。
この後、解説を見たいと思います。
結果
A~Cまでの3完です。
正直悔しいですね。
まだまだ、演習量が足りないので、増やせて行けたらと思います。
というわけで、ABC167の結果でした。
これからも引き続き、勉強を頑張っていきます。
素数について
お久しぶりとなってしまいました。
今回もAtCoderの記事です。
Web開発のほうはもう少しで記事として書けるくらいの内容までいくので、しばしお待ちください。
ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
どのように解くのか（Javaの場合）
自作のライブラリを作り、それを利用する形です。
Javaですが、自分のライブラリはここに置いたので、よかったら参考にしてください。
（バグがあったらすみません。）
github.com
このライブラリを使って、実際に問題を解いてみました。
解いた問題はABC084のD問題 2017-like Number です。
atcoder.jp
高速な素数判定にエラトステネスの篩（ふるい）を使います。
また、累積和も使わないとおそらくTLEします。
（累積和についてはまた今度記事にします。）
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); boolean[] isPrime = isPrimeN(100000); int[] sum = new int[100001]; sum[0] = 0; for(int i=1; i<=100000; i+=2) { if(like2017(i, isPrime)) sum[i] = sum[i-1] + 1; else sum[i] = sum[i-1]; sum[i+1] = sum[i]; } int Q = sc.nextInt(); for(int i=0; i<Q; i++) { int l = sc.nextInt(); int r = sc.nextInt(); System.out.println(sum[r]-sum[l-1]); } } public static boolean like2017(int n, boolean[] isPrime) { if(n % 2 == 0) return false; if(isPrime[n] && isPrime[(n+1)/2]) return true; else return false; } //n以下のすべての数の高速な素数判定(エラトステネスの篩) public static boolean[] isPrimeN(int n) { boolean[] isPrime = new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; int sqrt = (int)Math.sqrt(n); //割れる数はsqrt以下 for(int i=2; i<=sqrt; i++) { if(isPrime[i]) { for(int j=i*i; j<=n; j+=i) { isPrime[j] = false; } } } return isPrime; } }
これは緑diffですが、やはり緑くらいになってくると、複数の知識を組み合わせた問題が多いですね。
あと、あまり関係ないんですが、Arrays.fillなんて便利なものがあったんですね・・・。
今度から使っていきたいと思います。
というわけで、素数についての記事でした。
本日もABCがあるので、頑張りたいと思います。
Web開発についての記事は次回か次々回には記事にしたいと思います。
AtCoderの茶色になるまでにやったこと 【Java】
先日のAtCoder Beginner Contest 166 (ABC166)で茶色になりました！
茶色を達成したときの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
天才は見向きもしない色なのですが、我々凡人にとっては、茶色になるのは意外と大変です。
（どのくらい勉強するのか目安がわかりませんよね）
私も茶色くらいだったらすぐ行けるだろ、と思っていたのですが、結局達成するまでに10回かかってしまいました。
おそらく、もっとかかる方はかかると思います。
今回は備忘録として、茶色になるまでにやったことを書きたいと思います。
茶色になるまでに停滞している方、これから茶色になるために勉強しようとしている方の参考に少しでもなれば幸いです。
AtCoderの常識を覚える
ある程度、AtCoderをやっていると自然に覚えていくものなのですが、AtCoder界隈で常識とされていることがそこそこの量あります。
まずは、AtCoderに何回か参加して、こういった常識を知ることが大切だと思います。
ぱっと思いついた常識はこんな感じです。
- コンテストに積極的に参加する（特に、初心者のうちはAtCoder Beginner Contest (ABC) だけ参加すればよい）
- A問題から順に解いていく（ただし、回によっては難易度が入れ替わっていることがあるので、わからなければ1つ先の問題も見る）
- 必ず、自分のパソコンに開発環境を用意する（ブラウザ上だとどうしても速度が遅いので）
- 自分にプログラミングの基礎能力が身についていない場合は、もう少し勉強してから参加する（ガチのプログラミング初心者は周りのレベルが高すぎて、普通に心が折れます）
3つ目については長くなるので、次の項目を見てください。
4つ目については、あまりネットで言われていませんが、AtCoderは正直ガチの初心者向けではないことです。
回にもよりますが、A・B問題がスラスラと解けるレベルでないと挫折してしまうと思うので、PaizaやProgateなどである程度力をつけてから参加したほうがいいかもしれないです。
paiza.jp
自分のパソコンに開発環境を構築する
何回かコンテストに参加すると、必ず通る道だと思います。
やはりAtCoderでは速さを競うので、ブラウザ上では遅いと感じます。
なので、必然的に自分のパソコン上に開発環境が必要になってきます。
これは、メソッドや変数などを自動で補完してくれ、よく使う処理も便利なコマンドで補完してくれます。
ちなみに、Eclipseはこちらのサイトでダウンロードできます。
mergedoc.osdn.jp
こちらのサイトの最新版のJava版のFull Editionをダウンロードすれば大丈夫です。
インストール方法、使い方などはこちらのサイトが参考になります。
www.sejuku.net
他にも、AtCoderで人気なC++やPythonでも使える環境として、Visual Studio Code (VS Code) があります。（人気ですね）
azure.microsoft.com
AtCoderで必要な知識をつける
ここからは、よく他の方も紹介されているアルゴリズムやデータ構造、計算量に関することです。
やはり、色を変えるためにはこれらの知識が不可欠だと感じます。（私も今勉強中です）
こちらのサイトが非常にわかりやすいです。
qiita.com
こちらのサイトにあるように、基本的な文法に加え、まず全探索になれることから始まります。
あと、計算量に関する知識も必要です。
ただ、現段階では私もそこまで詳しくなく、茶色の段階ではAtCoderで時間制限に間に合うのは回以下という知識さえあればいいと思います。
そして、ここまで終わったら、さらにSetやMapなどの標準ライブラリの知識と使い方、二分探索などの他のアルゴリズムの知識をつけていきます。
こちらのサイトを参考に勉強しています。
qiita.com
このようにしていると、いつの間にか茶色に到達しているはずです。
（ちなみに、茶色に到達するまで平均10回といわれているので、あきらめずにコンテストに参加し続けるのも大切だと思います。）
というわけで、AtCoderで茶色になるまでにやったことを紹介させていただきました。
まだ、ブログ経験が浅いもので、分かりにくいところがあるかと思いますが、そこのところは見逃してください。
この記事が茶色を目指している方の参考に少しでもなれば嬉しいです。
これからも、AtCoderの勉強を続けていくつもりなので、もしよかったら読者になっていただけると嬉しいです。
（ツイート・はてなブックマークなどもしていただけると嬉しいです。）
二分探索について
今回も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だったこともあり、早めに退散しました。
