ざっと解説
ようやく理解したのでメモ。
コメントに全て解説を記述しています。同じ内容で提出しているのでどちらが検索に出てくるか。。。
色々他の人の解法を見ましたが、よくわからなかったのでノートに一行ずつ日本語で解説を書くノリで
全部書いています。
using System; using System.Collections.Generic; using System.Linq; namespace _150c { class Program { static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); int[] P = Array.ConvertAll(Console.ReadLine().Split(),int.Parse); int[] Q = Array.ConvertAll(Console.ReadLine().Split(),int.Parse); int[] factorial = new int[8]; //NのMAX 8なので //forに入れるの面倒なので0と1の階乗は先に入れておく factorial[0] = 0; factorial[1] = 1; //2以上の階乗の値も入れる for(int i = 2; i < 8; i++){ factorial[i] = i * factorial[i-1]; } //一つの数字あたりの組み合わせ数が求められる //例えば、例題のN=3のケースだと、1に対して組み合わせ2通り //2に対して組み合わせ2通り 3に対して組み合わせ2通り //factorial[N-1] = 2を使える //例えば 1 3 2 のケースだとまずは1が何番目か調べる必要がある //1の場所は配列でいうと0番目か1番目 //1が最初に出てくる配列番号は0*factorial[N-1]で求められる //213だったら、最初の数字が2なので1*factorial[N-1]としたい //そのために配列lを生成する List<int> l = new List<int>(); for(int i = 1; i<=N;i++){ l.Add(i); } //lが生成できたので行ないたいことを行う int a = 0; for(int i = 0; i<N;i++){ a += l.IndexOf(P[i])*factorial[l.Count()-1]; //1から推定される番号は2通りあるが、 //次の数字からは1通りになる。 //その組み合わせ数はfactorial[N-2] =factorial[ l.Count()-2]で置き換えられる //配列 lからP[i]を削除し、l.COuntをNとして使えばそれと同様のことができる l.Remove(P[i]); } int b = 0; //qについても同様の操作を行う List<int> m = new List<int>(); for(int i = 1; i<=N;i++){ m.Add(i); } for(int i = 0; i<N;i++){ b += m.IndexOf(Q[i])*factorial[m.Count()-1]; //1から推定される番号は2通りあるが、 //次の数字からは1通りになる。 //その組み合わせ数はfactorial[N-2] = l.Count()-2 //配列 lからP[i]を削除し、l.COuntをNとして使えばそれと同様のことができる m.Remove(Q[i]); } Console.WriteLine(Math.Abs(a-b)); } } }
その他
競技プログラミング時のお供に下記記事を参照ください。
infoaisaka.hatenablog.com