No.823
\(N = 1\) のときは得点はない.
\(K = 1\) のときはマス \(x\) にコマがある条件は \(A_1 \neq x\) なので, 得点の合計は
\[\sum_{x=1}^N x (N-1) = \frac{(N-1)N(N+1)}{2}\]となる.
以下それ以外のときを考える. \(A\) の得点を考えるのではなく, マス \(x\) が得点になる \(A\) の個数を考える.
操作後にマス \(x \ (1 \leq i \leq N-1)\) にコマがあるための条件は, 次のどちらかを満たすときである.
-
\(A_i = x\) となる \(i\) が存在しない.
-
\(A_i = x, A_j = x+1\) となる \((i, j) \ (i \lt j)\) が存在する.
よって, 条件を満たす \(A\) の個数は
\[\perm{N-1}{K} + \combi{K}{2} \cdot \perm{N-2}{K-2}\]となる. マス \(N\) にコマがあるための条件は \(A_i = N\) となるコマが存在しないことだけなので, 条件を満たす \(A\) の個数は
\[\perm{N-1}{K}\]である. よって得点は
\[\begin{align} & \sum_{x=1}^{N-1} x \cdot \left(\perm{N-1}{K} + \combi{K}{2} \cdot \perm{N-2}{K-2}\right) + N \cdot \perm{N-1}{k} \\ &= \frac{N(N+1)}{2} \perm{N-1}{K} + \frac{N(N-1)}{2} \combi{K}{2} \cdot \perm{N-2}{K-2} \end{align}\]となる. ただし, \(N == K\) のときは前者の条件は成り立たないので, 第二項だけが残る.