AtCoder ABC 021 A&B&C
AtCoder - 021
201905/15追記 A問題の解法がコメント欄に有
A問題
- 同じの何度も利用してよいなら全部1でもよいとおもって。。。一応AC
private void solveA() {
int n = nextInt();
out.println(n);
IntStream.range(0, n).forEach(i -> out.println(1));
}
A問題：ベタにループ
201905/15追記
コメント欄にきれいなループでのコード有
- 簡略化しないとこんな感じになるのか？
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;
}
}
}
}
}
}
B問題
- 経路が以下の条件を満たせば、少なくとも余計な回り道はしていない
- 始点と終点を含んでいない
- 同じ町が二回出てこない
コメントアウトは最初に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");
}
C問題：最短経路問題
Stream使ってとか余裕ないので全部For文・・・
参考：
最短経路問題の解法まとめ
DPの話
ダイクストラ法が分からなかった君のために
プログラミングコンテストチャレンジブック P.87~
有向非巡回グラフ（DAG）の意味とトポロジカルソート
- ワーシャルフロイド法で実装(Dijkstra法やBellmanFordだと上手く実装できなかったんや。。。)
- トポロジカルソート
- DP
遷移についてコードのコメントにも書いてあるけど抜き出し
最初に、隣接行列から各拠点間の移動にかかる最小コストを算出している
- ワーシャルフロイド法を利用
- 各町間の移動コストは1と仮置き（問題遺文中には移動コストがないかつ、入力例より各町間の移動コストは等価と読んだ）
- 各町間での移動コストが不定の場合は、、、その問題を解く時に考えよう
1:最小コストの計算
| 始点\終点 | 町1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 町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:最小コスト&入力された辺より始点→終点の移動についてトポロジカルソート
- ワーシャルフロイド法の結果をもとに、
次の町をマップ -
次の町の判定は、移動コストが $\pm 1$ であること- $+1$なら次の町、$-1$なら前の町
| 始点\終点 | 町1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 町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:トポロジカルソートの結果をもとに始点から終点まで、各コストごと（かつ、コスト順。順序性を持つためTreeMap利用している）に経由地が何個ずつあるのかをまとめ
| コスト | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| 経由する町 | 1 | 2,3 | 4 | 5,6 | 7 |
4:DPで（コスト順に）計算
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;
}
/*
* ワーシャルフロイド法の計算結果
* [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);
/*
* 最短路DAG
* トポロジカルソート実施後
* [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;
}
}
/*
* 最短距離マップ
* a地点(a=0)からの距離ごとのマップ
* {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;
/*
* 地点aから地点bへの移動コスト分回す
*/
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
* 地点：townから地点：kへ行くことが可能なら（dag上で1=）
* minStep[k]にminStep[town]からの移動回数をプラス(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]);
}
}
}
}
C問題注記
最短距離マップ を作ったのち、最後のDPはマップを利用している。
- 該当のコード
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
* 地点：townから地点：kへ行くことが可能なら（dag上で1=）
* minStep[k]にminStep[town]からの移動回数をプラス(k地点への移動が可能)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
ただ、入力例1や入力例2をもとにMapの中を見てみると以下（改修？コード）の様に改修できる気がしてくる。
結局全部のtownで回しているならMap要らないじゃん？
じゃぁ、最初から全て回せばよいのでは？？？と。
結論としては、MapをもとにDPをしないと正確な値は出てこない。
- 入力値：本来は出力=1となるはずだが、失敗改修後のコードだと出力=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;
}
}
}