/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
正整数 N, K と、(1, 2, \dots, NK) の順列 P = (P_{1}, P_{2}, \dots, P_{NK}) が与えられます。
Alice は以下の操作を繰り返し、P を昇順ソートします。
- 1 以上 NK 以下の整数 i, j(i\neq j) を選び、P_{i} と P_{j} を入れ替える。このとき、|i - j| が N の倍数なら、Alice は 1 ポイントもらえる。
Alice は最小の操作回数で P を昇順ソートし、その上でもらえるポイントの和を最大化する行動をします。
Alice が得るポイントの和を出力してください。
制約
- 1\leq N\leq 500
- 1\leq K\leq 10
- (P_{1}, P_{2}, \dots , P_{NK}) は (1, 2, \dots, NK) の順列
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N K
P_{1} P_{2} \dots P_{NK}
出力
答えを出力してください。
入力例 1
3 2 1 6 5 3 2 4
出力例 1
2
例えば以下のように 4 回操作すると P を昇順ソートできます。
- (i, j) = (2, 5) として操作する。操作後、P = (1, 2, 5, 3, 6, 4) となる。
- (i, j) = (4, 6) として操作する。操作後、P = (1, 2, 5, 4, 6, 3) となる。
- (i, j) = (3, 5) として操作する。操作後、P = (1, 2, 6, 4, 5, 3) となる。
- (i, j) = (3, 6) として操作する。操作後、P = (1, 2, 3, 4, 5, 6) となる。
上記の 4 回の操作のうち、1 回目と 4 回目の操作で Alice はそれぞれ 1 ポイントもらえるため、Alice は合計で 2 ポイントもらえます。
このように操作することが最小の操作回数で P を昇順ソートし、その上でもらえるポイントの和を最大化する行動のひとつであるため、2 を出力します。
入力例 2
1 1 1
出力例 2
0
入力例 3
4 6 10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
出力例 3
7
Score : 800 points
Problem Statement
You are given positive integers N, K and a permutation P = (P_{1}, P_{2}, \dots, P_{NK}) of (1, 2, \dots, NK).
Alice repeatedly performs the following operation to sort P in ascending order.
- Choose integers i and j (i\neq j) where 1 \leq i, j \leq NK, and swap P_{i} and P_{j}. If |i - j| is a multiple of N, Alice gets 1 point.
Alice sorts P in ascending order with the minimum number of operations, and under that condition, she maximizes the sum of points she gets.
Output the sum of points Alice gets.
Constraints
- 1\leq N\leq 500
- 1\leq K\leq 10
- (P_{1}, P_{2}, \dots , P_{NK}) is a permutation of (1, 2, \dots, NK)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
P_{1} P_{2} \dots P_{NK}
Output
Output the answer.
Sample Input 1
3 2 1 6 5 3 2 4
Sample Output 1
2
For example, P can be sorted in ascending order with four operations as follows.
- Perform the operation with (i, j) = (2, 5). After the operation, P = (1, 2, 5, 3, 6, 4).
- Perform the operation with (i, j) = (4, 6). After the operation, P = (1, 2, 5, 4, 6, 3).
- Perform the operation with (i, j) = (3, 5). After the operation, P = (1, 2, 6, 4, 5, 3).
- Perform the operation with (i, j) = (3, 6). After the operation, P = (1, 2, 3, 4, 5, 6).
Among the above four operations, Alice gets 1 point from each of the 1st and 4th operations, so Alice gets a total of 2 points.
This sequence of operations is one of the ways to sort P in ascending order with the minimum number of operations and maximize the sum of points under that condition, so output 2.
Sample Input 2
1 1 1
Sample Output 2
0
Sample Input 3
4 6 10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
Sample Output 3
7