itertoolsを使わないABC C問題 Count Order

C - Count Order

今回やらせていただく問題はこちら。

問題文の方はリンクから直接参照いただきたいです。
問題文をざっと説明すると、
例えば、A = 1, 2, 3みたいな数列があり、これを適当に並べ替えた数列がP、Qとなります。ここでは便宜上、P=1,2,3 Q=1,3,2とします。但し、数列の要素は重複しないものとします。A=1,2,2,3というものはないということです。
P、Qの数列は、それぞれ、数列Aの数字を並べ替えたときの一つの候補ですよね。数列Aの並べ替える通り数は、今回の場合、数列の要素が３つあるので３！個つまり６個あります。その６個の数列を辞書順に昇順で並べ替えたとき、PとQは何番目に位置するのかを調べます。Pの位置をa、Qの位置をbと置くと、出力する値は  | a - b| となります。

ここで辞書順について説明します。
今回は P=1,2,3  Q= 1,3,2 としています。そこでP、Qをそれぞれ左から見ていったときに、数列の２番目の値から異なっていますね。Pの２番目は２となっていて、Qの２番目は３となっています。２＜３のため、辞書順ではPの方が小さく、Qの方が大きいということになります。
今回は小さい順に並べるので、それぞれの数列を左から見ていって異なる数字が現れたときに、その数字が大きい方が辞書順の後ろ側にくることになりますね。

A = 1,2,3　の数列の並びを辞書順に列挙するなら、
[1, 2, 3] , [1, 3, 2] , [2, 1, 3 ] , [2, 3, 1] , [3, 1, 2] , [3, 2, 1] となります。

Pは左から１番目にあるため、a = 1 、Qは左から２番目にあるため、b=2となります。よって求める答えは　| a - b | = | 1 - 2 | = 1　となります。

めちゃくちゃ長くなりましたね。

こういう問題はさっきやったように全て数列の候補を求めて、PとQの数列が何番目にあるかを求める方がよさそうではあります。
数列を並べ替えた候補を列挙する関数として、c++ではnext_permitation、pythonではitertoolsというものが用意されているようですが、僕は正直この二つの使い方をイマイチ心得ていません。なので、今回は全候補を列挙せずに問題を解いていきたいと思います。

解法を説明するうえで例を挙げます。P=1, 2, 4, 3みたいな適当な数列があるとします。全体の数列の並びは４！＝２４通りあります。

あらかじめ、Ｐの辞書順を格納するため変数result=0を用意します。

これの辞書順を求めるときにまず先頭から見ていきます。
まず最初の数字は１です。先頭の数字が固定されると、後ろの３つの数列の並びは３！＝６通りしかありません。また先頭の１という数字は1,2,3,4の数列の中では一番小さいため、この段階で考えられる辞書順は1~6番目ということになります。

先頭の数字に１が来た場合→　数列の辞書順が１～６番目
先頭の数字に２が来た場合→　数列の辞書順が７～１２番目
先頭の数字に３が来た場合→　数列の辞書順が１３～１８番目
先頭の数字に４が来た場合→　数列の辞書順が１９～２４番目

この手前の数字をresultに足します。先頭の数字が１の場合は辞書順が1~6番目のため、０を足します。先頭の数字が２の場合、辞書順が７～１２番目のため、その手前の６を足します。先頭の数字に３が来た場合は同様に１２を足すといった要領です。
数列の先頭はP[0]と表せるので、これを式にすると
result = result + (P[0] - 1) * 3!  のような感じになります。

よって今回はresult+0 = 0となります。

そして便宜上、先頭の数字より大きい数字が後ろの残りの数列にある場合、その値から１を差し引きます。
今回はP＝１，２，４，３で２，４，３が先頭の１よりも大きいため、１，３，２になる感じです。

P＝１，１，３，２となります。
次は先頭から２番目を固定すると、３番目以降の数列の並びは２！＝２通りとなります。
先ほどのような式で表すと、
result = result + (P[1] - 1) * 2!
依然としてresult= 0ですね。

そして３番目以降の数字の中で、２番目の数字よりも大きい数字から１を引きます。

するとP＝１，１，２，１となりますね。
そして同様に
result = result + (P[2] -1) * 1! をするとresult = 1 となります。
そして最後にresult += 1　をすることでresult = 2 となり、Pは辞書順で見ると２番目にくることが分かります。

イマイチうまく説明できませんが、このようなやり方で順番を求めています。

次からはコード紹介をします。

def kaijou(num):
 result= 1
 for i in range(num):
   result *= (i+1)
 return result

def subtract(num, List):
 resultList = []
 for lisNum in List:
   if num  < lisNum:
     lisNum = lisNum-1
   resultList.append(lisNum)
 return resultList

def find_order_in_dictionary(List):
 result = 0
 for i in range(len(List)):
   result += (List[i]-1)*kaijouList[i]
   List= subtract(List[i], List)
 return result
     
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
kaijouList = [kaijou(N-i-1) for i in range(N)]

result =0
P_order = find_order_in_dictionary(P)+1
Q_order = find_order_in_dictionary(Q)+1
print(abs(P_order-Q_order))

まずは関数たちから

def kaijou(num):
 result= 1
 for i in range(num):
   result *= (i+1)
 return result

こちらは関数名の通り階乗を求める関数です。

def subtract(num, List):
 resultList = []
 for lisNum in List:
   if num  < lisNum:
     lisNum = lisNum-1
   resultList.append(lisNum)
 return resultList

こちらは先ほどの説明の中でもやっていた、i 番目の数以降の数字が、i 番目の数よりも大きかった場合、その数字から１を差し引くという処理です。

def find_order_in_dictionary(List):
 result = 0
 for i in range(len(List)):
   result += (List[i]-1)*kaijouList[i]
   List= subtract(List[i], List)
 return result

こちらは引数の数列が辞書順で何番目かを調べるための関数で、先ほどの説明した処理になります。kaijouList変数は後で説明します。

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
kaijouList = [kaijou(N-i-1) for i in range(N)]

result =0

Nが数列の個数&数列に出てくる数字の最大値。
Pが１つ目の数列
Qが二つ目の数列
kaijouListには(N-1)から１ずつ引いていった数字の階乗がN個分格納されています。

例えばN＝４とすると、数列の個数は４個なので、kaijouList= [ 3!, 2! , 1! , 0! ]みたいな感じになっています。

P_order = find_order_in_dictionary(P)+1
Q_order = find_order_in_dictionary(Q)+1
print(abs(P_order-Q_order))

最後の先ほどの関数を使用して、Pの辞書順とQの辞書順を求め、お互いに引いた数の絶対値を出力してファイナルアンサーです。