Edit

【pythonでABC150を解説】C - Count Order

問題概要

問題ページ

C - Count Order
C - Count Order

問題ページへ移動する

問題文

大きさ \(N\) の順列 (\((1,~2,~...,~N)\) を並び替えてできる数列) \(P,~Q\) があります。

大きさ \(N\) の順列は \(N!\) 通り考えられます。このうち、\(P\) が辞書順で \(a\) 番目に小さく、\(Q\) が辞書順で \(b\) 番目に小さいとして、\(|a - b|\) を求めてください。

注記

\(2\) つの数列 \(X,~Y\) について、ある整数 \(k\) が存在して \(X_i = Y_i~(1 \leq i < k)\) かつ \(X_k < Y_k\) が成り立つとき、\(X\) は \(Y\) より辞書順で小さいと定義されます。

制約

  • \(2 \leq N \leq 8\)
  • \(P,~Q\) は大きさ \(N\) の順列である。
  • 入力は全て整数である。

問題の考察

ACコード

import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    p = "".join(list(map(str, readline().rstrip().decode('utf-8').split())))
    q = "".join(list(map(str, readline().rstrip().decode('utf-8').split())))
    pp = 0
    qp = 0
    for i, v in enumerate(itertools.permutations(range(1, n + 1), n)):
        vstr = "".join(list(map(str, v)))
        if vstr == p:
            pp = i
        if vstr == q:
            qp = i
    print(abs(pp - qp))


if __name__ == '__main__':
    solve()

-Edit