AT_arc018_3 [ARC018C] 席替え

[problemUrl]: https://atcoder.jp/contests/arc018/tasks/arc018_3 僕の学校は各クラスの人数が非常に多い。 $ 1,000,000 $ 人で編成されるクラスもあるくらいだ。 僕のクラスも例外ではない。縦に $ N $ 行、横に $ M $ 列の長方形状に机が並んでいて、 $ N\ \times\ M $ 人の生徒が一人一つずつ、自分の机を持っている。 僕の学校は防災意識が高く、もしものときは教室の後ろの壁がはがれてそこから人が避難することができるようになっている。 このたび、避難時には成績のいい人から逃げることができるようにした方がいいという方針になった。というわけで、僕のクラスでは成績の良い人ほど教室の後ろの壁に近いところに座るように席替えをすることになった。 具体的に言うと、教室の一番前の行を第 $ 0 $ 行、 一番左の列を第 $ 0 $ 列として、第 $ i $ 行第 $ j $ 列の場所にある席のことを $ (i,\ j) $ 、そこに席替え後に座っている人の成績を $ G[i][j] $ とすると、ある $ 2 $ つの席 $ (a,\ b),\ (c,\ d) $ に対して $ a\ \gt\ c $ ならば $ b,\ d $ の値によらず $ G[a][b]\ \geq\ G[c][d] $ が常に成り立つように席替えをするということである。 生徒は任意の席へ移動することが可能だが、席替え後に $ 2 $ 人以上の人が同じ席にいたり、誰も座らない席があってはならない。もちろん、新しく机を増設したり、なくしたりして、 $ N $ 行 $ M $ 列の形を崩すことも許されない。 席替えをするのは良いが、あいにく人数が非常に大きいので席替えによる各生徒の移動距離の総和を最小限に抑えたい。このとき、生徒の移動距離というのは、移動前後の席の位置のマンハッタン距離である。つまり $ (a,\ b) $ から $ (c,\ d) $ に移動したのならば移動距離は $ |a\ -\ c|\ +\ |b\ -\ d| $ である。 席替え前の各席に座っている生徒の成績を与えるので、生徒の総移動距離の最小値を求めてほしい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ x_0 $ $ a $ $ p $ - $ 1 $ 行目には、教室の行の数、列の数をあらわす整数 $ N $ , $ M $ ( $ 1\ ≦\ N,\ M\ ≦\ 1,000 $ )が空白区切りで与えられる。 - $ 2 $ 行目には、各席に座っている生徒の成績のデータを生成する乱数の種 $ x_0 $ ( $ 0\ ≦\ x_0\ ≦\ 10^9 $ ), $ a $ ( $ 0\ ≦\ a\ ≦\ 10^9 $ ), $ p $ ( $ N\ \times\ M\ ≦\ p\ ≦\ 10^9 $ , $ p $ は常に素数)が空白区切りで与えられる。 br> 席の数が非常に多いため、席替え前の各席に座っている生徒の成績は上記の3つの変数を種に生成してもらう。 $ i\ \geq\ 1 $ について $ x_i\ =\ (x_{i-1}\ +\ a)\ mod\ p $ の漸化式で与えられる数列 $ x $ を考える。 $ (i,\ j) $ に席替え前に座っている生徒の成績は $ x_{i\ \times\ m\ +\ j} $ とする。 席替え時の各生徒の総移動距離の最小値を一行で出力せよ。 なお、出力の最後には改行を入れること。 ```

2 3
1 2 59
```

 ```
0
```

 席替え前の各席に座っている生徒の成績は以下のようになる。  
```
1  3  5
7  9 11
```

 どの席も自分より後ろ(画面では下)に、自分より成績の悪い人がいないので条件を満たしている。よって席替えの必要はない。 ```
2 3
6 55 59
```

 ```
2
```

 席替え前の各席に座っている生徒の成績は以下のようになる。  
```
 6  2 57
53 49 45
```

 $ (0,\ 2) $ と $ (1,\ 2) $ が席を交換すれば良い。共に $ 1 $ ずつの変化なので総移動距離は $ 2 $ である。 ```
4 5
15 25 79
```

 ```
26
```

 席替え前の各席に座っている生徒の成績は以下のようになる。  
```
15 40 65 11 36
61  7 32 57  3
28 53 78 24 49
74 20 45 70 16
```

 条件を満たす席替えの一例として以下のものがあげられる。  
```
15  7 16 11  3
28 20 32 24 36
53 40 45 57 49
74 61 65 70 78
```
                            

N/A

N/A