deepcopyとか階乗。(ABC150C)
お久しぶりです。えんぴつです。
最近はそこまで記事にするほど新たに学んだこともなかったので全然更新してなかったですね。ABCのBまでならコードの検索なしでだいぶ作れるようになってきた気がします。
anacondaを入れているのでjupiter Labでプログラミングをしていることが多いのですが、数行の入力例をテストとして入れるとき、コピペが使えない(1行にまとめられてしまう)のが最近の悩みです。誰か対処法教えてください…
前書きからわかる通り(?)今回は長丁場になるので目次で見たい場所まで飛んでくださいね。
今回の問題はこちら。
1~N番までの数字が並んだ数列が2つあって、辞書配列で何番目の配列なのかをそれぞれ出してその差の絶対値を出す問題でした。(詳しくはリンク先をクリックしてください…)
自分の解法
最初にそもそも辞書順ってどうやって出すの?って思ったので4桁の順列(N=4)を例に考えました。
↑手書きメモ(goodnoteより)
1324という順で並んでいる数列があった時、最初の数字は1なので1~6番目であると考えられます。
この1~6番目というのは1~24を4つ(N)で分けた時の最初のブロックです。
さらに2番目の数字が3である場合は3~4番目であると考えられますが、これは1~6を3つ(N-1)で分けた時の2つ目のブロックです。
同様に3桁目についても考えると4桁であればある数列の辞書順nは
n=1+(N!//N)*A+{(N-1)!//(N-1)}*B+{(N-2)!//(N-2)}*C
A=最初の数字は何番目?
B=1桁目の数字を抜かして考えた時、2つ目の数字は何番目?
C=1,2桁目の数字を抜かして考えた時、3つ目の数字は何番目?
※index参照を前提にしているので1324であればA=0、B=1ということになります
という式で求めることができます。
結局、「抜かす」という動作や何番目?を調べるためには1~Nまでの数字が入ったリストが必要だったので作りました。
下が自分の作ったコードです。
import math
import copy
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AL=[n for n in range(1,N+1)]
BL=copy.deepcopy(AL)
AA=1
BA=1
F=math.factorial(N)
AK=F
BK=F
for i in range(N-1):
AK//=(N-i)
a=A[i]
AA+=(AK*AL.index(a))
AL.remove(a)
for j in range(N-1):
BK//=(N-j)
b=B[j]
BA+=(BK*BL.index(b))
BL.remove(b)
print(abs(AA-BA))
同じ内容のリストを作る
今回数列A,Bに同じ処理をしたので同じリストや数字をA,Bの2つ分作ることになりました。すごく面倒だったのと、ものによっては処理時間がかかってしまうため何とかコピーを作ろうとしたんですが、リストに関しては特に制約が多かったです。
#errorが出た
A,B=[]
#Aの変更がBに反映された
A=[]
B=A
#成功した
import copy
A=[]
B=copy.deepcopy(A)
import copy の後、copy.deepcopyを使いました。copy.copyだとA,Bに共通する要素があればそれに関する変更は両方反映されてしまいます。
ちなみにA=B でつなぐと1つのリストに2つの名前を付けた状態になるそうです。↓参考記事
1~N までの数字が入ったリストを作る
AL=[n for n in range(1,N+1)]
range(N)にすると0~(N-1)のリストになってしまうので注意ですね
階乗を作る
import math
A=math.factorial(N)
今回学んだこと
#同じ内容のリストを作る
import copy
A=[]
B=copy.deepcopy(A)
#1~Nまでの数字が入ったリストを作る
L=[n for n in range(1,N+1)]
#階乗を作る
import math
K=math.factorial(N)
この記事が気に入ったらサポートをしてみませんか?