AtCoder NoviStepsを埋めてみる(4) bit全探索の続きです。今回は順列全探索です。
C++ であれば標準ライブラリである next_permutation 関数を用いて順列全探索を行うことができます。ただ C# にはこのようなものがないそうです。しかし ac-library-csharp というライブラリには同じようなメソッドがあります。今回はこれを使い倒すことにします。
StlFunction.NextPermutationメソッドの使い方は C++ の next_permutation 関数 とほぼ同じです。
Contents
- 1 C – Count Order
- 2 C – Average Length
- 3 C – One More aab aba baa
- 4 C – Select Mul
- 5 032 – AtCoder Ekiden（★3）
- 6 C – One-stroke Path
- 7 C – Avoid K Palindrome 2
- 8 C – Graph Isomorphism
- 9 C – Make Isomorphic
- 10 D – Laser Marking
- 11 D – joisino’s travel
- 12 D – Make 2-Regular Graph
- 13 E – Modulo MST
- 14 D – Swapping Puzzle
- 15 C – False Hope
- 16 D – Send More Money
C – Count Order
問題の概要
(1, 2, …, N) を並び替えてできる数列 P, Q がある。
N の順列は N! 通り考えられるが、このうち P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして |a – b| の値は？
StlFunction.NextPermutationメソッドで順列を求め、数列 P, Q が何番目の順列かを調べればよいです。
|
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 N = int.Parse(Console.ReadLine()); int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] Q = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i + 1; bool Check(int[] arr1, int[] arr2) { for (int i = 0; i < N; i++) { if(arr1[i] != arr2[i]) return false; } return true; } int loop = 0; int a = -1; int b = -1; do { loop++; if (Check(arr, P)) a = loop; if (Check(arr, Q)) b = loop; if (a != -1 && b != -1) break; } while (StlFunction.NextPermutation(arr)); Console.WriteLine(Math.Abs(a - b)); } } |
C – Average Length
問題の概要
座標平面上に N 個の町（座標は (x[i] , y[i])）がある。
これらの町をすべて 1 回ずつ訪れるとき、その移動距離の総和の平均値を計算せよ。
N 個の町を並べ替えた順列を生成して出発点から終着点までの移動距離の総和を計算してその平均値を求めればよいです。
|
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 |
using AtCoder; class Program { static void Main() { (double, double) ReadDouble2() { string[] vs = Console.ReadLine().Split(); return (double.Parse(vs[0]), double.Parse(vs[1])); } int N = int.Parse(Console.ReadLine()); int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; (double, double)[] pairs = new (double, double)[N]; for (int i = 0; i < N; i++) pairs[i] = ReadDouble2(); List<double> dists = new List<double>(); do { double d = 0; for (int i = 0; i < N - 1; i++) { var pos1 = pairs[arr[i]]; var pos2 = pairs[arr[i + 1]]; d += Math.Sqrt(Math.Pow(pos1.Item1 - pos2.Item1, 2) + Math.Pow(pos1.Item2 - pos2.Item2, 2)); } dists.Add(d); } while (StlFunction.NextPermutation(arr)); Console.WriteLine(dists.Average()); } } |
C – One More aab aba baa
与えられた文字を配列に格納して StlFunction.NextPermutation メソッドを使えばよいです。文字も整数の配列と同じように使えます。先頭の順列から何番目かを求めなければならないので入力された文字列をソートしておく必要があります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
using AtCoder; class Program { static void Main() { string[] vs = Console.ReadLine().Split(); char[] S = vs[0].ToArray(); int N = int.Parse(vs[1]); Array.Sort(S); List<string> T = new List<string>(); do T.Add(new string(S)); while (StlFunction.NextPermutation(S)); Console.WriteLine(T[N - 1]); } } |
C – Select Mul
問題の概要
整数 N が与えられる。
N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離する。
ただし、分離されたあとの 2 整数に leading zero が含まれていてはならない。
分離後の 2 数の積の最大値は？
整数 N を文字列とみなしてその順列を考えます。2 数にわけるときはわけることがすべての部分を考えます。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 |
using AtCoder; class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); int len = S.Length; Array.Sort(S); long ans = 0; do { for (int i = 1; i < len; i++) { string s1 = new string(S.Take(i).ToArray()); string s2 = new string(S.Skip(i).ToArray()); if (s1[0] != '0' && s2[0] != '0') ans = Math.Max(ans, long.Parse(s1) * long.Parse(s2)); } } while (StlFunction.NextPermutation(S)); Console.WriteLine(ans); } } |
032 – AtCoder Ekiden（★3）
問題の概要
N 人の駅伝選手がいる。1 人の選手が 1 つの区のみを担当して走る。
選手 i が第 j 区を走るのにかかる時間は A[i, j] である。
「選手 X[i] と Y[i] は仲が悪い」という 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 60 61 62 63 64 65 66 |
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[][] A = new int[N][]; for (int i = 0; i < N; i++) A[i] = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int M = int.Parse(Console.ReadLine()); // 仲が悪い組み合わせ HashSet<string> set = new HashSet<string>(); for (int i = 0; i < M; i++) { (int x, int y) = ReadInt2(); x--; y--; set.Add($"{x},{y}"); set.Add($"{y},{x}"); } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; int ans = int.MaxValue; do { bool ok = true; // 仲が悪い選手が隣り合っていないか調べる for (int i = 0; i < N - 1; i++) { if (set.Contains($"{arr[i]},{arr[i + 1]}")) { ok = false; break; } } // 仲が悪い選手が隣り合っていないなら完走するまでのタイムを計算する if (ok) { int time = 0; for (int i = 0; i < N; i++) time += A[arr[i]][i]; ans = Math.Min(ans, time); } } while (StlFunction.NextPermutation(arr)); if (ans == int.MaxValue) ans = -1; Console.WriteLine(ans); } } |
C – One-stroke Path
問題の概要
自己ループと二重辺を含まない N 頂点 M 辺の重み無し無向グラフが与えられる。
頂点 1 を始点として、全ての頂点を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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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(); HashSet<string> set = new HashSet<string>(); for (int i = 0; i < M; i++) { (int x, int y) = ReadInt2(); x--; y--; set.Add($"{x},{y}"); set.Add($"{y},{x}"); } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; int ans = 0; do { bool ok = true; if (arr[0] != 0) continue; for (int i = 0; i < N - 1; i++) { if (!set.Contains($"{arr[i]},{arr[i + 1]}")) // 隣り合った要素が辺で繋がっていない { ok = false; break; } } if (ok) ans++; } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
C – Avoid K Palindrome 2
問題の概要
S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として含まないものの個数を求めよ。
順列をつかって S の文字を並び替えて得られる文字列を生成して、長さ 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 |
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 K) = ReadInt2(); char[] S = Console.ReadLine().ToArray(); Array.Sort(S); // NextPermutation メソッドを使うときは最初の配列は昇順ソートされていること // 長さ K の部分文字列に回文が存在しないことをチェックする bool Check(char[] S) { for (int start = 0; start + K <= N; start++) { // 長さ K の部分文字列をすべて取得する List<char> list = new List<char>(); for (int i = start; i < start + K; i++) list.Add(S[i]); bool ok = false; // 長さ K の部分文字列が回文でなければ OK for (int i = 0; i < K; i++) { if (list[i] != list[K - 1 - i]) { ok = true; break; } } if (!ok) return false; } return true; } int ans = 0; do { if( Check(S)) ans++; } while (StlFunction.NextPermutation(S)); Console.WriteLine(ans); } } |
C – Graph Isomorphism
問題の概要
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 60 61 62 63 64 65 66 |
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(); // ふたつのグラフの隣接行列を生成する bool[,] mat1 = new bool[N, N]; for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; mat1[a, b] = true; mat1[b, a] = true; } bool[,] mat2 = new bool[N, N]; for (int i = 0; i < M; i++) { (int c, int d) = ReadInt2(); c--; d--; mat2[c, d] = true; mat2[d, c] = true; } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; // 合同であるかチェック bool Check() { for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { if (mat1[a, b] != mat2[arr[a], arr[b]]) return false; } } return true; } bool yes = false; do { if (Check()) { yes = true; break; } } while (StlFunction.NextPermutation(arr)); Console.WriteLine(yes ? "Yes" : "No"); } } |
C – Make Isomorphic
問題の概要
ふたつの単純無向グラフ G, H が与えられる。
A[i, j] 円を支払って、頂点 i と頂点 j を結ぶ辺がなければ追加し、あれば取り除く。
G と H を同型にするために少なくとも何円支払う必要があるだろうか？
順列をつかってグラフ H の頂点の位置を入れ替え、対応する辺が一致するようにするために必要なコストを調べ、最小になるものを調べます。
|
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 |
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 M1 = int.Parse(Console.ReadLine()); bool[,] mat1 = new bool[N, N]; for (int i = 0; i < M1; i++) { (int a, int b) = ReadInt2(); a--; b--; mat1[a, b] = true; mat1[b, a] = true; } int M2 = int.Parse(Console.ReadLine()); bool[,] mat2 = new bool[N, N]; for (int i = 0; i < M2; i++) { (int c, int d) = ReadInt2(); c--; d--; mat2[c, d] = true; mat2[d, c] = true; } int[,] costs = new int[N, N]; for (int r = 0; r < N - 1; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int i = 0; i < vs.Length; i++) { int c = i + r + 1; costs[r, c] = vs[i]; costs[c, r] = vs[i]; } } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; int ans = int.MaxValue; do { int cost = 0; for (int a = 0; a < N; a++) { // 同じ辺を 2 回数えないように b > a のときだけ調べる for (int b = a + 1; b < N; b++) { if (mat1[a, b] != mat2[arr[a], arr[b]]) cost += costs[arr[a], arr[b]]; } } ans = Math.Min(ans, cost); } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
D – Laser Marking
問題の概要
xy 平面に対し、レーザを照射しながら線分を印字する印字機があります。
印字開始時、レーザ照射位置は座標 (0, 0) にある。
印字するときはレーザ照射位置を線分の端点のうちどちらか 1 つに移動させる。
その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。
どちらの端点から描画を始めてもよいが、線分の途中で印字を中止することはできない。
レーザ照射位置は、レーザを照射していない時は 1 秒あたり速度 S で任意の方向に、照射している時は 1 秒あたり速度 T で印字中の線分に沿って移動できる。
N 本の線分を印字したい。線分は座標 (A[i], B[i]) と座標 (C[i], D[i]) を結ぶ。
すべての線分を印字完了するまでにかかる最小の時間は何秒？
どの順番で印字するかは順列をつかって全探索すればよいです。ふたつの端点のうちどちらから印字するかはbit全探索を使えばよいです。全体の計算量は O(N! × 2^N)です。
|
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 |
using AtCoder; class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (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 N, int S, int T) = ReadInt3(); ((int, int),(int, int))[] pairs = new ((int, int), (int, int))[N]; for (int i = 0; i < N; i++) { (int x1, int y1, int x2, int y2) = ReadInt4(); pairs[i] = ((x1, y1), (x2, y2)); } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; // 第一引数は印字する線分の順番、第二引数は印字はどちらの端点からおこなうか？ double Solve(int[] arr, int bit) { double res = 0; double x = 0; double y = 0; for (int i = 0; i < N; i++) { int idx = arr[i]; // 印字開始点への移動時間を計算する var pair1 = ((bit >> i) & 1) == 1 ? pairs[idx].Item1 : pairs[idx].Item2; double sx = pair1.Item1; double sy = pair1.Item2; double d1 = Math.Sqrt(Math.Pow(sx - x, 2) + Math.Pow(sy - y, 2)); res += d1 / S; // 印字終了点への移動時間を計算する var pair2 = ((bit >> i) & 1) == 1 ? pairs[idx].Item2 : pairs[idx].Item1; double tx = pair2.Item1; double ty = pair2.Item2; double d2 = Math.Sqrt(Math.Pow(tx - sx, 2) + Math.Pow(ty - sy, 2)); res += d2 / T; x = tx; y = ty; } return res; } double ans = double.MaxValue; do { for (int bit = 0; bit < 1 << N; bit++) ans = Math.Min(ans, Solve(arr, bit)); } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
D – joisino’s travel
問題の概要
N 個の町があり、M 本の双方向に移動可能な道で結ばれている。
i 本目の道は町 A[i] と町 B[i] の間を距離 C[i] で結んでいる。
R 個の町 r[0], r[1], …, r[R – 1] をすべて訪問したい。
訪問する順番を自由に選べるとして、移動距離を最小にしようとした場合の移動距離は？
まずダイクストラ法で任意の 2 つの町のあいだの移動時間を求めておきます。そのあと r の順列をすべて調べてどの順番で訪問すると移動時間が最小になるかを調べます。
|
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 |
using AtCoder; class Program { static void Main() { (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 R) = ReadInt3(); int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); 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 a, int b, int c) = ReadInt3(); a--; b--; G[a].Add((b, c)); G[b].Add((a, c)); } // ダイクストラ法で町 start からすべての町への移動距離を調べる long[] Dijkstra(int start) { long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (var edge in G[cur]) { int next = edge.Item1; long ncost = costs[cur] + edge.Item2; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } } return costs; } // 任意の 2 つの町の移動時間を取得する long[,] dists = new long[N, N]; for (int r = 0; r < N; r++) { long[] res = Dijkstra(r); for (int c = 0; c < N; c++) dists[r, c] = res[c]; } int[] arr = new int[R]; for (int i = 0; i < R; i++) arr[i] = X[i] - 1; Array.Sort(arr); // あとは順列で移動時間を計算して最小値を取得するだけ long ans = long.MaxValue; do { long dist = 0; for (int i = 0; i < R - 1; i++) dist += dists[arr[i + 1], arr[i]]; ans = Math.Min(ans, dist); } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
D – Make 2-Regular Graph
N 頂点 M 辺の単純無向グラフ G があります。
G に無向辺を 1 つ追加または 1 つ削除するという操作を繰り返すことで、G をすべての頂点の次数が 2 である単純無向グラフにするために行う操作回数として考えられる最小値を求めよ。
求めようとしているグラフが連結しているのであれば頂点の順列を生成してそれぞれについて調べればよいのですが、「すべての頂点の次数が 2 である単純無向グラフ」が連結している保証はどこにもありません。
ただし、N の最大値は 8 です。N が 5 以下のときは「すべての頂点の次数が 2 である単純無向グラフ」が連結したグラフにしかなりません。N が 6 または 7 のときは連結グラフか、3 つの頂点が連結した部分グラフと残りの頂点が連結した部分グラフ ＝ 連結成分数 2 のグラフになります。N が 8 のときはさらに加えて、4 つの頂点が連結した部分グラフが 2 つできます。問題の制約のもとでは連結成分数は 1 か 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 60 61 62 63 64 65 66 67 |
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(); 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 a, int b) = ReadInt2(); a--; b--; G[a].Add(b); G[b].Add(a); } int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = i; int Solve(int[] arr) { int res = 0; for (int i = 0; i < arr.Length; i++) { int cur = arr[i]; int next1 = arr[(i + 1) % arr.Length]; int nidx2 = i - 1; if (nidx2 < 0) nidx2 += arr.Length; int next2 = arr[nidx2]; if (G[cur].IndexOf(next1) == -1) res++; if (G[cur].IndexOf(next2) == -1) res++; res += G[cur].Count(_ => _ != next1 && _ != next2); } return res; } int ans = int.MaxValue; do { ans = Math.Min(ans, Solve(arr) / 2); if(N >= 6) { ans = Math.Min(ans, (Solve(arr.Take(3).ToArray()) + Solve(arr.Skip(3).ToArray())) / 2); if (N == 8) ans = Math.Min(ans, (Solve(arr.Take(4).ToArray()) + Solve(arr.Skip(4).ToArray())) / 2); } } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
E – Modulo MST
N 頂点 M 辺の重み付き単純連結無向グラフと正整数 K が与えられる。
辺 i は頂点 u[i] と頂点 v[i] を結んでおり、重みは w[i] である。
このグラフの全域木 T に対して、T のコストを T に含まれる辺の重みの総和を K で割ったあまりと定義する。
このグラフの全域木のコストの最小値は？
頂点数の最大値は 8 であり、このグラフが完全グラフの場合、辺の数は 28 となります。順列を使った処理をするにしては数が大きそうなのですが、bool変数の順列であれば長さ 28 でも高速に動作します。
全域木なので M 本ある辺のなかからどれを使うかを N – 1 本選び、それらの辺を使って本当に全域木が構築されるのかを調べます。構築できる場合は辺の重みの総和を計算して全域木 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
using AtCoder; class Program { static void Main() { (int, int, long) ReadValues3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), long.Parse(vs[2])); } (int N, int M, long K) = ReadValues3(); List<(int, int, long)> E = new List<(int, int, long)>(); for (int i = 0; i < M; i++) { (int u, int v, long w) = ReadValues3(); u--; v--; E.Add((u, v, w)); } bool[] arr = new bool[M]; for (int i = 0; i < M; i++) arr[i] = false; for (int i = 0; i < N - 1; i++) arr[i] = true; arr = arr.Reverse().ToArray(); long ans = long.MaxValue; do { long cost = 0; Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { if (arr[i]) { cost += E[i].Item3; cost %= K; dsu.Merge(E[i].Item1, E[i].Item2); } } if (dsu.Groups().Length == 1) ans = Math.Min(ans, cost); } while (StlFunction.NextPermutation(arr)); Console.WriteLine(ans); } } |
D – Swapping Puzzle
問題の概要
H 行 W 列の 2 つのグリッド A, B が与えられます。
グリッド A の 隣り合う 2 つの行または列を入れ替える操作を繰り返すことで、グリッド A をグリッド B に一致させることが可能かどうかを判定せよ。
可能な場合は必要な操作回数の最小値も出力せよ。
これも順列を使って行と列を入れ替えるすべてのパターンを試してグリッド A をグリッド B に一致させることができるか試してみればよいです。
一致させることができた場合は、隣り合う 2 つの行または列を入れ替える操作を何回すればよいかを出力しなければなりません。隣り合ったものと入れ替える回数は「転倒数」を求めることでわかります。
転倒数の計算方法ですが、数列中の「左にある要素が右の要素より大きい」組の個数を数えればできます。Binary Indexed Tree を用いて高速に求める方法もありますが、行数も列数も最大 5 なので愚直な方法で実装しています。
|
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 |
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(); int[,] A = new int[H, W]; for (int r = 0; r < H; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < W; col++) A[r, col] = vs[col]; } int[,] B = new int[H, W]; for (int r = 0; r < H; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < W; col++) B[r, col] = vs[col]; } int[] rows = new int[H]; for (int i = 0; i < H; i++) rows[i] = i; int[] cols = new int[W]; for (int i = 0; i < W; i++) cols[i] = i; // 転倒数を求める // 数列中の「左にある要素が右の要素より大きい」組の個数を数える int Inverse(int[] arr) { int len = arr.Length; int res = 0; for (int left = 0; left < len; left++) { for (int right = left + 1; right < len; right++) { if (arr[left] > arr[right]) res++; } } return res; } // 行と列の入れ替え全パターン試す int ans = int.MaxValue; do { Array.Sort(cols); do { int[,] grid = new int[H, W]; for (int r = 0; r < H; r++) { for (int col = 0; col < W; col++) grid[r, col] = A[rows[r], cols[col]]; } bool ok = true; for (int r = 0; r < H; r++) { for (int col = 0; col < W; col++) { if (grid[r, col] != B[r, col]) { ok = false; break; } if (!ok) break; } } if (ok) ans = Math.Min(ans, Inverse(rows) + Inverse(cols)); } while (StlFunction.NextPermutation(cols)); } while (StlFunction.NextPermutation(rows)); if (ans == int.MaxValue) ans = -1; Console.WriteLine(ans); } } |
C – False Hope
3 × 3 のマス目に 1 から 9 までの数字が書き込まれており、上から i 行目、左から j 列目 に書き込まれている数字は c[i, j] です。
高橋くんは、それぞれのマスに書かれている数字をランダムな順番で知るが、縦・横・斜めの列のうちの 1 つでも以下の条件を満たしたときがっかりする。
はじめに知ったほうの 2 マスに書かれた数字が同じであり、最後に知ったマスに書かれた数字がそれと異なる。
高橋くんががっかりせずにすべてのマスに書かれた数字を知る確率は？
全部で 9 マスあるが、どのような順番で数字を知るかを全パターン試してみればよいです。
縦・横・斜めの列は全部で 8 個あるが、それらのなかで最初に知ったもの、2番めに知ったもの、最後に知ったものをリストに格納し、最後にがっかりする条件を満たしていないか確認します。
がっかりしない回数 / 9! が出力すべき解となります。
|
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 |
using AtCoder; class Program { static void Main() { int[,] A = new int[3, 3]; for (int r = 0; r < 3; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < 3; col++) A[r, col] = vs[col]; } int[] arr = new int[9]; for (int i = 0; i < 9; i++) arr[i] = i; int all = 0; int cnt = 0; do { List<int>[] rows = new List<int>[3]; List<int>[] cols = new List<int>[3]; List<int> slash = new List<int>(); List<int> back_slash = new List<int>(); for (int i = 0; i < 3; i++) { rows[i] = new List<int>(); cols[i] = new List<int>(); } foreach (var idx in arr) { int r = idx / 3; int c = idx % 3; rows[r].Add(A[r, c]); cols[c].Add(A[r, c]); if (idx == 0 || idx == 4 || idx == 8) back_slash.Add(A[r, c]); if (idx == 2 || idx == 4 || idx == 6) slash.Add(A[r, c]); } bool ok = true; for (int i = 0; i < 3; i++) { if (rows[i][0] == rows[i][1] && rows[i][1] != rows[i][2]) ok = false; if (cols[i][0] == cols[i][1] && cols[i][1] != cols[i][2]) ok = false; } if (slash[0] == slash[1] && slash[1] != slash[2]) ok = false; if (back_slash[0] == back_slash[1] && back_slash[1] != back_slash[2]) ok = false; all++; if (ok) cnt++; } while (StlFunction.NextPermutation(arr)); Console.WriteLine(1.0 * cnt / all); } } |
D – Send More Money
問題の概要
英小文字からなる文字列 S1, S2, S3 が与えられる。
覆面算 S1 + S2 = S3 を解け。
ただし同じ文字には同じ数字が入る。
異なる文字に同じ数字は入らない。
文字列 S1, S2, S3 の先頭の文字は 0 ではない。
文字列 S1, S2, S3 に使われている文字が 11 種類以上なら解は存在しません。10種類以下の場合はこれに 0 ～ 9 を割り当てるパターンをすべて試します。入力に使われている文字が ‘a’から順番といった規則性がないのでさいしょにそれぞれの文字に 0 ～ 9 のインデックスを割り当てます。
あとは順列全探索をして解をみつけたらそれを出力して見つからない場合は”UNSOLVABLE”を出力します。
|
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 |
using AtCoder; class Program { static void Main() { string[] S = new string[3]; HashSet<char> set = new HashSet<char>(); List<char> list = new List<char>(); for (int i = 0; i < 3; i++) { S[i] = Console.ReadLine(); foreach (char ch in S[i]) { if (!set.Contains(ch)) { set.Add(ch); list.Add(ch); } } } if (set.Count > 10) { Console.WriteLine("UNSOLVABLE"); return; } Dictionary<char, int> dic = new Dictionary<char, int>(); for (int i = 0; i < list.Count; i++) dic.Add(list[i], i); int[] arr = new int[10]; for (int i = 0; i <= 9; i++) arr[i] = i; string[] Check() { string[] T = new string[3]; for (int i = 0; i < 3; i++) { string s = ""; foreach (char ch in S[i]) s += arr[dic[ch]].ToString(); T[i] = s; } if (T[0][0] == '0' || T[1][0] == '0' || T[2][0] == '0') return null; if (long.Parse(T[0]) + long.Parse(T[1]) == long.Parse(T[2])) return T; else return null; } do { var ans = Check(); if (ans != null) { foreach (var str in ans) Console.WriteLine(str); return; } } while (StlFunction.NextPermutation(arr)); Console.WriteLine("UNSOLVABLE"); } } |
