[JAVA] ABC --126 --A & B & C & D

AtCoder ABC 126 A&B&C&D AtCoder - 126

A - Changing a Character

――I used to write it like this, but is it difficult to read if I review it again? ?? ??

	private void solveA() {
		int n = nextInt();
		int k = nextInt() - 1;
		StringBuilder builder = new StringBuilder(next());

		out.println(builder.replace(k, k + 1, builder.substring(k, k + 1).toLowerCase()).toString());
	}

――Hmm. Not good enough. .. ..

	private void solveA() {
		int n = nextInt();
		int k = nextInt();
		String[] wk = next().split("");
		wk[k - 1] = wk[k - 1].toLowerCase();

		String res = Arrays.stream(wk).collect(Collectors.joining(""));

		out.println(res);
	}

B - YYMM or MMYY

	private void solveB() {
		int wk = nextInt();

		int front = wk / 100;
		int back = wk % 100;

		if ((0 < front && front <= 12) && (back <= 0 || back > 12)) {
			out.println("MMYY");
		} else if ((0 < back && back <= 12) && (front <= 0 || front > 12)) {
			out.println("YYMM");
		} else if ((0 < front && front <= 12) && (0 < back && back <= 12)) {
			out.println("AMBIGUOUS");
		} else {
			out.println("NA");
		}

	}

C - Dice and Coin

-Use Big Decimal because it is troublesome to round

Example 1: Because you roll the three-sided die

If 1 is rolled, the coin must be displayed 4 times in a row. If 1 appears: $ 1 x 2 x 2 x 2 x 2 = 16 $ Probability: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 4 $

If you get a 2, you need to get a coin table 3 times in a row If 2 appears: $ 2 x 2 x 2 x 2 = 16 $ Probability: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 3 $

If 3 is rolled, the coin must be displayed twice in a row If 3 appears: $ 3 x 2 x 2 = 12 $ Probability: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 2 $

The total (when 1 comes out, when +2 comes out, when +3 comes out) is as follows $ \frac{1}{3} × (\frac{1}{2})^4 + \frac{1}{3} × (\frac{1}{2})^3 +\frac{1}{3} × (\frac{1}{2})^2 = \frac{7}{48} $

Simplify the formula by wrapping it ** (Since it is troublesome to think about rounding at the time of implementation, division is brought to the end) ** $ ((\frac{1}{2})^4 + (\frac{1}{2})^3 + (\frac{1}{2})^2) × \frac{1}{3} = \frac{7}{48} $

	private void solveC() {
		int n = nextInt();
		int k = nextInt();

		BigDecimal res = new BigDecimal("0");
		for (int i = 1; i <= n; i++) {
			int pow = recursiveC(i, k);
			/*
			 *The front and back of the coin is 1/2 so 0.5 to the nth power
			 *0 when the die surface is i.5^pow
			 */
			BigDecimal powB = new BigDecimal("0.5").pow(pow);
			//Add
			res = res.add(powB);
		}

		//Finally, divide by the dice side at once
		out.println(res.divide(new BigDecimal(n), 11, RoundingMode.HALF_UP));
	}

	/**
	 *Returns how many times x 2 should exceed n
	 * @param i
	 * @param n
	 * @return
	 */
	private int recursiveC(int i, int n) {
		if (i >= n) {
			return 0;
		}
		return recursiveC(i * 2, n) + 1;
	}

D --Even Relation (BFS version)

Reference site

AtCoder ABC 126 D --Even Relation (400 points)

――The above reference site of Mr. Kenchon has a solution method in DFS. I referred to that. ――I have solved it with DFS myself, but I will not post it because Kenchon's site is easier to understand. ――Rather than brute force, decide one root and paint it by the evenness of the distance from there (I did not know unless I saw the explanation) ――Maybe you can go with Dijkstra? ?? ?? Let's try it next time.

	private void solveD() {
		int n = nextInt();

		int[] u = new int[n - 1];
		int[] v = new int[n - 1];
		int[] w = new int[n - 1];

		/*
		 *Create a map of edges
		 */
		Map<Integer, List<Edge>> wk = new TreeMap<Integer, List<Edge>>();

		for (int i = 0; i < n - 1; i++) {
			Edge e = null;
			List<Edge> tmp = null;

			u[i] = nextInt() - 1;
			v[i] = nextInt() - 1;
			w[i] = nextInt();
			/*
			 *The cost is unnecessary except for even and odd, so I modified it, but I didn't have to do it separately. .. ..
			 */
			int cost = w[i] % 2;
			e = new Edge();
			e.from = u[i];
			e.to = v[i];
			e.cost = cost;
			tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
			tmp.add(e);
			wk.put(e.from, tmp);

			e = new Edge();
			e.from = v[i];
			e.to = u[i];
			e.cost = cost;
			tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
			tmp.add(e);
			wk.put(e.from, tmp);
		}
		/*
		 *Queue for BFS
		 */
		Deque<Edge> ek = new ArrayDeque<Edge>();
		/*
		 *selection of the first que to explore the tree
		 *Not everything is fine, the child chooses one
		 *N vertices and N sides-Since there is only one, there is always one that meets this condition.
		 * while()Only the first queue in the list doesn't see all my destinations.
		 *Well, while()I feel like I should just put all the edges at position 0 in the queue before entering.
		 */
		for (List<Edge> edges : wk.values()) {
			if (edges.size() == 1) {
				ek.addLast(edges.get(0));
				break;
			}
		}
		//		ek.addLast(wk.get(0).get(0));
		int[] res = new int[n];
		//For storing colors
		res[0] = 0;
		while (!ek.isEmpty()) {
			Edge e = ek.removeLast();
			/*
			 *Decide the color to paint by the evenness of cost
			 */
			if (e.cost % 2 == 0) {
				//If it is an even number, both from and to have the same color
				res[e.to] = res[e.from];
			} else {
				//If it is odd, you need to paint to in a color different from from
				res[e.to] = 1 - res[e.from];
			}
			//Searching for a child in to
			List<Edge> edges = wk.get(e.to);
			for (Edge edge : edges) {
				/*
				 *To prevent parents and children from circulating
				 */
				if (e.from == edge.to) {
					continue;
				}
				/*
				 *Add to Queue because it is a search target
				 */
				ek.addLast(edge);
			}
		}

		for (int resN : res) {
			out.println(resN);
		}

	}

	/**
	 *Inner class for representing edges
	 */
	private static class Edge {
		private int from;
		private int to;
		private int cost;
	}

Recommended Posts

ABC --129- A & B & C & D
ABC --133- A & B & C & D
ABC --122 --A & B & C & D
ABC --125- A & B & C & D
ABC --130- A & B & C & D
ABC --126 --A & B & C & D
ABC --131- A & B & C & D & E
ABC --013-A & B & C
ABC --023 --A & B & C
ABC --036-A & B & C
ABC --010 --A & B & C
ABC --015 --A & B & C
ABC --128 --A & B & C
ABC --012-A & B & C
ABC --054 --A & B & C
ABC --017 --A & B & C
ABC --029- A & B & C
ABC --022 --A & B & C
ABC --019 --A & B & C
ABC --020 --A & B & C
ABC --030- A & B & C
ABC --127 --A & B & C
ABC --007 --A & B & C
ABC --132- A & B & C
ABC --026 --A & B & C
ABC --016 --A & B & C
ABC --011-A & B & C
ABC --031 --A & B & C
ABC --021 --A & B & C
ABC --025 --A & B & C
ABC --024 --A & B & C
ABC --027 --A & B & C
ABC --080- A & B & C
diverta 2019 Programming Contest A & B & C & D
AtCoder Beginner Contest 169 A, B, C with ruby
atcoder ABC113 C problem
atcoder ABC70 D problem
ABC093 C --Same Integers
atcoder ABC115 C problem
A person writing C ++ tried writing Java
Make a SOAP call in C #
Call a C function from Swift
What is a Ruby 2D array?
Convert Swift 2D array to C 2D array