AtCoder NoviStepsを埋めてみる(27) 幅優先探索 1Q 後編の続きです。今回も幅優先探索（BFS）です。やや難しめの問題に挑戦します。
054 – Takahashi Number（★6）
問題の概要
現在、この世界には高橋氏を含めて N 人の研究者と M 個の共著論文がある。
i 番目の共著論文は K[i] 人の研究者 R[i, 1] ,…,R[i, K] による共著である。
高橋氏は研究者 1 であるとする。このとき N 人の研究者それぞれについて高橋数は定義されているだろうか？ もし定義されているならばその値は？
高橋数の定義は以下のとおり。
高橋氏の高橋数は 0 である。
高橋数が n の研究者との共著経験があり、高橋数が n 未満の研究者との共著経験がない研究者の高橋数は n + 1 とする。
上記の事項によって高橋数が決まらなかった研究者については、高橋数は定義されない。
R[i, 1], R[i, 2], …, R[i, k] をひとつのグループとみなしてそれぞれを辺で結び、頂点 1 からの最短経路長を考えればよいのですが、これだと k の値が大きくなると辺の本数も増えてしまい、TLE する可能性があります。
なので打開策として超頂点を導入します。高橋数が大きい頂点に遷移するときは必ず超頂点を通ることになるので必ず最短経路長は 2 の倍数となります。これを半分にしたものが求める解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Program { static void Bfs(List<int>[] G, int start, int[] dists) { Queue<int> q = new Queue<int>(); dists[start] = 0; q.Enqueue(start); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; q.Enqueue(next); } } } } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N + M]; for (int i = 0; i < N + M; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int k = int.Parse(Console.ReadLine()); int[] R = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); foreach (int r in R) { G[i + N].Add(r - 1); G[r - 1].Add(i + N); } } int[] dists = new int[N + M]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); for (int i = 0; i < N; i++) { if (dists[i] < int.MaxValue) Console.WriteLine(dists[i] / 2); else Console.WriteLine(-1); } } } |
E – Hit and Away
問題の概要
N 頂点 M 辺の単純連結無向グラフが与えられる。
各頂点は「安全な頂点」か「危険な頂点」のどちらかである。
すべての危険な頂点 v について、「ある安全な頂点から出発し、v を経由し、 出発した頂点と異なる 安全な頂点へ移動するのにかかる時間としてあり得る最小値」を求めよ。
それぞれの危険な頂点から一番近い安全な頂点と二番目に近い安全な頂点がわかればよいです。
安全な頂点を始点に多始点幅優先探索をおこないます。このとき求めたい頂点 i に一番近い頂点と二番目に近い頂点は異なる頂点でなければならないので始点がどこなのかという情報も持たせる必要があります。各頂点への最短経路長が確定しているときは二番目に近い長さとして経路長を格納します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
class Program { // starts から一番近い頂点と二番目に近い頂点とその経路長を求める static void Bfs(List<int>[] G, List<int> starts, int[,] dists, int[,] froms) { Queue<(int, int, int)> q = new Queue<(int, int, int)>(); foreach (int start in starts) { q.Enqueue((start, start, 0)); dists[start, 0] = 0; froms[start, 0] = start; // 始点となる頂点であれば自分自身が一番近い。これを忘れるとバグる。 } while (q.Count > 0) { var cur = q.Dequeue(); foreach (var next in G[cur.Item1]) { if (dists[next, 0] > cur.Item3 + 1) { dists[next, 0] = cur.Item3 + 1; froms[next, 0] = cur.Item2; q.Enqueue((next, cur.Item2, cur.Item3 + 1)); } else { if (dists[next, 1] > cur.Item3 + 1 && froms[next, 0] != cur.Item2) { dists[next, 1] = cur.Item3 + 1; froms[next, 1] = cur.Item2; q.Enqueue((next, cur.Item2, cur.Item3 + 1)); } } } } } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int u = vs[0] - 1; int v = vs[1] - 1; G[u].Add(v); G[v].Add(u); } string S = Console.ReadLine(); List<int> starts = new List<int>(); for (int i = 0; i < S.Length; i++) { if (S[i] == 'S') starts.Add(i); } int[,] dists = new int[N, 2]; int[,] froms = new int[N, 2]; for (int i = 0; i < N; i++) { dists[i, 0] = int.MaxValue; dists[i, 1] = int.MaxValue; froms[i, 0] = -1; froms[i, 1] = -1; } Bfs(G, starts, dists, froms); for (int i = 0; i < N; i++) { if (S[i] == 'D') Console.WriteLine(dists[i, 0] + dists[i, 1]); } } } |
F – Merge Set
問題の概要
1 以上 M 以下の整数からなる集合が N 個 ある。
以下の操作を繰り返すことで 1 と M が両方含まれる集合を作ることができるか判定せよ。できるのであれば必要な操作回数の最小値も求めよ。
（操作）
1 個以上の共通した要素を持つ 2 個の集合 X, Y を選ぶ。
X, Y を取り除き、新たに X ∪ Y を追加する。
これは以下と同じ問題です。
はじめ、1 を含むある集合 S[x] にいる。ここから、今いる集合と同じ要素を 1 個以上含む集合に移動することを繰り返して、M を含む集合へ移動する。最低で何回の移動が必要か？
集合を頂点で表せば幅優先探索の問題として解くことができますが、移動できる頂点に辺を張ろうとすると辺の本数が多くなりすぎて TLE してしまいます。そこで超頂点を導入します。
集合 i が値 v を持つのであれば、頂点 i と超頂点 v のあいだに無向辺を張ります。あとは超頂点 1 から超頂点 M への最短経路長を考えればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Program { static void Bfs(List<int>[] G, int start, int[] dists) { Queue<int> q = new Queue<int>(); dists[start] = 0; q.Enqueue(start); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; q.Enqueue(next); } } } } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N + M]; for (int i = 0; i < N + M; i++) G[i] = new List<int>(); for (int i = 0; i < N; i++) { _ = Console.ReadLine(); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 0; j < vs.Length; j++) { int v = vs[j] - 1 + N; // 超頂点の番号 G[i].Add(v); G[v].Add(i); } } int[] dists = new int[N + M]; Array.Fill(dists, int.MaxValue); Bfs(G, N + (1 - 1), dists); // 超頂点を経由しているので得られた最短経路長を半分にする // また始点と終点も超頂点なのでそのぶんも差し引いた値が解 int ans = -1; if (dists[N + (M - 1)] < int.MaxValue) ans = (dists[N + (M - 1)] - 2) / 2; Console.WriteLine(ans); } } |
E – Min of Restricted Sum
問題の概要
整数 N, M と長さ M の整数列 X, Y, Z が与えられる。
X, Y の要素はすべて 1 以上 N 以下である。
以下の条件を満たす長さ N の非負整数列のなかで要素の総和が最小になる非負整数列 A を求めよ。
（条件）1 ≦ i ≦ M を満たすすべての整数 i に対し、A[X[i]] と A[Y[i]] の XOR が Z[i] と一致する。
N 個の頂点を用意し、頂点 X[i] と 頂点 Y[i] のあいだに重み Z[i] の辺を張ります。そして幅優先探索で各頂点に対して、頂点 X[i] の値と頂点 Y[i] の値の XOR が Z[i] になるように値を設定していきます（探索開始頂点の値はとりあえず 0 でよい）。
矛盾することなくすべての頂点に値を設定することができれば、これが求める非負数列 A となればよいのですが、「総和が最小」という条件があるのでこのままではダメです。
連結成分の各頂点の値が定まったら総和が最小になるように調整を加えます。まずそれぞれの値の各ビットに着目します。k 番目のビットが立っているかどうかを調べて過半数が立っていたらk 番目のビットをすべて反転させます。すべてのビットでこの処理をおこなうことで、連結成分の各頂点に設定された値の総和は最小になっています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
class Program { // 頂点に辺の重みと矛盾しないように値を設定できるか調べる static List<int> CheckByBfs(List<(int, int)>[] G, int start, int[] values, bool[] seen) { List<int> res = new List<int>(); Queue<int> q = new Queue<int>(); q.Enqueue(start); values[start] = 0; seen[start] = true; res.Add(start); while (q.Count > 0) { int cur = q.Dequeue(); int v = values[cur]; foreach (var next in G[cur]) { int nv = v ^ next.Item2; if (!seen[next.Item1]) { seen[next.Item1] = true; values[next.Item1] = nv; q.Enqueue(next.Item1); res.Add(next.Item1); } else { if (values[next.Item1] != nv) return new List<int>(); } } } return res; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<(int, int)>[] G = new List<(int, int)>[N]; for (int i = 0; i < N; i++) G[i] = new List<(int, int)>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = vs[0] - 1; int y = vs[1] - 1; int z = vs[2]; G[x].Add((y, z)); G[y].Add((x, z)); } int[] values = new int[N]; bool[] seen = new bool[N]; bool ok = true; for (int i = 0; i < N; i++) { if (!seen[i]) { List<int> res = CheckByBfs(G, i, values, seen); if (res.Count == 0) { ok = false; break; } for (int k = 0; k <= 30; k++) { // values が仮確定した頂点で k 番目のビットが立っている値の個数を調べる // 過半数が立っている場合、k 番目のビットを反転する（総和を最小にしたいので） int cnt = 0; foreach (int idx in res) { if (((values[idx] >> k) & 1) == 1) cnt++; } if (cnt * 2 > res.Count) { foreach (int idx in res) values[idx] ^= 1 << k; } } } } if (ok) Console.WriteLine(string.Join(" ", values)); else Console.WriteLine(-1); } } |
F – Two Spanning Trees
問題の概要
N 頂点 M 辺の無向グラフ G が与えられる。
下記の 2 つの条件をともに満たすような G の 2 つの全域木 T1, T2 を 1 組構成せよ。
（T1 の条件）
頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T1 に含まれないすべての辺 {u, v} について、u と v は T1 において祖先と子孫の関係にある。
（T2 の条件）
頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T2 に含まれない辺 {u, v} のなかに、u と v は T2 において祖先と子孫の関係にあるものは存在しない。
求めるべき T1 は DFS木 であり、T2 は BFS木 です。DFS木には「木に含まれないすべての G の辺 {u, v} について u と v が祖先と子孫の関係にある」という性質があり、BFS木には「木に含まれない G の辺 {u, v} について u と v が祖先と子孫の関係にあるものは存在しない」という性質があります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
class Program { // DFS木を得る（汎用的なものを作りたかったので解を得るために不要な処理もしている） static List<int>[] GetDfsTree(List<int>[] G, int start) { int v_cnt = G.Length; List<int>[] res = new List<int>[v_cnt]; for (int i = 0; i < v_cnt; i++) res[i] = new List<int>(); bool[] seen = new bool[v_cnt]; Dfs(start); return res; void Dfs(int cur) { seen[cur] = true; foreach (int next in G[cur]) { if (seen[next]) continue; res[cur].Add(next); res[next].Add(cur); Dfs(next); } } } // BFS木を得る（汎用的なものを作りたかったので解を得るために不要な処理もしている） static List<int>[] GetBfsTree(List<int>[] G, int start) { int v_cnt = G.Length; List<int>[] res = new List<int>[v_cnt]; for (int i = 0; i < v_cnt; i++) res[i] = new List<int>(); Queue<int> q = new Queue<int>(); bool[] seen = new bool[v_cnt]; q.Enqueue(start); seen[start] = true; while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in G[cur]) { if (seen[next]) continue; res[cur].Add(next); res[next].Add(cur); seen[next] = true; q.Enqueue(next); } } return res; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int u = uv[0] - 1; int v = uv[1] - 1; G[u].Add(v); G[v].Add(u); } List<int>[] G1 = GetDfsTree(G, 0); List<int>[] G2 = GetBfsTree(G, 0); for (int i = 0; i < N; i++) { foreach (int next in G1[i]) { if(i < next) Console.WriteLine($"{i + 1} {next + 1}"); } } for (int i = 0; i < N; i++) { foreach (int next in G2[i]) { if (i < next) Console.WriteLine($"{i + 1} {next + 1}"); } } } } |
F – Skate
問題の概要
H 行 W 列のグリッド型のスケート場がある。
スケート場には N 個の障害物があり、i 個目の障害物は (X[i] ,Y[i]) に置かれている。
1 回の移動において、上下左右いずれかの方向を選んで、障害物に当たるまで進み続ける。障害物に当たったときはその 1 つ手前のマスで停止する。
はじめ (sx, sy) にいて、何回か移動することで (gx, gy) で停止したい。
(gx, gy) へ辿り着くために必要な移動回数の最小値を求めよ。
幅優先探索で (sx, sy) から移動できる座標に移動することを繰り返して (gx, gy) へたどり着くための最短経路長を求めればよいです。最短移動回数を求めようとしているので、一度停止した座標に複数回停止することは考えなくてよいです。
現在位置から移動することができる座標はどのようにして求めればよいでしょうか？ 障害物の座標を Dictionary と SortedSet に格納しておくと高速で取得することができます（AtCoder NoviStepsを埋めてみる(21) SortedSet 1D の冒頭部分を参照）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
class Program { static void Main() { int[] hwn = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hwn[0]; int W = hwn[1]; int N = hwn[2]; int[] sxy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int sx = sxy[0]; int sy = sxy[1]; int[] gxy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int gx = gxy[0]; int gy = gxy[1]; Dictionary<int, SortedSet<int>> xToY = new Dictionary<int, SortedSet<int>>(); Dictionary<int, SortedSet<int>> yToX = new Dictionary<int, SortedSet<int>>(); for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0]; int y = xy[1]; if (!xToY.ContainsKey(x)) xToY.Add(x, new SortedSet<int>()); xToY[x].Add(y); if (!yToX.ContainsKey(y)) yToX.Add(y, new SortedSet<int>()); yToX[y].Add(x); } Queue<(int, int)> q = new Queue<(int, int)> (); q.Enqueue((sx, sy)); Dictionary<string, int> dic = new Dictionary<string, int> (); dic.Add($"{sx},{sy}", 0); while (q.Count > 0) { var cur = q.Dequeue(); int x = cur.Item1; int y = cur.Item2; int v = dic[$"{x},{y}"]; // y 座標を変えずに横移動 if (yToX.ContainsKey(y)) { // 右方向に移動できるか？ int[] x_rights = yToX[y].GetViewBetween(x, int.MaxValue).Take(1).ToArray(); if (x_rights.Length == 1) { int nx = x_rights[0] - 1; // 障害物の手前で停止するので -1 int ny = y; if (!dic.ContainsKey($"{nx},{ny}")) { dic.Add($"{nx},{ny}", v + 1); q.Enqueue((nx, ny)); // ゴールに着いたら即終了してよいがあまり実行時間は短縮されない if (nx == gx && ny == gy) break; } } // 左方向に移動できるか？ int[] x_lefts = yToX[y].GetViewBetween(-1, x).Reverse().Take(1).ToArray(); if (x_lefts.Length == 1) { int nx = x_lefts[0] + 1; int ny = y; if (!dic.ContainsKey($"{nx},{ny}")) { dic.Add($"{nx},{ny}", v + 1); q.Enqueue((nx, ny)); if (nx == gx && ny == gy) break; } } } // x 座標を変えずに縦移動 if (xToY.ContainsKey(x)) { // 上方向に移動できるか？ int[] y_uppers = xToY[x].GetViewBetween(y, int.MaxValue).Take(1).ToArray(); if (y_uppers.Length == 1) { int nx = x; int ny = y_uppers[0] - 1; if (!dic.ContainsKey($"{nx},{ny}")) { dic.Add($"{nx},{ny}", v + 1); q.Enqueue((nx, ny)); if (nx == gx && ny == gy) break; } } // 下方向に移動できるか？ int[] y_lowers = xToY[x].GetViewBetween(-1, y).Reverse().Take(1).ToArray(); if (y_lowers.Length == 1) { int nx = x; int ny = y_lowers[0] + 1; if (!dic.ContainsKey($"{nx},{ny}")) { dic.Add($"{nx},{ny}", v + 1); q.Enqueue((nx, ny)); if (nx == gx && ny == gy) break; } } } } Console.WriteLine(dic.ContainsKey($"{gx},{gy}") ? dic[$"{gx},{gy}"] : -1); } } |
F – Blocked Roads
問題の概要
N 頂点 M 辺の有向グラフが与えられる。
各 i(1 ≦ i ≦ M) について、辺 i のみ通れないときの頂点 1 から頂点 N までの最短距離を求めよ。
まず頂点 1 から頂点 N までの最短経路と最短経路長を求めます。辺 i が最短経路上にないのであればそのときの距離は最初に求めた最短経路長と同じです。そうでない場合はそのつど辺を取り除いて最短経路長を求めればよいです。最初に求めた最短経路上に辺が存在するケースは最大で N – 1 回です。N – 1 回の最短経路長の計算であれば TLE することはありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
class Program { static List<int> GetPathByBfs(HashSet<int>[] G, int s, int t) { Queue<int> q = new Queue<int>(); q.Enqueue(s); int[] dists = new int[G.Length]; Array.Fill(dists, int.MaxValue); int[] froms = new int[G.Length]; dists[s] = 0; froms[s] = -1; while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; froms[next] = cur; q.Enqueue(next); } } } if(dists[t] == int.MaxValue) // 解なし return new List<int>(); int last = t; List<int> path = new List<int>(); while (true) { path.Add(last); last = froms[last]; if (last == -1) break; } path.Reverse(); return path; } static int[] Bfs(HashSet<int>[] G, int start) { Queue<int> q = new Queue<int>(); q.Enqueue(start); int[] dists = new int[G.Length]; Array.Fill(dists, int.MaxValue); dists[start] = 0; while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; q.Enqueue(next); } } } return dists; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; HashSet<int>[] G = new HashSet<int>[N]; for (int i = 0; i < N; i++) G[i] = new HashSet<int>(); int[] S = new int[M]; int[] T = new int[M]; for (int i = 0; i < M; i++) { int[] st = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); S[i] = st[0] - 1; T[i] = st[1] - 1; } Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < M; i++) { G[S[i]].Add(T[i]); dic.Add($"{S[i]},{T[i]}", i); } List<int> path = GetPathByBfs(G, 0, N - 1); HashSet<int> used_edges = new HashSet<int>(); for (int i = 0; i < path.Count - 1; i++) used_edges.Add(dic[$"{path[i]},{path[i + 1]}"]); for (int i = 0; i < M; i++) { if (used_edges.Contains(i)) { G[S[i]].Remove(T[i]); int[] dists = Bfs(G, 0); Console.WriteLine(dists[N - 1] < int.MaxValue ? dists[N - 1] : -1); G[S[i]].Add(T[i]); } else Console.WriteLine(path.Count - 1); } } } |
F – Pure
問題の概要
N 頂点 M 辺の有向グラフ G が与えられる。
すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフが存在するか判定し、存在するならその一例を示せ。
題意を満たす誘導部分グラフとはどのようなグラフになるでしょうか？ 「閉路を探せばよい」では不十分です。閉路を構成する頂点同士であり、しかも隣り合っていない頂点への辺が存在する場合は題意を満たしていません。
「閉路を構成する頂点同士であり、しかも隣り合っていない頂点への辺が存在する場合」とは閉路のなかにもっと閉路長が短い別の閉路が存在する場合です。なので閉路長が最小の閉路に含まれる頂点集合が求めるべき解となります。
では閉路長が最小になる閉路はどうやって求めればよいでしょうか？
頂点 A[i] から頂点 B[i] に向けて辺 i が張られていて、これが閉路の一部であるなら頂点 B[i] から頂点 A[i] に戻ってくることができるはずです。これを幅優先探索で探します。見つかった最短経路に頂点 A[i] から頂点 B[i] への辺を加えたものが 辺 i を含む閉路長最小の閉路です。このなかから閉路長が最小のものを探します。これが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); int[] U = new int[M]; int[] V = new int[M]; for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); U[i] = uv[0] - 1; V[i] = uv[1] - 1; } for (int i = 0; i < M; i++) G[U[i]].Add(V[i]); int min_len = int.MaxValue; List<int> ans = new List<int>(); for (int i = 0; i < M; i++) { Queue<int> q = new Queue<int>(); q.Enqueue(V[i]); int[] dists = new int[N]; int[] froms = new int[N]; Array.Fill(dists, int.MaxValue); dists[V[i]] = 0; froms[V[i]] = -1; while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; froms[next] = cur; q.Enqueue(next); } } } if (dists[U[i]] < int.MaxValue) { List<int> res = new List<int>(); int last = U[i]; res.Add(last + 1); while (true) { last = froms[last]; res.Add(last + 1); if (last == V[i]) break; } if(min_len > res.Count) { min_len = res.Count; res.Reverse(); ans = res; } } } if (min_len < int.MaxValue) { Console.WriteLine(ans.Count); Console.WriteLine(string.Join(" ", ans)); } else Console.WriteLine(-1); } } |
E – League
テニスの大会に参加している N 人の選手がいる。
大会は総当たり戦で、合計 N * (N – 1) / 2 試合が行われる。
以下の条件ですべての試合を消化することができるか判定し、できる場合は必要な最小の日数も求めよ。
（条件）
各選手は一日に最大で一試合をおこなう。
各選手 i は、選手 A[i, 1], A[i, 2], …, A[i, N – 1] とこの順に一度ずつ試合をおこなう。
各選手の対戦相手を Queue に格納して対戦可能なペアを探して Dequeue していけばよいのですが、対戦可能なペアを探す処理を工夫しないと TLE してしまいます。
対戦した選手のみ次の日に対戦する相手が変わります。なので相手を探す処理は前日試合をした選手からだけでよいです。選手 A と選手 B の対戦と選手 B と選手 A の対戦を別対戦として二重に処理をするなどのバグには注意が必要です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Queue<int>[] Q = new Queue<int>[N]; for (int i = 0; i < N; i++) { Q[i] = new Queue<int>(); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); foreach (int v in vs) Q[i].Enqueue(v - 1); Q[i].Enqueue(N); } // 初日 HashSet<string> pairs = new HashSet<string>(); for (int i = 0; i < N; i++) { int p = Q[i].Peek(); if (i < p && Q[p].Peek() == i) pairs.Add($"{Math.Min(i, p)} {Math.Max(i, p)}"); } int ans = 0; while (true) { ans++; // 次の対戦相手が変化したプレイヤー HashSet<int> changes = new HashSet<int>(); foreach (string pair in pairs) { string[] vs = pair.Split(); int a = int.Parse(vs[0]); int b = int.Parse(vs[1]); Q[a].Dequeue(); Q[b].Dequeue(); changes.Add(a); changes.Add(b); } pairs.Clear(); // 次の対戦相手が変化したプレイヤーだけ調べる int[] arr = changes.ToArray(); foreach (int v in arr) { int p = Q[v].Peek(); if (p < N && Q[p].Peek() == v) pairs.Add($"{Math.Min(v, p)} {Math.Max(v, p)}"); } // 次の対戦相手が番兵のみならすべての対戦相手と対戦したことになる // すべてのプレイヤーの対戦相手が番兵のみなら終了 if (Q.All(_ => _.Count == 1)) break; // 終了していないのに対戦の組み合わせが見つからない場合は「解なし」 if (pairs.Count == 0) { ans = -1; break; } } Console.WriteLine(ans); } } |
