回答編集履歴
4
テキスト修正
test
CHANGED
|
@@ -82,7 +82,17 @@
|
|
|
82
82
|
|
|
83
83
|
```
|
|
84
84
|
|
|
85
|
+
を作り、この配列を各要素の先頭の値で昇順ソートすると以下が得られます。
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
|
|
89
|
+
```
|
|
90
|
+
|
|
91
|
+
[ [10, 3], [20, 2], [30, 1], [40, 0] ]
|
|
92
|
+
|
|
93
|
+
```
|
|
94
|
+
|
|
85
|
-
|
|
95
|
+
上記の配列を使うと、各要素の移動量の計算は、各要素の配列の二番目に入っているソート前のインデクスと、ソート後の配列の各要素それ自体のインデクスの差から求めることができます。以下はこの考え方による `f(lst)` です。
|
|
86
96
|
|
|
87
97
|
|
|
88
98
|
|
3
テキスト修正
test
CHANGED
|
@@ -40,7 +40,7 @@
|
|
|
40
40
|
|
|
41
41
|
|
|
42
42
|
|
|
43
|
-
### 追記
|
|
43
|
+
### 追記1
|
|
44
44
|
|
|
45
45
|
|
|
46
46
|
|
|
@@ -63,3 +63,41 @@
|
|
|
63
63
|
```
|
|
64
64
|
|
|
65
65
|
によっても得られます。
|
|
66
|
+
|
|
67
|
+
|
|
68
|
+
|
|
69
|
+
### 追記2
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
別案を挙げます。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
与えられた配列 `lst` が例えば `[40, 30, 20, 10]` だった場合に、この配列のコピーをソートするのではなく、`lst` の要素とインデクスを並べた、長さ2の配列を要素とする配列
|
|
78
|
+
|
|
79
|
+
```
|
|
80
|
+
|
|
81
|
+
[ [40, 0], [30, 1], [20, 2], [10, 3] ]
|
|
82
|
+
|
|
83
|
+
```
|
|
84
|
+
|
|
85
|
+
を作り、この配列を各要素の先頭の値で昇順ソートすると、各要素の移動量の計算は、各要素の配列の二番目に入っている、ソート前のインデクスと、ソート後のインデクスの差から求めることができます。以下はこの考え方による `f(lst)` です。
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
|
|
89
|
+
```javascript
|
|
90
|
+
|
|
91
|
+
const f = lst =>
|
|
92
|
+
|
|
93
|
+
lst.map((v, i) => [v, i])
|
|
94
|
+
|
|
95
|
+
.sort(([v1],[v2]) => v1 - v2)
|
|
96
|
+
|
|
97
|
+
.reduce((s, [v, i], j) => s + Math.abs(i-j), 0);
|
|
98
|
+
|
|
99
|
+
```
|
|
100
|
+
|
|
101
|
+
|
|
102
|
+
|
|
103
|
+
- **動作確認用サンプル:** [https://codepen.io/jun68ykt/pen/oNbQjgv](https://codepen.io/jun68ykt/pen/oNbQjgv?editors=0012)
|
2
テキスト修正
test
CHANGED
|
@@ -37,3 +37,29 @@
|
|
|
37
37
|
|
|
38
38
|
|
|
39
39
|
- **動作確認用サンプル:** [https://codepen.io/jun68ykt/pen/pogxBGy](https://codepen.io/jun68ykt/pen/pogxBGy?editors=0012)
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
### 追記
|
|
44
|
+
|
|
45
|
+
|
|
46
|
+
|
|
47
|
+
上記の回答コードでは、引数で与えられた `lst`(のコピー)をソートした `lstSorted` を得るために javascript標準の sort メソッドを使って
|
|
48
|
+
|
|
49
|
+
```javascript
|
|
50
|
+
|
|
51
|
+
const lstSorted = [...lst].sort((v1, v2) => v1 - v2);
|
|
52
|
+
|
|
53
|
+
```
|
|
54
|
+
|
|
55
|
+
としていますが、Q3fdxrGzWzu0u5nさんが自作されたquicksortを使えば、以下の二行
|
|
56
|
+
|
|
57
|
+
```javascript
|
|
58
|
+
|
|
59
|
+
const lstSorted = [...lst];
|
|
60
|
+
|
|
61
|
+
quicksort(lstSorted, 0, lstSorted.length -1)
|
|
62
|
+
|
|
63
|
+
```
|
|
64
|
+
|
|
65
|
+
によっても得られます。
|
1
テキスト修正
test
CHANGED
|
@@ -12,15 +12,15 @@
|
|
|
12
12
|
|
|
13
13
|
|
|
14
14
|
|
|
15
|
-
const lst
|
|
15
|
+
const lstSorted = [...lst].sort((v1, v2) => v1 - v2);
|
|
16
16
|
|
|
17
17
|
|
|
18
18
|
|
|
19
19
|
const sum = lst.reduce((s, v, i) => {
|
|
20
20
|
|
|
21
|
-
const j = lst
|
|
21
|
+
const j = lstSorted.indexOf(v);
|
|
22
22
|
|
|
23
|
-
lst
|
|
23
|
+
lstSorted[j] = NaN;
|
|
24
24
|
|
|
25
25
|
return s + Math.abs(i - j);
|
|
26
26
|
|