ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです!

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.はじめに

今回も、プログラミング言語C#を使用しています。

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.最後に

この問題みんな通してるんだけど、僕は苦手な気がします…