問題一覧 > 通常問題

No.270 next_permutation (1)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : antaanta
5 ProblemId : 569 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:11

問題文

ある$n$に対する$[1,2,\ldots,n]$の置換(permutation) $x$に対し、$f(x)$を辞書順で$x$の次の置換とする。 ただし、$x$が辞書順で最後のもの$[n,n-1, \ldots, 1]$である場合は、$f(x)$を辞書順で最初のもの$[1,2,\ldots,n]$として定義する。 たとえば、$f([1, 2, 3]) = [1, 3, 2]$, $f(f([3,1,2])) = f([3,2,1]) = [1,2,3]$ となる。

ある$n$に対し長さが$n$の2つの配列$x, y$に対する$L_1$距離 $\displaystyle \sum_{i=1}^n |x_i - y_i|$を${\rm dist}(x, y)$として表す。 たとえば、$x = [1,2,3], y = [3,2,1]$なら${\rm dist}(x, y) = |1-3| + |2-2| + |3-1| = 4$となる。

置換$p$が与えられたとき、置換の列$A$を、$A_0 = p$, $A_i = f(A_{i-1})$ ($i \in [1,2,\ldots]$) として定義する。 つまり、$A_i$は$p$に$f$を$i$回適用したものである。 たとえば、$p = [2,1,3]$ なら $A = [[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$ となる。 $A$の添字は0から始まることに注意せよ。

整数$N$, 整数$K$, 長さ$N$の置換$p$, 長さ$N$の配列$B$ が入力として与えられる。 $\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$を求めよ。

入力

$N$ $K$
$p_1$ $p_2$ $\ldots$ $p_N$
$B_1$ $B_2$ $\ldots$ $B_N$

1行目に、整数$N (1 \le N \le 10^5)$, 整数$K (0 \le K \le 10^5)$が空白区切りで与えられる。 2行目に、長さ$N$の$[1,2,\ldots,N]$の置換$p$が空白区切りで与えられる。 3行目に、長さ$N$の整数の配列$B (1 \le B_i \le 10^8)$が空白区切りで与えられる。

出力

$\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$を1行に出力せよ。

ヒント

総和の対象が$L_1$距離であることに大きな意味はないです。

サンプル

サンプル1
入力
3 5
2 1 3
3 2 1
出力
12

問題文にある$A$の例である。それぞれの${\rm dist}$は$[4, 2, 2, 0, 4]$となるので、その総和の$12$が答えとなる。

サンプル2
入力
3 36
1 2 3
1 1 1
出力
108

この場合、$A$は長さ$3! = 6$の周期で巡回する。1周期の${\rm dist}$和が$18$であるので、$18 \times \frac{36}{6} = 108$が答えとなる。

サンプル3
入力
1 100000
1
1
出力
0

サンプル4
入力
2 100000
1 2
100000000 100000000
出力
19999999700000

オーバーフローに注意せよ。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。