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

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

ただいまの
回答率

87.33%

atcoder150cが分からず困ってます

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 569

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

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

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

fac = [0] * 8
fac[1] = 1
for i in range(2, N):
    fac[i] = i * fac[i - 1]

a = 0
l = list(range(1, N + 1))
for i in range(N):
    a += l.index(P[i]) * fac[len(l) - 1]
    l.remove(P[i])

b = 0
l = list(range(1, N + 1))
for i in range(N):
    b += l.index(Q[i]) * fac[len(l) - 1]
    l.remove(Q[i])

print(abs(a - b))
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

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

入力例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 16:12

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

    キャンセル

+1

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 16:12

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

    キャンセル

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

  • ただいまの回答率 87.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る