AtCoder ABC 021 A&B&C AtCoder - 021 ** 201905/15 postscript ** There is a solution to problem A in the comment section
――If you can use the same many times, I think you can use all 1. .. .. AC
private void solveA() {
int n = nextInt();
out.println(n);
IntStream.range(0, n).forEach(i -> out.println(1));
}
** 201905/15 postscript ** There is a code in a clean loop in the comment section
――Does it look like this without simplification?
private void solveA2() {
int n = nextInt();
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
for (int l = 0; l <= n; l++) {
if (i * 1 + j * 2 + k * 4 + l * 8 == n) {
out.println(i + j + k + l);
for (int l2 = 0; l2 < i; l2++) {
out.println(1);
}
for (int j2 = 0; j2 < j; j2++) {
out.println(2);
}
for (int k2 = 0; k2 < k; k2++) {
out.println(4);
}
for (int l2 = 0; l2 < l; l2++) {
out.println(8);
}
return;
}
}
}
}
}
}
――If the route meets the following conditions, at least there is no extra detour --Does not include start and end points ――The same town does not appear twice
Commenting out is a remnant of what I first thought about for
private void solveB() {
int n = nextInt();
int a = nextInt();
int b = nextInt();
int k = nextInt();
int[] wk = IntStream.range(0, k).map(i -> nextInt()).toArray();
Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
boolean res = tmp.entrySet().stream()
.allMatch(entry -> !entry.getKey().equals(a) && !entry.getKey().equals(b) && entry.getValue() < 2);
out.println(res ? "YES" : "NO");
// for (Entry<Integer, Long> entry : tmp.entrySet()) {
// if (entry.getKey().equals(a) || entry.getKey().equals(b) || entry.getValue() > 1) {
// out.println("NO");
// return;
// }
// }
// out.println("YES");
}
I can't afford to use Stream, so all For statements ...
reference: Summary of solutions to the shortest path problem DP story For you who didn't understand Dijkstra's algorithm Programming Contest Challenge Book P.87 ~ Directed Acyclic Graph (DAG) Opinion and Topological Sort
--Implemented by the Floyd-Warshall method (I couldn't implement it well by the Dijkstra method or Bellman Ford ...) --Topological sort
The transition is also written in the code comment, but it is extracted
--Use the Warshall Floyd method --The movement cost between each town is 1 and temporarily placed (there is no movement cost in the problem statement, and the movement cost between each town is read as equivalent from the input example) --If the cost of moving between towns is uncertain, ... ** Think when solving the problem **
** 1: Calculation of minimum cost **
| start point\end point | Town 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Town 1 | 0 | 1 | 1 | 2 | 3 | 3 | 4 | |
| 2 | 1 | 0 | 2 | 1 | 2 | 2 | 3 | |
| 3 | 1 | 2 | 0 | 1 | 2 | 2 | 3 | |
| 4 | 2 | 1 | 1 | 0 | 1 | 1 | 2 | |
| 5 | 3 | 2 | 2 | 1 | 0 | 2 | 1 | |
| 6 | 3 | 2 | 2 | 1 | 2 | 0 | 1 | |
| 7 | 4 | 3 | 3 | 2 | 1 | 1 | 0 |
** 2: Minimum cost & Topological sort for moving from start point to end point from the entered edge **
--Map the next town based on the results of the Floyd-Warshall Floyd method
--The judgment of next town is that the movement cost is $ \ pm 1
| start point\end point | Town 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Town 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
** 3: Summarize how many waypoints there are for each cost (and in order of cost. TreeMap is used for ordering) from the start point to the end point based on the result of topological sort **
| cost | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| Town to go through | 1 | 2,3 | 4 | 5,6 | 7 |
** 4: Calculated by DP (in order of cost) **
private void solveC() {
int n = nextInt();
int a = nextInt() - 1;
int b = nextInt() - 1;
int m = nextInt();
final int CONST_INF = 999999999;
int[][] graph = new int[n][n];
for (int i = 0; i < graph.length; i++) {
Arrays.fill(graph[i], CONST_INF);
graph[i][i] = 0;
}
Edge[] edge = new Edge[m];
for (int j = 0; j < m; j++) {
int from = nextInt() - 1;
int to = nextInt() - 1;
graph[from][to] = 1;
graph[to][from] = 1;
Edge wkEdge = new Edge();
if (from > to) {
wkEdge.from = to;
wkEdge.to = from;
wkEdge.cost = 1;
} else {
wkEdge.from = from;
wkEdge.to = to;
wkEdge.cost = 1;
}
edge[j] = wkEdge;
}
/*
*Calculation result of Floyd-Warshall Floyd method
* [0, 1, 1, 2, 3, 3, 4]
* [1, 0, 2, 1, 2, 2, 3]
* [1, 2, 0, 1, 2, 2, 3]
* [2, 1, 1, 0, 1, 1, 2]
* [3, 2, 2, 1, 0, 2, 1]
* [3, 2, 2, 1, 2, 0, 1]
* [4, 3, 3, 2, 1, 1, 0]
*/
getMinByWarshall(graph, n);
/*
*Shortest path DAG
*After performing topological sort
* [0, 1, 1, 0, 0, 0, 0]
* [0, 0, 0, 1, 0, 0, 0]
* [0, 0, 0, 1, 0, 0, 0]
* [0, 0, 0, 0, 1, 1, 0]
* [0, 0, 0, 0, 0, 0, 1]
* [0, 0, 0, 0, 0, 0, 1]
* [0, 0, 0, 0, 0, 0, 0]
*/
int[][] dag = new int[n][n];
for (int i = 0; i < m; i++) {
int x = edge[i].from;
int y = edge[i].to;
if (graph[a][x] == graph[a][y] + 1) {
dag[y][x] = 1;
}
if (graph[a][x] == graph[a][y] - 1) {
dag[x][y] = 1;
}
}
/*
*Shortest distance map
*Point a(a=0)Map by distance from
* {0=[0], 1=[1, 2], 2=[3], 3=[4, 5], 4=[6]}
*/
Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < n; i++) {
int d = graph[a][i];
if (map.containsKey(d)) {
List<Integer> list = map.get(d);
list.add(i);
map.put(d, list);
} else {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(d, list);
}
}
long CONST_MOD = (long) Math.pow(10, 9) + 7;
long[] minStep = new long[n];
minStep[a] = 1;
/*
*Rotate the movement cost from point a to point b
*/
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*If it is possible to go from point: town to point: k (1 on dag)=）
* minStep[k]To minStep[town]Plus the number of moves from(Can move to point k)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
System.out.println(minStep[b]);
}
private static class Edge {
private int from;
private int to;
private int cost;
}
private void getMinByWarshall(int[][] edge, int vertex) {
for (int k = 0; k < vertex; k++) {
for (int i = 0; i < vertex; i++) {
for (int j = 0; j < vertex; j++) {
edge[i][j] = Integer.min(edge[i][j], edge[i][k] + edge[k][j]);
}
}
}
}
After making the ** shortest distance map **, the last DP uses the map.
--Corresponding code
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*If it is possible to go from point: town to point: k (1 on dag)=）
* minStep[k]To minStep[town]Plus the number of moves from(Can move to point k)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
However, if you look inside the Map based on Input Example 1 and Input Example 2, you will feel that you can repair it as shown below (repair? Code). After all, if you're spinning in all towns, you don't need a map, right? Then, why not turn everything from the beginning? ?? ?? When. In conclusion, accurate values will not come out unless DP is done based on Map.
--Input value: Originally, output = 1, but with the code after failure repair, output = 0
7
4 7
7
1 5
1 6
6 7
1 2
2 3
3 4
1 7
for (int town = 0; town < n; town++) {
for (int k = 0; k < n; k++) {
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
Recommended Posts