AtCoder NoviStepsを埋めてみる(12) 整数系探索問題 1Q以上の続きです。今回は Union-Find です。
素集合データ構造（disjoint-set data structure）とは、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造のことです。
このデータ構造に対して
① Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
② Union: 2つの集合を1つに統合する。
これらの操作を Union-Find アルゴリズムと呼び、グラフの連結判定、サイクル検出などに使うことができます。
また ac-library-csharp というライブラリの Dsu クラスを使えば、自分でこのようなデータ構造を実装しなくても簡単に使用することができます。
C – Count Connected Components
C – Count Connected Components
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。グラフに含まれる連結成分の個数を求めよ。
基本問題です。Union-Find を使えば簡単に解けます。辺でつながっている頂点を Merge して最後に Groups メソッドを呼び出せば連結成分と各連結成分に属する頂点の配列が返されるので、dsu.Groups().Length を出力すればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } int ans = dsu.Groups().Length; Console.WriteLine(ans); } } |
C – Connect Cities
問題の概要
N 個の都市と都市 A[i] と都市 B[i] を結ぶM 個の双方向道路がある。
どの都市からどの都市へもひとつまたは複数の道路をたどることで到達できるようにするためには、最低何個の道路を作ればよいだろうか？
連結成分が何個あるか求めれば、それらを連結させるために必要な道路の数がわかります。連結成分の個数 – 1 が解です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); } int ans = dsu.Groups().Length; Console.WriteLine(ans - 1); } } |
C – Make it Forest
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
グラフを森にするためには辺を最低何本削除する必要があるだろうか？
閉路を持たない（連結であるとは限らない）グラフを森（英: forest）といいます。森は各連結成分をみたとき、木になっています。木も閉路を持たず辺の数が頂点数よりも 1 少ないという性質があります。
なので（各連結成分に属する頂点 – 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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } foreach (var group in dsu.Groups()) M -= group.Length - 1; Console.WriteLine(M); } } |
C – Virus
問題の概要
N 人の人が二次元平面上におり、人 i は座標 (X[i] ,Y[i]) にいる。
人 1 がウイルスに感染した。ウイルスに感染した人から距離が D 以内にいる人にウイルスは感染する。
十分に時間が経過したあと、各 i についてウイルスに感染しているか判定せよ。
Union-Find で距離が D 以内にある頂点を Merge していきます。頂点 i が 頂点 1 と同じ連結成分に属するのであれば “Yes”、そうでないなら “No” を出力します。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int D) = ReadInt2(); int[] X = new int[N]; int[] Y = new int[N]; for (int i = 0; i < N; i++) { (int x, int y) = ReadInt2(); X[i] = x; Y[i] = y; } Dsu dsu = new Dsu(N); for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { if(Math.Pow(X[a] - X[b], 2) + Math.Pow(Y[a] - Y[b], 2) <= Math.Pow(D, 2)) dsu.Merge(a, b); } } for (int i = 0; i < N; i++) Console.WriteLine(dsu.Same(i, 0) ? "Yes" : "No"); } } |
C – Don’t be cycle
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めよ。
閉路を持たない ⇔ 連結成分が木 です。
また 木 ⇒ 辺の数は 頂点数 – 1 です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } foreach (var group in dsu.Groups()) M -= group.Length - 1; Console.WriteLine(M); } } |
D – Friends
問題の概要
N 人の人がいる。
「人 A[i] と人 B[i] は友達である」という情報が M 個与えられる。
X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達である。
この N 人をいくつかのグループに分け、すべての人について「同じグループの中に友達がいない」という状況を作りたい。
最小でいくつのグループに分ければ良いだろうか？
まず Union-Find で友達なら同じ連結成分に属するようにわけます。
「同じグループの中に友達がいない」という状況を作るのであれば同じ連結成分に属する人をバラバラにしなければなりませんが、そうでないなら同じグループにしても問題ありません。
なので、各連結成分の大きさの最大値が解となります。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; dsu.Merge(u, v); } long ans = 0; foreach (var group in dsu.Groups()) ans = Math.Max(ans, group.Length); Console.WriteLine(ans); } } |
D – Do use hexagon grid
問題の概要
無限に広い六角形のグリッドがある。最初、すべてのマスは白である。
ある六角形のマスは 2 つの整数 i, j を用いて (i, j) と表され、マス (i, j) は以下の 6 つのマスと隣接する。
(i – 1, j – 1)
(i – 1, j)
(i, j – 1)
(i, j + 1)
(i + 1, j)
(i + 1, j + 1)
N 個のマスを黒く塗ったが、黒いマスがいくつの連結成分をなすか求めよ。
六角形のマスは 2 つの整数 i, j を用いて表されるが、これを 1 つの整数で表すことができるようにすると Union-Find が使えます。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } int N = int.Parse(Console.ReadLine()); int[] X = new int[N]; int[] Y = new int[N]; Dictionary<string, int> dic = new Dictionary<string, int>(); for (int i = 0; i < N; i++) { (int x, int y) = ReadInt2(); X[i] = x; Y[i] = y; dic.Add($"{x},{y}", i); } Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) { int x = X[i]; int y = Y[i]; if (dic.ContainsKey($"{x - 1},{y - 1}")) dsu.Merge(i, dic[$"{x - 1},{y - 1}"]); if (dic.ContainsKey($"{x - 1},{y}")) dsu.Merge(i, dic[$"{x - 1},{y}"]); if (dic.ContainsKey($"{x},{y - 1}")) dsu.Merge(i, dic[$"{x},{y - 1}"]); if (dic.ContainsKey($"{x},{y + 1}")) dsu.Merge(i, dic[$"{x},{y + 1}"]); if (dic.ContainsKey($"{x + 1},{y}")) dsu.Merge(i, dic[$"{x + 1},{y}"]); if (dic.ContainsKey($"{x + 1},{y + 1}")) dsu.Merge(i, dic[$"{x + 1},{y + 1}"]); } Console.WriteLine(dsu.Groups().Length); } } |
D – New Friends
問題の概要
N 人のユーザーが利用している SNS がある。
この SNS では 2 人のユーザが互いに友達になれる機能があり、友達関係は双方向的である。
現在 SNS 上には M 組の友達関係が存在し、i 組目の友達関係はユーザー A[i] とユーザー B[i] からなる。
「X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなユーザーを選んで X と Z を友達にする」という操作をおこなえる最大の回数を求めよ。
「X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなユーザーを選んで X と Z を友達にする」という操作を繰り返すとその連結成分は任意の 2 頂点間に辺があるグラフになります。この場合、辺の数は連結成分に属する頂点数を n とすると n (n – 1) / 2 になります。
なので各連結成分の頂点数 n から n (n – 1) / 2 の総和を計算し、最初から存在した辺の数である 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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); } long ans = 0; foreach (var group in dsu.Groups()) ans += 1L * group.Length * (group.Length - 1) / 2; ans -= M; Console.WriteLine(ans); } } |
C – Puddles
問題の概要
縦 H 行、横 W 列のグリッドがある。
上から i 行目左から j 列目のマスは S[i, j] が ‘#’ のとき黒く ‘.’ のとき白く塗られている。
白マスの連結成分であって、グリッドの最外周のマスを含まないものの個数を求めよ。
白く塗られているマスの連結成分を考えればいいのですが、四方向が黒マスで囲まれていなければなりません。連結成分のうち端にあるマスを含まないものだけを数えればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int H, int W) = ReadInt2(); char[][] grid = new char[H][]; for (int r = 0; r < H; r++) { grid[r] = Console.ReadLine().ToArray(); } int ToIndex(int r, int c) => r * W + c; (int, int) ToRowCol(int idx) => (idx / W, idx % W); Dsu dsu = new Dsu(H * W + 1); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.') { if (r - 1 >= 0 && grid[r - 1][c] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r - 1, c)); if (r + 1 < H && grid[r + 1][c] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r + 1, c)); if (c - 1 >= 0 && grid[r][c - 1] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r, c - 1)); if (c + 1 < W && grid[r][c + 1] == '.') dsu.Merge(ToIndex(r, c), ToIndex(r, c + 1)); } else dsu.Merge(ToIndex(r, c), H * W); } } long ans = 0; foreach (var group in dsu.Groups()) { // 連結成分のうち端にあるマスが含まれていたり '#' であるものは除外する bool ok = !group.Any(_ => { var rc = ToRowCol(_); return (rc.Item1 == 0 || rc.Item1 == H - 1 || rc.Item2 == 0 || rc.Item2 == W - 1); }); if (ok) ans++; } Console.WriteLine(ans); } } |
C – Cycle Graph?
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
このグラフがサイクルグラフであるか判定せよ。
グラフがサイクルグラフ ⇔ グラフが連結 かつ すべての頂点の次数が 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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); int[] counts = new int[N]; // 頂点から出ている辺の数 for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); counts[a]++; counts[b]++; } Console.WriteLine(dsu.Groups().Length == 1 && counts.All(_ => _ == 2) ? "Yes" : "No"); } } |
D – Tying Rope
問題の概要
一方の端が赤に塗られており、もう一方の端が青に塗られているロープが N 本ある。
ロープの端を結ぶ操作を M 回おこなう。
i 回目の操作ではロープ A[i] の色 B[i] の端とロープ C[i] の色 D[i] の端を結ぶ。
すべての操作を終えた後に、ひとつながりになっているロープの組について環状になっているものとそうでないものの個数を出力せよ。
N 本のロープの両端を頂点 2i, 頂点 2i + 1 とみなしてロープを結んだら頂点を merge します。連結成分の個数がひとつながりになっているロープの組の個数です。環状になっているかどうかは連結成分内の辺の数で判定できます。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N * 2); int[] counts = new int[N * 2]; // 頂点から出ている辺の数 // 同じロープの両端に相当する頂点を merge する for (int i = 0; i < N; i++) { int u = i * 2; int v = i * 2 + 1; dsu.Merge(u, v); counts[u]++; counts[v]++; } for (int i = 0; i < M; i++) { string[] vs = Console.ReadLine().Split(); int a = int.Parse(vs[0]) - 1; string b = vs[1]; int c = int.Parse(vs[2]) - 1; string d = vs[3]; int u = b == "R" ? a * 2 : a * 2 + 1; int v = d == "R" ? c * 2 : c * 2 + 1; dsu.Merge(u, v); counts[u]++; counts[v]++; } int X = 0; int Y = 0; foreach (var group in dsu.Groups()) { int e_cnt = 0; foreach (var v in group) e_cnt += counts[v]; // 同じ辺を 2 回数えているので e_cnt / 2 // これが頂点数と一致するなら環状になっている if (e_cnt / 2 == group.Length) X++; else Y++; } Console.WriteLine($"{X} {Y}"); } } |
D – Unicyclic Components
問題の概要
N 頂点 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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); Dsu dsu = new Dsu(N); int[] counts = new int[N]; for (int i = 0; i < M; i++) { (int v, int u) = ReadInt2(); v--; u--; dsu.Merge(u, v); counts[u]++; counts[v]++; } bool yes = true; foreach (var group in dsu.Groups()) { int e_cnt = 0; foreach (var v in group) e_cnt += counts[v]; // 同じ辺を 2 回数えているので e_cnt / 2 // これが頂点数と一致するか？ if (e_cnt / 2 != group.Length) yes = false; } Console.WriteLine(yes ? "Yes" : "No"); } } |
D – Circumferences
問題の概要
xy 平面上の N 個の円が与えられる。
N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (sx, sy) から点 (tx, ty) に行くことができるかどうかを判定せよ。
円をひとつの頂点とみなして円が他の円と接するか交わっていれば頂点を merge します。点 (sx, sy) がある円と点 (tx, ty) がある円が同一連結成分内にあれば “Yes” です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int, int, int) ReadInt4() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]), int.Parse(vs[3])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } int N = int.Parse(Console.ReadLine()); (int sx, int sy, int tx, int ty) = ReadInt4(); long[] X = new long[N]; long[] Y = new long[N]; long[] R = new long[N]; int s = 0, t = 0; for (int i = 0; i < N; i++) { (int x, int y, int r) = ReadInt3(); X[i] = x; Y[i] = y; R[i] = r; long d2 = (X[i] - sx) * (X[i] - sx) + (Y[i] - sy) * (Y[i] - sy); if (d2 == R[i] * R[i]) s = i; d2 = (X[i] - tx) * (X[i] - tx) + (Y[i] - ty) * (Y[i] - ty); if (d2 == R[i] * R[i]) t = i; } Dsu dsu = new Dsu(N); for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { long d2 = (X[a] - X[b]) * (X[a] - X[b]) + (Y[a] - Y[b]) * (Y[a] - Y[b]); if ((R[a] + R[b]) * (R[a] + R[b]) >= d2 && (R[a] - R[b]) * (R[a] - R[b]) <= d2) dsu.Merge(a, b); } } Console.WriteLine(dsu.Same(s, t) ? "Yes" : "No"); } } |
D – KAIBUNsyo
問題の概要
N 項からなる正整数列が与えられます。
「ある正整数の組 (x, y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える」
この操作を 0 回以上何度でも行える時、操作を最小何回行えば、A を回文にすることができるだろうか？
「A に含まれる x をすべて y に置き換える」という操作を 頂点 x と 頂点 y を merge すると考えます。回文になるように A[i] と A[N – 1 – i] が同じ連結成分にないなら merge していきます。merge した回数が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dsu dsu = new Dsu((int)Math.Pow(10, 5) * 2 + 1); int ans = 0; for (int i = 0; i < N / 2; i++) { if (!dsu.Same(A[i], A[N - 1 - i])) { dsu.Merge(A[i], A[N - 1 - i]); ans++; } } Console.WriteLine(ans); } } |
D – Equals
問題の概要
1 から N までの整数を並び替えた順列 P と整数のペア (x, y) が M 個与えられる。
P[x] と P[y] を入れ替える操作を好きな回数だけおこなうことができる。
P[i] = i となる i の個数の最大値を求めよ。
x, y を merge すると同一連結成分内であれば P を好きなように入れ替えることが可能であることを意味しています。なので入力を 0-based index に変換したあと、i と i = P[j] を満たす j が同一連結成分内に存在するかを調べ、存在するなら入れ替え操作で P[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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); P = P.Select(_ => _ - 1).ToArray(); int[] valueToIndex = new int[N]; for (int i = 0; i < N; i++) { valueToIndex[P[i]] = i; } Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { (int x, int y) = ReadInt2(); x--; y--; dsu.Merge(x, y); } int ans = 0; for (int i = 0; i < N; i++) { if (dsu.Same(i, valueToIndex[i])) ans++; } Console.WriteLine(ans); } } |
D – 道路の老朽化対策について
問題の概要
ある国には N 個の都市があり、そこには都市間を結ぶ M 本の道路がある。
i 本目の道路は都市 a[i] と都市 b[i] を結ぶもので y[i] 年に造られたものである。
この国の国民は、あまりに古い道は使わない。
Q 人の国民の情報が与えられる。
j 人目の国民について、都市 v[j] に住んでおり、造られた年が w[j] 年以前であるような道路を使わないことがわかっている。
それぞれの国民に対し、その人が住んでいる都市から道路のみを使って行き来できるような都市の個数を求めよ。
イベントソートで解きます。
人 j にとってはw[j] 年以前に造られた道路は存在しないのと同じです。なので、道路が造られた順の逆順（現在から過去へ）でグラフを構築していき、w[j] 年段階で都市 v[j] から行き来可能な都市の数を数えればよいです。y[i] 年と w[j] 年が同じ年になる場合は w[j] が先になるようにします。
|
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 |
using AtCoder; class Event { public Event(int a, int b, int y) // 道路をつくる { Year = y; From = a; To = b; } public Event(int v, int w) // 質問クエリ { Year = w; From = v; } public int Year = 0; public int From = 0; public int To = -1; // -1 なら質問クエリ public int Ans = 0; } class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int N, int M) = ReadInt2(); List<Event> E = new List<Event>(); for (int i = 0; i < M; i++) { (int a, int b, int y) = ReadInt3(); a--; b--; E.Add(new Event(a, b, y)); } int Q = int.Parse(Console.ReadLine()); Event[] arr = new Event[Q]; for (int i = 0; i < Q; i++) { (int v, int w) = ReadInt2(); v--; Event e = new Event(v, w); E.Add(e); arr[i] = e; } E = E.OrderByDescending(_ => _.Year).ThenBy(_ => _.To).ToList(); Dsu dsu = new Dsu(N); foreach (Event e in E) { if (e.To != -1) dsu.Merge(e.From, e.To); else e.Ans = dsu.Size(e.From); } foreach (Event e in arr) Console.WriteLine(e.Ans); } } |
D – Friend Suggestions
問題の概要
とある SNS に、N 人 の人が登録している。
この N 人の間には M 組の「友達関係」と K 組の「ブロック関係」が存在する。
友達関係もブロック関係も双方向的である。
a から見て b が友達関係でもブロック関係でもなく友達関係をたどってつながっている場合、b は a の「友達候補」であると定義する。
すべての人 i について、友達候補の数を答えよ。
友達関係をたどってつながっているかどうかは Union-Find を使えばわかります。ここから自分自身とすでに友達関係にある人とブロック関係にある人を除けば解が得られます。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int N, int M, int K) = ReadInt3(); Dsu dsu = new Dsu(N); int[] exclusions = new int[N]; Array.Fill(exclusions, 1); // 自分自身は友達候補にはならない for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; dsu.Merge(a, b); exclusions[a]++; // すでに友達関係なら友達候補にはならない exclusions[b]++; } for (int i = 0; i < K; i++) { (int c, int d) = ReadInt2(); c--; d--; if (dsu.Same(c, d)) // 友達候補であってブロック関係なら友達候補にはならない { exclusions[c]++; exclusions[d]++; } } int[] ans = new int[N]; for (int i = 0; i < N; i++) ans[i] = dsu.Size(i) - exclusions[i]; Console.WriteLine(string.Join(" ", ans)); } } |
D – Detonate a Dynamite
問題の概要
N 個の地雷が置かれている。i 番目の地雷は座標 (X[i] ,Y[i]) にある。
ある地雷が爆発すると、爆発した地雷と同じ X 座標にある地雷と、同じ Y 座標にある地雷が連鎖的に爆発する。
新しく地雷を 1 つ設置し、それを爆発させることによって、なるべく多くの地雷を爆発させたい。
新しく設置した地雷も含めて爆発させることのできる地雷の個数の最大値を求めよ。
X 座標か Y 座標が同じ地雷は merge します。すると同一連結成分内の地雷はそのなかのひとつが爆発するとすべて誘爆することになります。
新しく設置することで異なる連結成分内の地雷を誘爆させることができるので、地雷がもっとも多い連結成分と二番目に多い連結成分の地雷の数の合計に新しく設置した地雷の数を加えた値を出力すればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } int N = int.Parse(Console.ReadLine()); Dsu dsu = new Dsu(N); // 新しく座標 x or y に設置された地雷の番号 Dictionary<int, int> dicX = new Dictionary<int, int>(); Dictionary<int, int> dicY = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { // すでに同じ x 座標に置かれている地雷があれば merge する (int x, int y) = ReadInt2(); if (!dicX.ContainsKey(x)) dicX.Add(x, i); else dsu.Merge(i, dicX[x]); // y 座標も同様に if (!dicY.ContainsKey(y)) dicY.Add(y, i); else dsu.Merge(i, dicY[y]); } Console.WriteLine(dsu.Groups().Select(_ => _.Length).OrderByDescending(_ => _).Take(2).Sum() + 1); } } |
D – 似ている文字列
問題の概要
英小文字の組 (A[i], B[i]) が N 組与えられる。
A[i], B[i] は似ている文字なので相互に置き換え可能である。
長さの等しい文字列 S, T が与えられる。
S と T を一致させることができるかどうか判定せよ。
文字を整数に変換して似ている文字同士であれば merge します。同一連結成分内の文字はすべて代表元に置き換えます。このような置換処理をしたあと、最後に S と T が一致しているかどうか調べればよいです。
|
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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Dsu dsu = new Dsu(26); for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); int a = vs[0][0] - 'a'; int b = vs[1][0] - 'a'; dsu.Merge(a, b); } string S = Console.ReadLine(); string T = Console.ReadLine(); for (int i = 0; i < 26; i++) { char old_char = (char)(i + 'a'); char new_char = (char)(dsu.Leader(i) + 'a'); if (old_char != new_char) { S = S.Replace(old_char, new_char); T = T.Replace(old_char, new_char); } } Console.WriteLine(S == T ? "Yes" : "No"); } } |
