ARC018 C問題
解法
pは常に素数であり、N*M以上なのでa mod pが0でない限り、全ての値が異なるものになる。a mod pが0である場合は、x0が他の値と同じなら0を、そうでないなら2*(N-1)を返す。
全ての値が異なる場合は、値をソートしM個ずつ取り出すことで移動距離が計算できる。M個の点の移動距離の最小値は貪欲法で解ける。jの値が小さい順に左から割り当てていく。
計算量
pは常に素数であり、N*M以上なのでa mod pが0でない限り、全ての値が異なるものになる。a mod pが0である場合は、x0が他の値と同じなら0を、そうでないなら2*(N-1)を返す。
全ての値が異なる場合は、値をソートしM個ずつ取り出すことで移動距離が計算できる。M個の点の移動距離の最小値は貪欲法で解ける。jの値が小さい順に左から割り当てていく。