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