AtCoder Beginner Contest 150 C - Count Order
1月も終わるのが早いです、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc150/tasks/abc150_c)にて開催されました、AtCoder Beginner Contest 150 C問題「C - Count Order」の問題と僕との戦闘記です。
0.はじめに
1.問題文
大きさ N の順列 ( 1 , 2 , . . . , N ) を並び替えてできる数列) P , Q があります。
大きさ N の順列は N ! 通り考えられます。このうち、 P が辞書順で a 番目に小さく、 Q が辞書順で b 番目に小さいとして、 | a − b | を求めてください。
2.制約
- 2 ≤ N ≤ 8
- P , Q は大きさ N の順列である。
- 入力は全て整数である。
3.入力例
- 入力
8 7 3 5 4 2 1 6 8 3 8 2 5 4 6 7 1
- 出力
17517
4.初見の感想
- 制約が2~8なので入力として考えられるパターンを全部列挙して、何番目かを確かめたい
- どうやって辞書順に並べ替えるか
5.学びポイント
- 順列を辞書順で作成するPermutationクラスを作った
- 再帰的処理で順列を作成
- 先頭で「1」を使う→「2,3,4」で残りの順列を作るという感じ
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; public class Permutation { //再帰の初期セットを代入する処理 public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) { return _GetPermutations<T>(new List<T>(), items.ToList()); } //再帰関数 private IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> items) { if (items.Count() == 0) { yield return perm.ToArray(); } else { foreach (var item in items) { //先頭の文字を省いて再帰を回す var result = _GetPermutations<T>(perm.Concat(new T[] { item }), items.Where(x => x.Equals(item) == false)); foreach (var xs in result) yield return xs.ToArray(); } } } } class Program { public static void Main() { int N = int.Parse(Console.ReadLine()); string[] input = Console.ReadLine().Split(); string[] input2 = Console.ReadLine().Split(); int[] A = new int[N]; int[] B = new int[N]; int[] temp = new int[N]; int pattern = 1; for (var i = 0; i < N; i++) { A[i] = int.Parse(input[i]); B[i] = int.Parse(input2[i]); //patternで順列の総数を計算 pattern *= (i + 1); //最初に入力する1~Nまでの順列を準備 temp[i] = i+1; } int[,] all_list = new int[pattern, N]; var perm = new Permutation(); int count = 0,a_num=0,b_num=0; bool A_flag = true; bool B_flag = true; foreach (var n in perm.Enumerate(temp)) { A_flag = true;B_flag = true; for (int i = 0; i < N; i++) { //辞書順でAやBと一致しないところがあればflagをfalse all_list[count, i] = n[i]; if (A[i] != n[i]) A_flag = false; if (B[i] != n[i]) B_flag = false; } count++; //辞書順をa_num,b_numに保存 if (A_flag == true) { a_num = count; } if (B_flag == true) { b_num = count; } } Console.WriteLine(Math.Abs(a_num - b_num)); } }
7.最後に
この問題みんな通してるんだけど、僕は苦手な気がします…