No.018 C

$p$ が素数で $p \geq NM$ なので, $a\ %\ p \neq 0$ であれば $G[i][j]$ はすべて相異なる. よって, $i$ 列目に座る人の集合は一意に特定できるので, 縦方向の移動距離も一意となる.

あとは横方向の移動距離の最小を求めることとなる.

これは, $i$ 列目に座る人の横方向の位置の一覧をソートして, 横方向の位置が小さい人から順に左から埋めていく方法で最小移動距離が求まる.

$a\ %\ p = 0$ のときは $x_0 \lt p$ ならば $x_i$ はすべて一致するので席替えの必要はない. $x_0 \geq p$ ならば $x_0$ だけが異なり, $x_0 \lt x_i$ であるので, $x_0$ を一番後ろに移動させるために $2(N-1)$ の移動が必要となる.