きままにものづくり

日々の気付いたことなんかを書いてます。

ARC018 C問題

問題


C: 席替え - AtCoder Regular Contest #018 | AtCoder

解法

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

計算量

 O(NM log NM)

コード

広告を非表示にする