週末副業記

土日は副業エンジニアのブログです。副業に関することを投稿します。

AtCoder Beginner Contest 150 C 【C#】


ざっと解説

ようやく理解したのでメモ。
コメントに全て解説を記述しています。同じ内容で提出しているのでどちらが検索に出てくるか。。。
色々他の人の解法を見ましたが、よくわからなかったのでノートに一行ずつ日本語で解説を書くノリで
全部書いています。

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