bpeldi2oerkd8の開発日誌

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

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の結果でした。
やはり演習量を増やすことが大事だと思ったので、次回までには演習量を増やしたいと思います。