質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

1060閲覧

atcoder150cが分からず困ってます

syuheisyosinsya

総合スコア17

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/06/06 05:12

編集2020/06/06 05:13

atcoderで下記問題に対して
問題
参考URL

下のコードで回答されている方がいて、
13行目
a += l.index(P[i]) * fac[len(l) - 1]
この処理が理解できず困っています。
ここではどのような処理が行われているのでしょうか?
ご教示よろしくお願いいたします。

python

1N = int(input()) 2P = list(map(int, input().split())) 3Q = list(map(int, input().split())) 4 5fac = [0] * 8 6fac[1] = 1 7for i in range(2, N): 8 fac[i] = i * fac[i - 1] 9 10a = 0 11l = list(range(1, N + 1)) 12for i in range(N): 13 a += l.index(P[i]) * fac[len(l) - 1] 14 l.remove(P[i]) 15 16b = 0 17l = list(range(1, N + 1)) 18for i in range(N): 19 b += l.index(Q[i]) * fac[len(l) - 1] 20 l.remove(Q[i]) 21 22print(abs(a - b))

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

その式は上の桁から順に数字を固定していき、その桁でその数字が初めて出現したときの順位を順に足していっています。

入力例2の(7 3 5 4 2 1 6 8)を例にとると、まず最上位の桁が7です。仮に最上位の桁が1とすると、残りの数字(2 3 4 5 6 7 8)が取りうる組み合わせは7! = 5040あります。すなわち、全体の集合のうち辞書順が1から5040番目までは最上位の桁が1です。同様に最上位の桁が2の数列は辞書順5041から10080までです。
つまり最上位の桁が7の場合、(7-1)*7! = 30240番目が先頭になります。

次に2番目の桁を考えます。最上位はほおっておいて、2から8桁目までの数字で同じように順位を作っていきます。(1 2 3 4 5 6 8)で3は3番目。数字を1つ固定すると残りの6つの数字でとりうる組み合わせは6! = 840。3が先頭にくる最初の順番は(3-1)*6! = 1680です。これと先ほどの7が最上位の順番を足し合わせると、先頭2文字が(7 3)の場合の一番最初の順番が求まります。

同様に最後の桁まで計算していくとその数列の辞書順順位が求まるわけです。

投稿2020/06/06 06:21

hope_mucci

総合スコア4447

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

syuheisyosinsya

2020/06/06 07:12

7!を6回したって計算なんですね! 分かりやすく解説していただき、ありがとうございました。
guest

0

a += l.index(P[i]) * fac[len(l) - 1]

i番目の文字が辞書順の何番目になるかの算出ですね。

facは0, 1, 2, 6, 24, 120が入ってます。

この値は、パターン数になっております。

例:

3 1 3 2 3 1 2

においての3 1 2において
最初の3は辞書順で何番目になるかというと残り2桁ののパターン数である2とあとはその桁のパターン数である(3 - 1)になります。あとはその繰り返し

投稿2020/06/06 06:12

rururu3

総合スコア5545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

syuheisyosinsya

2020/06/06 07:12

早急な回答ありがとうございます。 こちらの回答もとても参考になりました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問