bpeldi2oerkd8の開発日誌

とある大学院生の成長の記録。

Web開発の勉強11- 自作サービス作り4

およそ半年ぶりとなってしまいました。
今回はWeb開発の勉強の記事です。
前回は出席登録機能以外を完成させました。
developer-bpeldi2oerkd8.hatenablog.com

今回は出席登録機能とURL共有機能の追加、Herokuへのデプロイまで完成させました。

完成したもの

GitHubにも載せましたが、念のためデモ動画を載せます。

経過

経過の詳細は以下のコミット履歴を確認してください。
github.com

まずは概要を説明します。
前回からの変更点は以下の3つです。

  • 出欠登録機能の追加
  • Herokuへデプロイするためにパッケージ等のアップグレード

それぞれ簡単に説明します。

出欠登録機能の追加

前回完成していなかった出欠登録機能を完成させました。
前回はbotを使ってAPIを叩いて出欠登録ができるようにしようと思っていたのですが、時間の関係でいったん諦めました。
その代わりにN予備校の教材にあったAjaxを使った登録を実装しました。
この部分については、今後時間があればbotを使って出欠登録ができるように修正したいと思います。

URL共有機能の追加

予定ページにそのページのURLを表示し、Copyボタンを押すとクリップボードにコピーされるように変更しました。
実装はjQueryを用いて実装しています。
jQueryのclickメソッドとselectメソッドは非推奨らしいので、onメソッドとtriggerメソッドを代わりに使いました。
Bootstrap4がjQueryを必要とするため、jQueryを使いましたが、今のトレンドはReactですかね...

Herokuへのデプロイ

基本的には今までやったようにデプロイするだけでした。
Node.jsのバージョンを上げるとなぜか動かなかったのですが、pgモジュールのバージョンを上げることで解決しました。

感想

事情があって時間がかなり空きましたが、ひとまずサービスとして動くように完成できたと思います。
botとの連携については時間がかかりそうなので今回はパスしましたが、時間があるときに追加したいと思っています。
あと、今年からN予備校の入門コースの教材がDocker対応になったのでそれも時間があれば試したいと思います。

【メモ】Windows10で画面録画をするとき「録画が動作していません エラー:0x82323007」とエラーが出て録画できない場合の対処法

Windows10で画面録画をしようと思ったのですが、「録画が動作していません エラー: 0x82323007」というエラーメッセージが出て、録画できなかったので対処法を探しました。

対処法

Windows10のバージョンを1909から20H2にバージョンアップすることで解決。

原因

おそらくDirectX 12 UltimateをサポートしているバージョンでないとXbox Game Barが録画できないようになったため。
なので、バージョン2004以上に上げれば動作するようになるはず。

Web開発の勉強10- 自作サービス作り3

今回もWeb開発に関する記事です。
前回は出欠登録に使うbotを側だけ作りました。
developer-bpeldi2oerkd8.hatenablog.com

今回は予定の作成・編集・削除ページとその処理を書き、デザイン面も決めました。
後はメインのbotを使って出席登録をできるようにするだけです。
(おそらくここが大変だと思いますが)

作ったもの

削除確認ダイアログはBootstrapのModalを使って実装しました。

slackIDはユーザー一人につき1回のみslackのIDを登録することになっています。
ここのあたりの仕様はまだ詰め切れてないので、残りの部分を実装しながら修正します。

各フォームはcsurfモジュールを用いてCSRF対策を実装済みです。

  • 予定一覧ページ

f:id:bpeldi2oerkd8:20201110232303p:plain

  • 予定確認ページ

f:id:bpeldi2oerkd8:20201110232354p:plain

  • 予定作成ページ

f:id:bpeldi2oerkd8:20201110232609p:plain

  • 予定編集ページ

f:id:bpeldi2oerkd8:20201110232501p:plain

  • 予定削除確認ダイアログ

f:id:bpeldi2oerkd8:20201110232543p:plain

  • slackID登録ページ

f:id:bpeldi2oerkd8:20201110232744p:plain

経過

細かな経過はこちらのコミット履歴をご覧ください。
github.com

工夫した点は削除ボタンを押した際、確認ダイアログを作った点です。
また、苦労した点はHerokuにデプロイする際、ローカルで出なかったエラーが出て苦戦した点です。

原因はいくつかありました。
1つ目は、bootstrapとjQueryをバージョンアップさせた際、yarn installをし直してyarn.lockファイルを更新していなかったことです。
2つ目は、不要なrequireやrequireの位置がおかしかったなどrequire関係のエラーです。

ひとまず出席登録以外の機能は完成したと思います。

まだまだ改善の余地はあると思いますが(日程の追加・編集方法など)、今後はbotを使った出欠登録を完成させることを優先させたいと思います。

感想

時間はかかりましたが、出席登録機能以外を完成させました。

残りはbotを使った出席登録ですが、以前作ったlattendance-botからlattenndanceのAPIを叩き、出欠情報をデータベースに登録させたいと考えています。

うまくいくかはわかりませんが、何とか完成させたいと思います。

Web開発の勉強9- 自作サービス作り2

今回もWeb開発に関する記事です。
前回は自作サービスづくりで側だけ作りました。
developer-bpeldi2oerkd8.hatenablog.com

今回はbotの部分を作りました。

作ったもの

新たにhubotのひな型を作成し、出席登録のbotを作成しました。
今回は決まったフォーマットでメッセージを飛ばすと登録結果が返ってくるようにしました。
f:id:bpeldi2oerkd8:20201027164724p:plain

誤登録を防ぐため、メンションをつけないと反応しないようになっています。

反応する形式は、以下の3つです。

  • 出席(空白いくつでも)(月)/(日)
  • 欠席(空白いくつでも)(月)/(日)
  • 不明(空白いくつでも)(月)/(日)

経過

hubotのひな型をyoで作り、決まった形式ではないと反応しないようにbotJavascriptで実装しました。

個人的にはまったのが、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" %*

感想

botはすぐ完成させて次に行く予定だったのですが、heroku上で動かないという問題に悩まされて思ったより時間がかかりました。

今後は、登録のメッセージが飛ばされた後、APIを呼び、出欠情報をデータベース上に登録できるようにしたいと思います。

次回こそ、フォーム・データモデルの実装を行っていきたいと思います。

Web開発の勉強8- 自作サービス作り1

今回も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を使ったデザインの実装を行いました。

完成した画像はこちらです。

  • トップページ

f:id:bpeldi2oerkd8:20201010235558p:plain

  • ログインページ

f:id:bpeldi2oerkd8:20201010235644p:plain

  • ログインボタン後の遷移画面

f:id:bpeldi2oerkd8:20201010235749p:plain

  • マイページ

f:id:bpeldi2oerkd8:20201010235812p:plain

感想

今回はログイン機能とデザインを主にやりましたが、思った以上に苦戦しました。

特にログインしたときにユーザー名が表示できるようにし、プルダウンメニューでログアウトボタンを実装するのはかなり時間がかかりました。

また、GitHubでログインボタンのデザインにも悩み苦戦しました。

ただ、自分で試行錯誤して実装すると、今まで理解が浅かった部分がわかり、力になっていることを実感できました。

次回は、フォーム・データモデルの実装を行っていきたいと思います。

Web開発の勉強7- 実践サーバーサイドプログラミング2

今回もWeb開発に関する記事です。
ようやく夏のインターンシップが終わり、一息したところで残っていたWeb開発入門のコースを終わらせました。

このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

内容

教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico

内容のほうは、4章をすべて終わらせました。

具体的な内容としては以下のような感じです。

  • 「予定調整くん」というサービスを今までの知識を用いて制作

具体的には設計の部分からデザイン・セキュリティ対策まで実装しました。

感想

ひとまずこれで入門コースが終わり、Web開発に関する基本的な知識がついたと思います。
今回得た知識を使って、簡単なサービスを設計から一度やってみて完成させようと思います。
その経過をこのブログに載せたいと思います。


というわけで、Web開発の勉強の記事でした。
この入門コースはボリュームがあり、大変でしたが大変実のあるものになったと思います。
実際にExpressを用いて自分でサービスを作ることで、知識をより強固なものにしたいと思っています。

Web開発の勉強6- 実践サーバーサイドプログラミング1

お久しぶりです。
今回はWeb開発に関する記事です。

インターンシップ・研究などと忙しく、なかなかAtCoder、Web開発に手がつかない時期が続きました。
ここ1か月は時間が取れるようになってきたので、再開したいと思います。

このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

内容

教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico

無料登録期間中に登録したので、1年間は無料です。
ありがとうございます。

内容のほうは、4章の 15.テーブルの集計 まで終わりました。

具体的な内容としては以下のような感じです。

  • Webフレームワーク(Express)を使った開発の基礎

いよいよ本格的なWeb開発という感じですね。
Web APIの開発までカバーしています。

感想

これでWeb開発の基本はほとんど終わり、あとは実際のサービス開発の練習のみとなりました。
無料でこの教材が使えるのは大きく、とても勉強になります。
(有償でも受ける価値はあると思います。これはステマでもなんでもなく。)
このコースが終わった後は、実際に勉強した内容を使って1つサービスを作る予定です。


というわけで、Web開発の勉強の記事でした。
残りは予定調整くんという架空のサービスを作る練習です。
夏休み中には自作のサービスを1つ完成させたいなと思っています。

エイシング プログラミング コンテスト 2020 に参加しました (AtCoder)

エイシング2020
お久しぶりとなります。
エイシング プログラミング コンテスト 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_result
久しぶりにしてはという感じですが、やはり問題を解かないとレベルは上がっていきませんね。
他のことでも忙しいのですが、なんとか時間を作って頑張りたいと思います。


というわけで、エイシング プログラミング コンテスト 2020の結果でした。
次回も参加したいと思います。

東京海上日動プログラミングコンテスト 2020に参加しました(AtCoder)

東京海上日動2020_score
東京海上日動プログラミングコンテスト 2020に参加しました。
結果は上にある通り、初めてレートが下がりました・・・(つらい)
反省点を書きます。

ちなみに、前回のABCの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

準備

最近いろいろ忙しかったので、ほとんど何もしていないです。
(就活などが忙しいと言い訳させてください・・・)

経過

今回は準備はしていないけど、とりあえず出て、A・B問題までは手堅くいこうと思って出ました。

A問題が簡単だったので1分ほどで解き、B問題にとりかかりました。

しかし、B問題の意味がいまいちわかりません。
問題文を見ても、1秒ごとに更新とも読み取れますし、途中で捕まるとダメとも読み取れます。
(問題設定ガバガバ過ぎやしませんか・・・)

とりあえず、鬼ごっこなので間で捕まってもダメと読んで、提出しました。

そして、C問題にとりかかって開始から30分くらいでB問題が間違っているのに気づきました
そう、結果を見ずに次の問題に取り組んでしまったんですね。

B問題の結果は1つのテストケースだけが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_result
結果は特にいうことはありません。
ただただ、大惨敗です。
正直、記事にするのも迷いました。


というわけで、東京海上日動プログラミングコンテスト 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();

作ったライブラリを使って2問ほど解いてみました。

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が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)

abc169_score
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);

	}

}

結果

abc169_result
A~Cの3完です。
今回は痛いところを突く問題が多く、苦手なタイプの問題でした。
自分の勉強の甘さを強く感じました。

D問題は解けそうで解けないのがすごくもやもやしますね。
しっかりと復習したいと思います。


というわけで、ABC169の結果でした。
自分の甘さを感じて大反省という感じです。
今回のD問題はどの色の難易度かはわかりませんが、解くべき問題だったような気がするので、次回までには解けるようにしていきたいです。

NOMURA プログラミングコンテスト 2020に参加しました!(AtCoder)

NOMURA2020_score
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);

	}

}

結果

NOMURA2020_result
A・Bの2完でした。
過去最高パフォーマンスです!
緑になるためにこれからも頑張ります。


というわけで、NOMURA プログラミングコンテスト 2020の結果でした。
明日もABCがあるので、この調子で頑張りたいです。

Web開発の勉強5- サーバーサイドプログラミング入門3

お久しぶりの投稿となってしまいました。
今回はWeb開発の勉強に関する記事です。

このシリーズの前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

内容

教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
www.nnn.ed.nico

前回、1年間キャンペーンに申し込んでキャンペーンが適用されるのかわからないと書きましたが、無事適用されたみたいです。


ちゃんと「N予備校生」になってます。
Nschool_profile

こんなに充実した教材を1年間も無料にしていただき、本当にありがとうございます。
これからもN予備校を使って勉強に励みます。


内容のほうですが、今回はこの3章の27. デザインの改善 まで終わりました。

具体的な内容としては次のような感じです。

  • SQLを使わずデータベース(PostgreSQL)を使う方法(sequelize)
  • テンプレートCSSの利用(Bootstrap)

内容盛りだくさんです。

感想

実はインターンで簡単なWeb掲示板は実装したことがあるのですが、その時はHTML, CSSなどで直接書いていました。

便利なテンプレートなどがたくさんあると知り、目から鱗でした。

特に、Bootstrapについては名前は知っていたのですが、こんなに簡単にきれいなレスポンシブデザインを作れるんですね・・・。

これからはこれを中心に使っていきたいと思います。


というわけで、Web開発の勉強の記事でした。

3章の残りはセキュリティの話ですね。

おそらく次の記事で3章は終わると思うので、終わった後はWeb掲示板を作ってみようと思います。

なんとか、3章を5月中に終わらせたいと思います。

ダイクストラ法について

今回は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があるのでそこまでに練習量を増やせて行けたらなと思います。