AtCoder NoviStepsを埋めてみる(4) bit全探索の続きです。今回は順列全探索です。
C++ であれば標準ライブラリである next_permutation 関数を用いて順列全探索を行うことができます。ただ C# にはこのようなものがないそうです。しかし ac-library-csharp というライブラリには同じようなメソッドがあります。今回はこれを使い倒すことにします。
StlFunction.NextPermutationメソッドの使い方は C++ の next_permutation 関数 とほぼ同じです。
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); } } |
