bpeldi2oerkd8の開発日誌

とあるひよっこエンジニアの成長の記録。

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

今回は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を使った動的なフォームの作成

いよいよ本格的に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にしたバージョンの実行時間を計ってみた結果がこちらです。
abc168_runtime_compare

上から、

FastScanner+PrintWriter (563ms)
FastScannerのみ (1099ms)
そのまま (1648ms)

です。

いや、すごい威力ですね。

今回のように、入出力が長い行になる場合は迷わずFastScanner, PrintWriterを使ったほうがよさそうです。


というわけで、ABC168のD問題の復習でした。

BFSは知っていたのに時間内にACできなかったのは悔しいですが、結果的に勉強になりました。

BFSのテンプレを今回の形に修正しておきます。

次こそは、4完できるように頑張ります。

AtCoder Beginner Contest 168に参加しました! (ABC168)

abc168_score
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);
		}
	}

}

結果

abc168_result
A~Cの3完でした。
やはり、D問題が鬼門で、演習量がまだ足りてないなと感じました。
このままだと緑まで遠いので、もっと頑張ります。


というわけで、ABC168の結果でした。
やはり演習量を増やすことが大事だと思ったので、次回までには演習量を増やしたいと思います。

累積和について

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次元累積和もあります。

実際に問題を2つ解いてみました。

1つめは 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開発の勉強3- サーバーサイドプログラミング入門1

お久しぶりの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) に参加しました!

abc167_score
AtCoder Beginner Contest 167 (ABC167) に参加しました。
うーん、ちょっと悔しいですね。
感想を書いていきます。

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

準備

前回から勉強したのは次の2つです。

今回のを見ると、そろそろDPやらないとやばそうですね・・・

経過

今回もスタートがスムーズでした。
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・・・。

原因は今の段階ではわかっていません。
この後、解説を見たいと思います。

結果

abc167_result
A~Cまでの3完です。
正直悔しいですね。
まだまだ、演習量が足りないので、増やせて行けたらと思います。


というわけで、ABC167の結果でした。
これからも引き続き、勉強を頑張っていきます。

素数について

お久しぶりとなってしまいました。

今回もAtCoderの記事です。

Web開発のほうはもう少しで記事として書けるくらいの内容までいくので、しばしお待ちください。

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

素数とは

素数とは、1とその数字以外で割り切れない数です。(1は素数ではない)

よく某大学がネタにしているやつですね笑

AtCoderでは、素数の問題として、素数かどうかを判定する問題、n以下の素数の数を求める問題が出ます。

どのように解くのか(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】

abc166_score
先日のAtCoder Beginner Contest 166 (ABC166)で茶色になりました!

茶色を達成したときの結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

天才は見向きもしない色なのですが、我々凡人にとっては、茶色になるのは意外と大変です。

(どのくらい勉強するのか目安がわかりませんよね)

私も茶色くらいだったらすぐ行けるだろ、と思っていたのですが、結局達成するまでに10回かかってしまいました。

おそらく、もっとかかる方はかかると思います。

今回は備忘録として、茶色になるまでにやったことを書きたいと思います。

茶色になるまでに停滞している方、これから茶色になるために勉強しようとしている方の参考に少しでもなれば幸いです。

AtCoderの常識を覚える

ある程度、AtCoderをやっていると自然に覚えていくものなのですが、AtCoder界隈で常識とされていることがそこそこの量あります。

まずは、AtCoderに何回か参加して、こういった常識を知ることが大切だと思います。

ぱっと思いついた常識はこんな感じです。

  • コンテストに積極的に参加する(特に、初心者のうちはAtCoder Beginner Contest (ABC) だけ参加すればよい)
  • A問題から順に解いていく(ただし、回によっては難易度が入れ替わっていることがあるので、わからなければ1つ先の問題も見る)
  • 必ず、自分のパソコンに開発環境を用意する(ブラウザ上だとどうしても速度が遅いので)
  • 自分にプログラミングの基礎能力が身についていない場合は、もう少し勉強してから参加する(ガチのプログラミング初心者は周りのレベルが高すぎて、普通に心が折れます)
  • AtCoderのための便利なサイトを知り、登録する(Aizu Online Judge (AOJ)、AtCoder Problemsなど)

3つ目については長くなるので、次の項目を見てください。

4つ目については、あまりネットで言われていませんが、AtCoderは正直ガチの初心者向けではないことです。

回にもよりますが、A・B問題がスラスラと解けるレベルでないと挫折してしまうと思うので、PaizaやProgateなどである程度力をつけてから参加したほうがいいかもしれないです。
paiza.jp

prog-8.com

自分のパソコンに開発環境を構築する

何回かコンテストに参加すると、必ず通る道だと思います。

やはりAtCoderでは速さを競うので、ブラウザ上では遅いと感じます。

なので、必然的に自分のパソコン上に開発環境が必要になってきます。

JavaではEclipseという便利な開発環境があります。

これは、メソッドや変数などを自動で補完してくれ、よく使う処理も便利なコマンドで補完してくれます。

ちなみに、Eclipseはこちらのサイトでダウンロードできます。
mergedoc.osdn.jp

こちらのサイトの最新版のJava版のFull Editionをダウンロードすれば大丈夫です。

インストール方法、使い方などはこちらのサイトが参考になります。
www.sejuku.net

www.sejuku.net

他にも、AtCoderで人気なC++Pythonでも使える環境として、Visual Studio Code (VS Code) があります。(人気ですね)
azure.microsoft.com

AtCoderで必要な知識をつける

ここからは、よく他の方も紹介されているアルゴリズムやデータ構造、計算量に関することです。

やはり、色を変えるためにはこれらの知識が不可欠だと感じます。(私も今勉強中です)

こちらのサイトが非常にわかりやすいです。
qiita.com

こちらのサイトにあるように、基本的な文法に加え、まず全探索になれることから始まります。

あと、計算量に関する知識も必要です。

ただ、現段階では私もそこまで詳しくなく、茶色の段階ではAtCoderで時間制限に間に合うのは10^ 9回以下という知識さえあればいいと思います。

そして、ここまで終わったら、さらに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 に参加しました!

abc166_score
昨日に引き続いて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);

	}


}

結果

abc166_result
A~Dの4完です!まさかこんなに早く達成できるとは思っていなかったので、とても嬉しいです!
そして、3度目の緑パフォです!
これからは緑色になるために、4完を安定できるように勉強を続けます。


というわけで、ABC166の結果でした。
自分はどちらかというと数学的な問題が出たほうがパフォーマンスがいいみたいです。
他のタイプのD問題も解けるように頑張ります!

AtCoder Beginner Contest 165 に参加しました!

abc165_score
先ほど行われた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]が0となるxの中で最大のものを取ればよいと気づいたので、何とか解けました。
初めてのD問題ACで嬉しかったです。
次は、4完を目指したいと思います。

参考になるかわかりませんが、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);

	}


}

結果

abc165_result
ABDの3完で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開発の勉強2- サーバーサイド開発の準備

書きます詐欺を繰り返していたWeb開発の勉強の記事を書きます。
第2回はサーバーサイド開発の準備です。

このシリーズの前回の記事はこちらです。(だいぶ前ですが(汗))
developer-bpeldi2oerkd8.hatenablog.com

内容

教材としては「N予備校」の「 プログラミング入門Webアプリコース 」を使ってます。
コロナの期間中は無料で提供していただけているので、本当に感謝です。
(決して回し者ではありません)
www.nnn.ed.nico

今回はこの第2章が終わりました。
内容としては、次のような感じです。

  • Linux(Ubuntu)の操作の学習
  • 仮想環境でのローカルサーバーの立て方
  • Vimの操作
  • シェルプログラミング
  • GitとGithubの使い方

中途半端に知識はあるので、知っていることも多かったのですが、意外と穴がありました。
あと、こちらで紹介されている手法は、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開発のほうについても早いうちに記事にしたいと思います。