Web開発の勉強９- 自作サービス作り２
今回もWeb開発に関する記事です。
前回は自作サービスづくりで側だけ作りました。
developer-bpeldi2oerkd8.hatenablog.com
今回はbotの部分を作りました。
作ったもの
新たにhubotのひな型を作成し、出席登録のbotを作成しました。
今回は決まったフォーマットでメッセージを飛ばすと登録結果が返ってくるようにしました。
誤登録を防ぐため、メンションをつけないと反応しないようになっています。
反応する形式は、以下の3つです。
- 出席（空白いくつでも）（月）/（日）
- 欠席（空白いくつでも）（月）/（日）
- 不明（空白いくつでも）（月）/（日）
経過
hubotのひな型をyoで作り、決まった形式ではないと反応しないようにbotをJavascriptで実装しました。
個人的にはまったのが、herokuで動くようにするための方法です。
ひな形のままでは、「/usr/bin/env: 'coffee': No such file or directory」というエラーが出てしまい、動きません。
これを解決するためには、binフォルダ直下のhubotとhubot.cmdを以下のように編集します。
#!/bin/sh set -e yarn install #--no-bin-linksを削除 export PATH="node_modules/.bin:node_modules/hubot/node_modules/.bin:$PATH" exec node_modules/hubot/bin/hubot --name "lattendance-bot" "$@"
@echo off rem --no-bin-linksを削除 call yarn install SETLOCAL SET PATH=node_modules\.bin;node_modules\hubot\node_modules\.bin;%PATH% node_modules\hubot\bin\hubot.cmd --name "lattendance-bot" %*
Web開発の勉強８- 自作サービス作り１
今回もWeb開発に関する記事です。
前回の記事でようやくWeb開発の入門コースが終わりました。
developer-bpeldi2oerkd8.hatenablog.com
今回から自分でサービスを1つ作ろうと思います。
何を作るか
せっかく「予定調整君」を作ったので、これを活かして自ら使うサービスを作れないかと考えました。
身近な問題として「研究室の出欠登録と確認が大変だ」という課題がありました。
このため、習った知識を生かし、Slackのbotを用いて出欠を簡単に登録できるようにし、それをサイト上で確認できるようにするというサービスを考案しました。
このサービスをLab（研究室）＋Attendance（出席）の造語として「Lattendance」と名付けました。
今回からはこのサービスを作っていこうと思います。
設計
ページ構成は以下の通りです。
- トップページ/マイページ（自ら作った予定の一覧）ログアウトはボタンを押すとできるようにする
- ログインページ（Githubのログインへのリンク）
- 予定表示/出欠一覧ページ（Slackのbotから登録した出欠情報を表形式で表示）
- 予定作成ページ
注意点として、出欠の登録はSlackのbot経由でのみ可能です。
これによって、無関係者が出欠の登録をすることを防ぎます。
使う技術
開発言語：Javascript, HTML, CSS, SQL
フレームワーク：Node.js, Express, Bootstrap, Jest
環境：Linux, VS Code, heroku
データベース：PostgreSQL
プロジェクト管理：GitHub, Git
雛型の作成
今回はログイン機能の実装とBootstrapを使ったデザインの実装を行いました。
完成した画像はこちらです。
- トップページ
- ログインページ
- ログインボタン後の遷移画面
- マイページ
感想
今回はログイン機能とデザインを主にやりましたが、思った以上に苦戦しました。
特にログインしたときにユーザー名が表示できるようにし、プルダウンメニューでログアウトボタンを実装するのはかなり時間がかかりました。
また、GitHubでログインボタンのデザインにも悩み苦戦しました。
ただ、自分で試行錯誤して実装すると、今まで理解が浅かった部分がわかり、力になっていることを実感できました。
次回は、フォーム・データモデルの実装を行っていきたいと思います。
Web開発の勉強７- 実践サーバーサイドプログラミング２
今回もWeb開発に関する記事です。
ようやく夏のインターンシップが終わり、一息したところで残っていたWeb開発入門のコースを終わらせました。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
内容のほうは、4章をすべて終わらせました。
具体的な内容としては以下のような感じです。
- 「予定調整くん」というサービスを今までの知識を用いて制作
具体的には設計の部分からデザイン・セキュリティ対策まで実装しました。
感想
ひとまずこれで入門コースが終わり、Web開発に関する基本的な知識がついたと思います。
今回得た知識を使って、簡単なサービスを設計から一度やってみて完成させようと思います。
その経過をこのブログに載せたいと思います。
というわけで、Web開発の勉強の記事でした。
この入門コースはボリュームがあり、大変でしたが大変実のあるものになったと思います。
実際にExpressを用いて自分でサービスを作ることで、知識をより強固なものにしたいと思っています。
Web開発の勉強６- 実践サーバーサイドプログラミング１
お久しぶりです。
今回はWeb開発に関する記事です。
インターンシップ・研究などと忙しく、なかなかAtCoder、Web開発に手がつかない時期が続きました。
ここ1か月は時間が取れるようになってきたので、再開したいと思います。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
無料登録期間中に登録したので、1年間は無料です。
ありがとうございます。
内容のほうは、4章の 15.テーブルの集計 まで終わりました。
具体的な内容としては以下のような感じです。
- Webフレームワーク（Express）を使った開発の基礎
- 各種フレームワークの使い方
- Jest（テスティング）
- CircleCI（継続的インテグレーション）
- webpack（クライアント）
- jQuery（DOM操作）
- AjaxとWebSocket
- データベースとSQL（PostgreSQL）
いよいよ本格的なWeb開発という感じですね。
Web APIの開発までカバーしています。
感想
これでWeb開発の基本はほとんど終わり、あとは実際のサービス開発の練習のみとなりました。
無料でこの教材が使えるのは大きく、とても勉強になります。
（有償でも受ける価値はあると思います。これはステマでもなんでもなく。）
このコースが終わった後は、実際に勉強した内容を使って１つサービスを作る予定です。
というわけで、Web開発の勉強の記事でした。
残りは予定調整くんという架空のサービスを作る練習です。
夏休み中には自作のサービスを1つ完成させたいなと思っています。
エイシング プログラミング コンテスト 2020 に参加しました (AtCoder)
お久しぶりとなります。
エイシング プログラミング コンテスト 2020 に参加しました。
久しぶりのコンテストだったので、感覚を忘れていて、リハビリ感覚です。
ちなみに、前回の記事はこちらです。（だいぶ前となってしまいますが・・・）
developer-bpeldi2oerkd8.hatenablog.com
準備
ほとんどできていないです。
これから少しずつでも復帰できたらなと思います。
経過
前回からしばらく空いていたので、とにかく感覚を取り戻すのに精一杯でした。
A・B問題をさくっと解き、C問題に移りました。
C問題はぱっと見わからず、式変形を試みたりしましたが、
x^x+y^y+z^z+x*y+y*z+z*x >= 1となる関係から、
x=1, y=1と考えてもz=100くらいだと思ったので、全探索で行きました。
余裕をもってx, y, z <= 200で3重ループを回すと問題なく通りました。
（ここまで40分ほど）
import java.io.PrintWriter; 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[] count = new int[N+1]; Arrays.fill(count, 0); for(int x=1; x<=200; x++) { for(int y=1; y<=200; y++) { for(int z=1; z<=200; z++) { int n = x*x+y*y+z*z+x*y+y*z+z*x; if(n <=N) { count[n]++; } } } } PrintWriter pw = new PrintWriter(System.out); for(int i=1; i<=N; i++) { pw.println(count[i]); } pw.flush(); } }
D問題は再帰と進数の変換を用いて実装しましたが、N=2*10^5と大きいので、
途中計算の記憶をMapで実装しました。
しかし、サンプルは通したのですが、ほとんどREとなってしまいました。
原因については、調べます。
import java.io.PrintWriter; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { //java11 // static int[] fn; static Map<Integer, Integer> fn; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String X = sc.next(); // fn = new int[(int)Math.pow(2, N)]; // fn = new int[10000000]; fn = new HashMap<>(); // Arrays.fill(fn, -1); PrintWriter pw = new PrintWriter(System.out); for(int i=0; i<N; i++) { StringBuilder sb = new StringBuilder(X); //bit反転 if(X.charAt(i) == '0') { sb.setCharAt(i, '1'); }else { sb.setCharAt(i, '0'); } int Xi = Integer.parseInt(sb.toString(), 2); pw.println(fn(Xi)); } pw.flush(); } public static int fn(int n) { if(fn.get(n) != null) { return fn.get(n); } if(n == 0) { // fn[n] = 0; fn.put(n, 0); return fn.get(n); } if(popcount(n) == 0) { fn.put(n, fn(0) + 1); }else { fn.put(n, fn(n % popcount(n)) + 1); } return fn.get(n); } public static int popcount(int n) { return Integer.bitCount(n); } }
結果
久しぶりにしてはという感じですが、やはり問題を解かないとレベルは上がっていきませんね。
他のことでも忙しいのですが、なんとか時間を作って頑張りたいと思います。
というわけで、エイシング プログラミング コンテスト 2020の結果でした。
次回も参加したいと思います。
東京海上日動プログラミングコンテスト 2020に参加しました(AtCoder)
東京海上日動プログラミングコンテスト 2020に参加しました。
結果は上にある通り、初めてレートが下がりました・・・（つらい）
反省点を書きます。
ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
最近いろいろ忙しかったので、ほとんど何もしていないです。
（就活などが忙しいと言い訳させてください・・・）
経過
今回は準備はしていないけど、とりあえず出て、A・B問題までは手堅くいこうと思って出ました。
A問題が簡単だったので1分ほどで解き、B問題にとりかかりました。
しかし、B問題の意味がいまいちわかりません。
問題文を見ても、1秒ごとに更新とも読み取れますし、途中で捕まるとダメとも読み取れます。
（問題設定ガバガバ過ぎやしませんか・・・）
とりあえず、鬼ごっこなので間で捕まってもダメと読んで、提出しました。
そして、C問題にとりかかって開始から30分くらいでB問題が間違っているのに気づきました。
そう、結果を見ずに次の問題に取り組んでしまったんですね。
B問題の結果は１つのテストケースだけがWAとなっていました。
今回は、ここではまってしまいました。
結局解消方法がわからず、C問題を解くことで逆転を目指すも、解けず・・・
開始以来初の大失敗で幕を閉じました。
結局原因は割り算時のキャスト不足です。
なんで気づかなかったんでしょう。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long A = sc.nextLong(); long V = sc.nextLong(); long B = sc.nextLong(); long W = sc.nextLong(); long T = sc.nextLong(); long dis = Math.abs(A-B); long speed = V - W; if(speed <= 0) { System.out.println("NO"); }else if((double)dis / speed <= T){ System.out.println("YES"); }else { System.out.println("NO"); } } }
結果
結果は特にいうことはありません。
ただただ、大惨敗です。
正直、記事にするのも迷いました。
というわけで、東京海上日動プログラミングコンテスト 2020の結果でした。
本日のABCで巻き返したいと思います。
ワーシャルフロイド法について
またまたAtCoderの記事です。
Web開発の記事は次回の予定です。
ちなみに前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
ワーシャルフロイド法とは
全頂点の最小の重みの和（最短経路など）を求めるときに使います。
ダイクストラ法と違い、重みに負の値があるときも計算可能です。
計算量はO(V^3)なので、時間はかかります。
ただし、負の閉路（重みの和が負となる閉路）があるときは正しい答えを出せません。
しかし、負の閉路があることの検出は可能です。
説明についてはこちらのサイトがわかりやすいかなと思います。
triple-four.hatenablog.com
どのように解くのか（Javaの場合）
ライブラリを作って以下のサイトに上げました。
github.com
使い方は以下のような感じです。
//重さを格納する配列 long[][] w = new long[N][N]; //大きい値の設定 long INF = 10000000L; //ワーシャルフロイド法用のインスタンスを作成 WF wf = new WF(c, INF); //各重みを設定 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { c[i][j] = sc.nextLong(); } } //すべての頂点間の最小の重みの和（最短距離）を返す long[][] min_w = wf.getAllDis(); //負の閉路検出(必ずgetAllDisの後で行う) boolean isNegativeCycle = wf.isNegativeCycle();
作ったライブラリを使って２問ほど解いてみました。
1つ目は、AtCoder Beginner Contest 079 D - Wall です。
atcoder.jp
この問題はワーシャルフロイド法を使うことさえわかってしまえば、あとは1と各数字との最小の重みの和を求めるだけです。
このように、最短経路でないときも使えるんですね。
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 H = sc.nextInt(); int W = sc.nextInt(); long[][] c = new long[10][10]; long INF = 10000000; WF wf = new WF(c, INF); for(int i=0; i<10; i++) { for(int j=0; j<10; j++) { c[i][j] = sc.nextLong(); } } long[][] min_c = wf.getAllDis(); long min_maryoku = 0; int[][] A = new int[H][W]; for(int i=0; i<H; i++) { for(int j=0; j<W; j++) { A[i][j] = sc.nextInt(); if(A[i][j] != -1 && A[i][j] != 1) { min_maryoku += min_c[A[i][j]][1]; } } } System.out.println(min_maryoku); } //ワーシャルフロイド法 public static class WF{ long[][] d; long INF; public WF(long[][] d, long INF) { this.d = d; this.INF = INF; //初期化 for(int i=0; i<d.length; i++) { Arrays.fill(d[i], INF); } //自分自身との距離を0に設定 for(int i=0; i<d.length; i++) { d[i][i] = 0; } } //全頂点間の最短距離(重みに負の値あり)(ワーシャルフロイド法)(O(V^3)) public long[][] getAllDis(){ long[][] new_d = new long[d.length][d.length]; System.arraycopy(d, 0, new_d, 0, d.length); for(int k=0; k<new_d.length; k++) { for(int i=0; i<new_d.length; i++) { for(int j=0; j<new_d.length; j++) { if(new_d[i][k] != INF && new_d[k][j] != INF) { new_d[i][j] = Math.min(new_d[i][j], new_d[i][k]+new_d[k][j]); } } } } return new_d; } //負の閉路検出(O(V)) public boolean isNegativeCycle() { for(int i=0; i<d.length; i++) { if(d[i][i] < 0) { return true; } } return false; } } }
2つ目は、AtCoder Beginner Contest 074 D - Restoring Road Network です。
atcoder.jp
この問題は水色diffです。
水色レベルになってくると、考察が必要になってきます。
各頂点間の最短距離がすでに与えられているので、
ワーシャルフロイド法を使って、
他の頂点を経由した方が距離が短くなる場合は-1、
別の経由地を使って最短距離と同じになる場合はその2点間のエッジを切ればよいです。
この解答ではグラフを使わず、あらかじめ与えられる最短距離をすべて加え、
エッジを切る際は代わりにその2点間の最短距離を引きます。
この時注意するのは、エッジを切った情報を記録しておかないと2種類以上最短経路がある場合種類の数だけ引いてしまうので、エッジを切った情報を記録するようにする点です。
（ここでWAを出しました。）
最終的な解答はこちらです。
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(); long[][] A = new long[N][N]; long ans = 0; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { A[i][j] = sc.nextLong(); ans += A[i][j]; } } //2点間がつながっているか boolean[][] connected = new boolean[N][N]; for(int i=0; i<N; i++) { Arrays.fill(connected[i], true); } for(int i=0; i<N; i++) { connected[i][i] = false; } for(int k=0; k<N; k++) { for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { //別の経由地を通ったほうが距離が短くなる場合 if(A[i][j] > A[i][k] + A[k][j]) { System.out.println(-1); return; } //別の経由地を通っても最短距離になる場合 else if(connected[i][j] && i != k && j != k && A[i][j] == A[i][k] + A[k][j]) { ans -= A[i][j]; connected[i][j] = false; //2重で引くのを防ぐ } } } } //無向グラフなので2で割る ans /= 2; System.out.println(ans); } }
というわけで、ワーシャルフロイド法についての記事でした。
まだ、ベルマンフォード法と最小全域木問題があるので、そこについても勉強したいと思います。
今週末はABCがないみたいなので、次回のABCまでにこの2つを勉強したいと思います。
ABC169のD問題について【Java】
今回もAtCoderの記事です。
昨日の解けなかったD問題の復習をしました。
昨日のABC169の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
コンテスト中に出した答え
コンテスト中に出した答えはこちらです。
エラトステネスの篩を応用して解こうとしましたが、素数判定に使う配列の個数がintを超えてしまったため、うまくいきませんでした。(WAです)
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int sqrt = (int)Math.sqrt(N); boolean[] isPrime = isPrimeN(sqrt); long ans = 0; for(int i=2; i<=sqrt; i++) { long n = N; if(isPrime[i]) { for(long j=i; j<=N; j*=i) { if(n >= 2 && n % j == 0) { ans++; n /= j; }else break; } } } if(ans == 0 && N >= 2) ans++; System.out.println(ans); } //n以下のすべての数の高速な素数判定(エラトステネスの篩) public static boolean[] isPrimeN(int n) { boolean[] isPrime = new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; //割れる数はsqrt以下 for(int i=2; i<=Math.sqrt(n); i++) { if(isPrime[i]) { for(int j=i*i; j<=n; j+=i) { isPrime[j] = false; } } } return isPrime; } }
修正した結果
Twitterを見てると解法らしきものが1文ほどで書いてあったので、それをもとに自力で修正してみました。
解法としては素因数分解を使い、同じ数のうちは1個たまったらカウントし、次は2個たまったらカウントし・・・という風にカウントするまでにたまる上限の数を1ずつ増やしていきました。
自作の素因数分解用のライブラリでは、最小の約数を返すようになってるので、例えば24の場合は
2, 2, 2, 3
と値を返すので、2が1個たまったら答えを+1、次は２が2個たまったら答えを+1、約数の値が変わったらまた3が1個たまったら答えを+1とし、これを繰り返すことで最後に答えの値を返します。
プログラムは次のような感じです。（もうちょっときれいに書けた気もする）
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int ans = 0; long n = N; long before_yakusuu; long yakusuu = -1; long count = 0; //指数 long limit = 0; //現在の必要上限(1, 2, 3, ...と増やしていく) while(n >= 2) { before_yakusuu = yakusuu; yakusuu = fact(n); if(yakusuu == -1) { break; } if(yakusuu != before_yakusuu) { count = 1; limit = 0; }else { count++; } if(count > limit) { ans++; limit++; count = 0; } n /= yakusuu; } System.out.println(ans); } //最小の約数を返す(素因数分解用) public static long fact(long n){ if(n < 2) return -1; for(long i=2; i<=Math.sqrt(n); i++) { if(n % i == 0) return i; } return n; } }
というわけで、ABC169のD問題の復習でした。
コンテスト中には、素因数分解を使ったアプローチでは何となくTLEになるのではと思っていましたが、間違いでした。
今回は完全に間違ったアプローチで解いてしまったので、そこから時間内に修正できるように練習を重ねていきたいです。
AtCoder Beginner Contest 169に参加しました！ (ABC169)
AtCoder Beginner Contest 169 (ABC169) に参加しました。
やってしまったな・・・という感じです。
感想を書いていきます。
ちなみに昨日の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
昨日からの進捗はありません。
これが原因かなという感じです。
経過
A問題はとても簡単だったので、例を試さずに提出してACしました。
B問題ではオーバーフローをし、1WAしてしまいました。
オーバーフローするかもしれないけどまあいいか、と思って提出してしまったのですが、それが仇になりました。
C問題はdoubleの精度の問題だと思って、小数を100倍してから答えを100割ってWAでした。
なぜなんでしょうか。ちょっとわかりません。
結局BigDecimalを使って書き直し、ACしました。
D問題についてはエラトステネスの篩を応用すればできそうだと思いましたが、Nが10^12と大きいので配列だと扱えません。
何を思ったかNのルートまでを調べればいいと勘違いし、WA。
Nのルート以上でも素数があることに気づき、どうにかNまでの素数判定を実装しようとするも間に合いませんでした。
（どうやら素因数分解だったようですね。[23:11追加]）
念のため、B問題とC問題の解答を載せておきます。（Javaですけど）
B問題
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[] A = new long[N]; for(int i=0; i<N; i++) { A[i] = sc.nextLong(); if(A[i] == 0) { System.out.println(0); return; } } long ans = A[0]; for(int i=1; i<N; i++) { if(A[i] <= (1000000000000000000L / ans)) { ans *= A[i]; }else { System.out.println(-1); return; } } System.out.println(ans); } }
C問題
import java.math.BigDecimal; import java.math.RoundingMode; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); BigDecimal bA = new BigDecimal(A); BigDecimal bB = new BigDecimal(B); BigDecimal ans = bA.multiply(bB); ans = ans.setScale(0, RoundingMode.DOWN); System.out.println(ans); } }
結果
A～Cの３完です。
今回は痛いところを突く問題が多く、苦手なタイプの問題でした。
自分の勉強の甘さを強く感じました。
D問題は解けそうで解けないのがすごくもやもやしますね。
しっかりと復習したいと思います。
というわけで、ABC169の結果でした。
自分の甘さを感じて大反省という感じです。
今回のD問題はどの色の難易度かはわかりませんが、解くべき問題だったような気がするので、次回までには解けるようにしていきたいです。
NOMURA プログラミングコンテスト 2020に参加しました！(AtCoder)
NOMURA プログラミングコンテスト 2020に参加しました。
今回はARCクラスということでC問題以降が難しかったです。
感想を書いていきたいと思います。
ちなみに、前回のABC168の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
前回のコンテスト（もう2週間前になりますね）から準備してきたことはこちらです。
- ABC167, ABC168の解けなかったD問題の見直し
- ワーシャルフロイド法（の一部）
ワーシャルフロイド法についてはもう少し問題を解いて、近いうちに記事にします。
経過
今回は問題の配点が100-200-600-700-900-1000だったので、C問題以降はかなり難しいと予想し、A・B問題の早解きを狙いました。
A問題については問題の意味が最初わからなかったものの、入力例を見て意味を理解し、3分ほどで解きました。
B問題については解法を考えることに時間がかかりましたが、冷静に考えれば?にDを入れればいいことに気づき、比較的時間をかけずに解けました。
（?Dの時、PDとしてもDDとしても同じように博士・PD 指数が1増えるため）
A・B問題でトータル9分ほどで、良いスピードで解けたんじゃないかと思います。
念のため、私の答えを載せておきます。（Javaですけど）
A問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int h1 = sc.nextInt(); int m1 = sc.nextInt(); int h2 = sc.nextInt(); int m2 = sc.nextInt(); int K = sc.nextInt(); int hm1 = h1 * 60 + m1; int hm2 = h2 * 60 + m2; System.out.println(hm2-hm1-K); } }
B問題
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String T = sc.next(); T = T.replace("?", "D"); System.out.println(T); } }
結果
A・Bの2完でした。
過去最高パフォーマンスです！
緑になるためにこれからも頑張ります。
というわけで、NOMURA プログラミングコンテスト 2020の結果でした。
明日もABCがあるので、この調子で頑張りたいです。
Web開発の勉強５- サーバーサイドプログラミング入門３
お久しぶりの投稿となってしまいました。
今回はWeb開発の勉強に関する記事です。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
前回、1年間キャンペーンに申し込んでキャンペーンが適用されるのかわからないと書きましたが、無事適用されたみたいです。
N高の授業システム、N予備校の無料キャンペーンに参加頂いた皆様に「N予備校生」の権限を付与しました。設定から確認ください。応募条件を満たしているのに付与されていない方は記載事項の不備の可能性があります。
— Ｎ高等学校（学校法人角川ドワンゴ学園） (@nhigh_info) May 28, 2020
名前、Twitter ID、N予備校IDを記載して問い合わせください→https://t.co/X3oN02Vg6x
ちゃんと「N予備校生」になってます。
こんなに充実した教材を1年間も無料にしていただき、本当にありがとうございます。
これからもN予備校を使って勉強に励みます。
内容のほうですが、今回はこの3章の27. デザインの改善 まで終わりました。
具体的な内容としては次のような感じです。
- SQLを使わずデータベース（PostgreSQL）を使う方法（sequelize）
- テンプレートCSSの利用（Bootstrap）
内容盛りだくさんです。
ダイクストラ法について
今回はAtCoderの記事です。
ちなみに、昨日AGCがあったのですが、ちょっとだけ問題を覗いて解けそうになかったので早めに退散しました。
次回からはratedの対象が2000～になるみたいですね。
あれだけ難しい問題がそろっているので、対象を絞るのも仕方のないことなのかなと思います。
（昨日は1問も解けなくてもレートが上がった方がそこそこいたようですし）
次回のNOMURA プログラミングコンテスト 2020 (ARCクラス) には参加する予定です。
さて、今回はダイクストラ法について勉強しました。
ダイクストラ法とは
最短経路を求めるアルゴリズムです。
BFSとの違いは、BFSはグラフの辺の重みが等しい時にしか使えませんが、ダイクストラ法は辺の重みが正であればそれぞれ重みが違っても使うことができます。
BFSは計算量がO(V+E)で解けますが、ダイクストラ法はO(ElogV)です。
基本的にBFSで解ける場合はBFSで解くという感じですね。
このアルゴリズムの考え方は以下のサイトがわかりやすかったです。
https://nw.tsuda.ac.jp/lec/dijkstra/
どのように解くのか（Javaの場合）
ライブラリを作ってGithubに上げました。
github.com
このライブラリの使い方について簡単に説明します。
まずグラフを作ってそれを引数としてDijkstraクラスのインスタンスを作ります。
次に、問題文で求められているものに必要なメソッドを呼び出します。
例えば、下のような感じです。
//無向グラフの作成 UDGraph g = new UDGraph(n); //インスタンスを生成 Dijkstra dk = new Dijkstra(g); //メソッドを呼び出す（この場合、最短経路を返す） Deque<Integer> path = dk.getMinPath(a, b);
作ったライブラリを使って、1つ問題を解いてみました。
解いた問題は、JOI 2008 予選 6 - 船旅 です。
atcoder.jp
自作のライブラリの部分はスペースの都合上、省きました。
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.PriorityQueue; import java.util.Queue; 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 k = sc.nextInt(); UDGraph g = new UDGraph(n); Dijkstra dk = new Dijkstra(g); while(sc.hasNext()) { int num = sc.nextInt(); if(num == 0) { int a = sc.nextInt(); int b = sc.nextInt(); long cost = dk.getMinWeight(a, b); if(cost == Long.MAX_VALUE) System.out.println(-1); else System.out.println(cost); }else if(num == 1) { int c = sc.nextInt(); int d = sc.nextInt(); long e = sc.nextLong(); g.addEdge(c, d, e); } } } //ここから下は自作のライブラリ }
というわけで、ダイクストラ法についてでした。
久しぶりに週末にAtCoderのコンテストがないので変な気分です。
（慣れって怖いですよね。）
来週の週末はNOMURAさんのコンテストと、ABCがあるのでそこまでに練習量を増やせて行けたらなと思います。
Web開発の勉強４- サーバーサイドプログラミング入門２
今回はWeb開発の勉強の記事です。
第4回も前回と引き続き、Node.jsを用いたサーバーサイドプログラミングの勉強です。
このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
内容
教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico
5月31日まで無料です。
追加で応募者全員に1年間無料にするキャンペーンをしていたのですが、もう終わってしまっています。
ちなみに、私は申し込んだのですが、キャンペーンが適用される場合、連絡は来るのでしょうか・・・
期限後も連絡がないので、6月1日からキャンペーンが適用されるのか現時点ではわかりません。
今回はこの3章の18. 認証で利用者を制限する まで終わりました。
内容としては次のような感じです。
- HTTPサーバーとログ保存
- フォームを使ったGETとPOSTの場合の処理
- Pugを使った動的なフォームの作成
- Herokuを使ったWebサービスのデプロイ
いよいよ本格的にWeb開発という感じですね。
中身としては楽しくなってきました。
ちなみに、VirtualBoxでSimlinkエラーが出た時の対処法は以下の記事が役に立ちました。
var.blog.jp
感想
入門編にもかかわらず、結構重いなという感想は変わりません。
ただ、この入門編が終われば、Web開発やってますと言っても恥ずかしくないレベルの知識は身につくと思います。
個人的には、3章が終わった時点で普通のWebアプリが作れそうなので、3章が終わったら一度自分で何か作ってみようかなと思います。
というわけで、Web開発の勉強の記事でした。
まだ、3章はあと半分ほどありますが、着実に進めていきたいと思います。
3章が5月末までに終わればいいかな・・・
ABC168のD問題で解法が同じなのにTLEしてしまったわけ【Java】
今回はABC168の復習をしました。
先日のABC168のD問題で、解法が全く同じにもかかわらずTLEを出し続けて沼にはまりました。
それが悔しかったので、この原因を調べてみました。
ちなみにABC168の結果がこちらです。
developer-bpeldi2oerkd8.hatenablog.com
コンテスト中に出した答え
コンテスト中に出した答えはこちらです。(長いですけど)
ちゃんとBFSを使って解いているにも関わらず、TLEしました。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; 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(); 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)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); while(!queue.isEmpty()) { Node n = queue.poll(); //訪問済み visited[n.value-1] = true; for(Edge edge : n.edges) { Node node = edge.to; if(!queue.contains(node) && !visited[node.value-1]) { queue.add(node); if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } } //一般的なグラフ public static class Graph{ int n; Map<Integer, Node> nodes; //(ノード番号, ノード) //1~Nまでをもつグラフ public Graph(int n) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(i+1, new Node()); } } public Graph(int n, int[] values) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(values[i], new Node(values[i])); } } public Node getNode(int node_n) { //ノード番号を指定してノードを取得 return nodes.get(node_n); } public void addEdge(Node from, Node to) { //重みが1のグラフの場合(重みが均等な場合にも場合によっては使える) from.edges.add(new Edge(to, 1)); } public void addEdge(Node from, Node to, long weight) { //エッジの重みが異なる場合 from.edges.add(new Edge(to, weight)); } public void removeEdge(Node from, Node to) { //指定したノード間のエッジを削除 from.edges.remove(new Edge(to, 1)); } } public static int count = 0; //ノードを表すクラス public static class Node{ int value; List<Edge> edges; boolean visited = false; Node root; public Node(){ value = count+1; edges = new ArrayList<Edge>(); count++; } public Node(int value) { this.value = value; edges = new ArrayList<Edge>(); } @Override public boolean equals(Object obj) { if(obj instanceof Node) { Node n = (Node)obj; if(this.value == n.value) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.value); } } //エッジを表すクラス public static class Edge{ Node to; //行き先 long weight; //重み public Edge(Node to, long weight) { this.to = to; this.weight = weight; } @Override public boolean equals(Object obj) { if(obj instanceof Edge) { Edge e = (Edge)obj; if(this.to.equals(e.to)) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.to); } } }
原因の分析
TLEになった原因をJavaの実行時間を測るSystem.nanoTimeを使って地道に調べました。
すると、意外にも自作のライブラリのほうではなく、BFSの実装部分のほうに原因があるとわかってきました。
（自作のライブラリが原因だと思ってかなりの時間を使ってしまったのは内緒です。）
さらに絞り込んでいくと、どうやらif(!queue.contains(node) && !visited[node.value-1])で時間を消費していることがわかってきました。
どう考えても、!visited[node.value-1]には時間がかかるはずがないので、（配列だからO(1)でとってこれるはず）
原因は!queue.contains(node)にあると推測しました。
TLEになった原因
結局TLEになった原因は、queueに多くの要素が含まれるようになったとき、queue.containsに多くの時間がかかってしまうことでした。
queue.containsメソッドの内部処理はよく知りませんが、要素を1つずつ確認していくのであればO(N)の時間がかかってしまうので、ここで時間がかかっていたのだと思います。
対処法としては、queueに加えるときに、visited=trueとして、訪問済みにしてしまうことです。
こうすれば、queueに加えるときに訪問済みかどうか調べるだけでいいので、O(1)の時間しかかかりません。
修正したプログラムはこちらです。
（自作のライブラリの部分は同じなので省略しています。）
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; 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(); 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)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); visited[0] = true; while(!queue.isEmpty()) { Node n = queue.poll(); for(Edge edge : n.edges) { Node node = edge.to; if(!visited[node.value-1]) { queue.add(node); //queueに加えたときに訪問済みにしてしまう visited[node.value-1] = true; if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } }
さらに、これだと制限時間ギリギリなので、入出力を変えてみました。
入力にネットで拾ってきたFastScannerを使ったバージョンと、それに加え、出力をPrintWriterにしたバージョンの実行時間を計ってみた結果がこちらです。
上から、
FastScanner+PrintWriter (563ms)
FastScannerのみ (1099ms)
そのまま (1648ms)
です。
いや、すごい威力ですね。
今回のように、入出力が長い行になる場合は迷わずFastScanner, PrintWriterを使ったほうがよさそうです。
というわけで、ABC168のD問題の復習でした。
BFSは知っていたのに時間内にACできなかったのは悔しいですが、結果的に勉強になりました。
BFSのテンプレを今回の形に修正しておきます。
次こそは、４完できるように頑張ります。
AtCoder Beginner Contest 168に参加しました！ (ABC168)
AtCoder Beginner Contest 168 (ABC168) に参加しました。
やはり演習不足を強く実感しました・・・。
感想を書いていきます。
ちなみに、前回の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
準備
前回から勉強したのは次の1つです。
- 累積和
やはりどう考えても勉強不足ですね。
演習量の不足も強く感じました。
経過
スタート後、いつもの通りA・B問題をサクッと解き、C問題に進みました。
C問題は余弦定理を使う問題でしたね。
数学は苦手ではないので、20分ほどで解きました。
提出した回答がこちらです。
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); int B = sc.nextInt(); int H = sc.nextInt(); int M = sc.nextInt(); int pass_time = H*60 + M; double digA = (0.5 * (double)pass_time) % 360; double digB = (6 * pass_time) % 360; double C = Math.sqrt(A*A + B*B -2*A*B*Math.cos(Math.toRadians(Math.abs(digA-digB)))); System.out.println(C); } }
cosの中身がラジアンなことを忘れて、ちょっと詰まりましたが、ノーミスでここは通しました。
問題はD問題でグラフの問題と最短経路なのでBFSだなと思い、実装を進めました。
ただ、まずNoを出す条件がわからなかったので、ここでまず詰まりました。
考えた結果、閉路と同じ感じでやればいいのかと思い、やってみたところ間違ってはいないようでした。
ただ、要素の数が大きいとき、TLEが出てしまい、ここを解消できずにコンテストが終わりました。
なぜ、TLEが出ているのか理由がわかっていません。
念のため、提出したものを載せます。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Queue; 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(); 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)); } boolean[] visited = new boolean[N]; Arrays.fill(visited, false); //BFS Queue<Node> queue = new ArrayDeque<>(); queue.add(g.getNode(1)); while(!queue.isEmpty()) { Node n = queue.poll(); //訪問済み visited[n.value-1] = true; for(Edge edge : n.edges) { Node node = edge.to; if(!queue.contains(node) && !visited[node.value-1]) { queue.add(node); if(node.root != null) { System.out.println("No"); return; }else { node.root = n; } } } } System.out.println("Yes"); for(int i=2; i<=N; i++) { System.out.println(g.getNode(i).root.value); } } //一般的なグラフ public static class Graph{ int n; Map<Integer, Node> nodes; //(ノード番号, ノード) //1~Nまでをもつグラフ public Graph(int n) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(i+1, new Node()); } } public Graph(int n, int[] values) { this.n = n; nodes = new HashMap<>(n); for(int i=0; i<n; i++) { nodes.put(values[i], new Node(values[i])); } } public Node getNode(int node_n) { //ノード番号を指定してノードを取得 return nodes.get(node_n); } public void addEdge(Node from, Node to) { //重みが1のグラフの場合(重みが均等な場合にも場合によっては使える) from.edges.add(new Edge(to, 1)); } public void addEdge(Node from, Node to, long weight) { //エッジの重みが異なる場合 from.edges.add(new Edge(to, weight)); } public void removeEdge(Node from, Node to) { //指定したノード間のエッジを削除 from.edges.remove(new Edge(to, 1)); } } public static int count = 0; //ノードを表すクラス public static class Node{ int value; List<Edge> edges; boolean visited = false; Node root; public Node(){ value = count+1; edges = new ArrayList<Edge>(); count++; } public Node(int value) { this.value = value; edges = new ArrayList<Edge>(); } @Override public boolean equals(Object obj) { if(obj instanceof Node) { Node n = (Node)obj; if(this.value == n.value) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.value); } } //エッジを表すクラス public static class Edge{ Node to; //行き先 long weight; //重み public Edge(Node to, long weight) { this.to = to; this.weight = weight; } @Override public boolean equals(Object obj) { if(obj instanceof Edge) { Edge e = (Edge)obj; if(this.to.equals(e.to)) return true; else return false; } return false; } @Override public int hashCode() { return Objects.hash(this.to); } } }
結果
A～Cの３完でした。
やはり、D問題が鬼門で、演習量がまだ足りてないなと感じました。
このままだと緑まで遠いので、もっと頑張ります。
というわけで、ABC168の結果でした。
やはり演習量を増やすことが大事だと思ったので、次回までには演習量を増やしたいと思います。
