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の3完でした。
やはり、D問題が鬼門で、演習量がまだ足りてないなと感じました。
このままだと緑まで遠いので、もっと頑張ります。
というわけで、ABC168の結果でした。
やはり演習量を増やすことが大事だと思ったので、次回までには演習量を増やしたいと思います。