回答編集履歴
6
コード修正
test
CHANGED
|
@@ -6,9 +6,11 @@
|
|
|
6
6
|
lst = np.array(lst)
|
|
7
7
|
L = len(lst)
|
|
8
8
|
|
|
9
|
-
#
|
|
9
|
+
# リング上の選手の「位置」と「値（強さ）」
|
|
10
10
|
# 強さの昇順で並びをキープする
|
|
11
|
+
# 配列サイズは固定で最大分を用意
|
|
11
|
-
idxs
|
|
12
|
+
idxs = np.zeros(L,dtype=int)
|
|
13
|
+
vals = np.zeros(L,dtype=int)
|
|
12
14
|
|
|
13
15
|
ret = np.zeros(L,dtype=int) # 各選手の防衛回数
|
|
14
16
|
|
|
@@ -18,26 +20,33 @@
|
|
|
18
20
|
ret[idxs] = idxs - idx - 1 # 各選手の位置 - 挑戦者の位置 - 1
|
|
19
21
|
|
|
20
22
|
# 逆順にリングに上がる
|
|
23
|
+
count = 0 # リング上にいる選手の数
|
|
21
24
|
for i in range(L):
|
|
22
25
|
|
|
23
26
|
# 挑戦者
|
|
24
27
|
idx = L-i-1
|
|
25
28
|
val = lst[idx]
|
|
26
29
|
|
|
30
|
+
st = L-count # リング上にいる先頭（最弱）選手の位置
|
|
31
|
+
|
|
27
32
|
# リング上にいる選手内での挑戦者のランク（位置）を決定
|
|
28
33
|
# searchsortedはバイナリサーチなので速いはず
|
|
34
|
+
p = 0
|
|
35
|
+
if count > 0:
|
|
29
|
-
p = np.searchsorted(vals, val, side='right')
|
|
36
|
+
p = np.searchsorted(vals[-count:], val, side='right')
|
|
30
37
|
|
|
31
38
|
# pより手前にいる選手は挑戦者以下なのでリングから脱落
|
|
32
39
|
# 脱落者の防衛回数を算出
|
|
33
|
-
calc_ret(idxs[
|
|
40
|
+
calc_ret(idxs[st:st+p], idx)
|
|
34
41
|
|
|
35
42
|
# この時点で挑戦者は最弱なので先頭に追加
|
|
43
|
+
count = count - p + 1
|
|
44
|
+
st = L-count
|
|
36
|
-
idxs
|
|
45
|
+
idxs[st] = idx
|
|
37
|
-
vals
|
|
46
|
+
vals[st] = val
|
|
38
47
|
|
|
39
48
|
# 最後に生き残った選手の防衛回数を算出
|
|
40
|
-
calc_ret(idxs, -1)
|
|
49
|
+
calc_ret(idxs[-count:], -1)
|
|
41
50
|
|
|
42
51
|
return ret.tolist()
|
|
43
52
|
|
5
コード修正
test
CHANGED
|
@@ -14,8 +14,8 @@
|
|
|
14
14
|
|
|
15
15
|
# 防衛回数の算出
|
|
16
16
|
def calc_ret(idxs, idx):
|
|
17
|
-
f
|
|
17
|
+
if idxs.shape[0] > 0:
|
|
18
|
-
ret[i] = i - idx - 1 #
|
|
18
|
+
ret[idxs] = idxs - idx - 1 # 各選手の位置 - 挑戦者の位置 - 1
|
|
19
19
|
|
|
20
20
|
# 逆順にリングに上がる
|
|
21
21
|
for i in range(L):
|
4
修正
test
CHANGED
|
@@ -1,5 +1,4 @@
|
|
|
1
|
-
numpy
|
|
1
|
+
いわば勝ち残り戦での防衛回数を求める問題と考え、numpyにて実装しました。
|
|
2
|
-
たぶん想定通りの結果が出せていると思います。
|
|
3
2
|
```Python
|
|
4
3
|
import numpy as np
|
|
5
4
|
|
|
@@ -7,40 +6,60 @@
|
|
|
7
6
|
lst = np.array(lst)
|
|
8
7
|
L = len(lst)
|
|
9
8
|
|
|
10
|
-
# 手
|
|
9
|
+
# 勝ち残った選手の「位置」と「値（強さ）」
|
|
10
|
+
# 強さの昇順で並びをキープする
|
|
11
11
|
idxs, vals = np.array([],dtype=int), np.array([],dtype=int)
|
|
12
12
|
|
|
13
|
-
ret = np.zeros(L,dtype=int) #
|
|
13
|
+
ret = np.zeros(L,dtype=int) # 各選手の防衛回数
|
|
14
14
|
|
|
15
|
+
# 防衛回数の算出
|
|
16
|
+
def calc_ret(idxs, idx):
|
|
17
|
+
for i in idxs:
|
|
18
|
+
ret[i] = i - idx - 1 # idx=挑戦者の位置
|
|
19
|
+
|
|
15
|
-
# 逆順に
|
|
20
|
+
# 逆順にリングに上がる
|
|
16
21
|
for i in range(L):
|
|
17
22
|
|
|
18
|
-
#
|
|
23
|
+
# 挑戦者
|
|
19
24
|
idx = L-i-1
|
|
20
25
|
val = lst[idx]
|
|
21
26
|
|
|
22
|
-
#
|
|
27
|
+
# リング上にいる選手内での挑戦者のランク（位置）を決定
|
|
23
28
|
# searchsortedはバイナリサーチなので速いはず
|
|
24
29
|
p = np.searchsorted(vals, val, side='right')
|
|
25
30
|
|
|
26
|
-
#
|
|
31
|
+
# pより手前にいる選手は挑戦者以下なのでリングから脱落
|
|
32
|
+
# 脱落者の防衛回数を算出
|
|
27
|
-
re
|
|
33
|
+
calc_ret(idxs[0:p], idx)
|
|
28
|
-
if remain.shape[0] > 0:
|
|
29
|
-
ret[remain] += 1
|
|
30
34
|
|
|
31
|
-
#
|
|
35
|
+
# この時点で挑戦者は最弱なので先頭に追加
|
|
32
36
|
idxs = np.insert( idxs[p:], 0, idx)
|
|
33
37
|
vals = np.insert( vals[p:], 0, val)
|
|
34
38
|
|
|
39
|
+
# 最後に生き残った選手の防衛回数を算出
|
|
35
|
-
ret
|
|
40
|
+
calc_ret(idxs, -1)
|
|
36
41
|
|
|
42
|
+
return ret.tolist()
|
|
43
|
+
|
|
44
|
+
|
|
45
|
+
N = 100000
|
|
46
|
+
for lst in [np.random.randint(1,N,N),
|
|
47
|
+
np.arange(1,N),
|
|
37
|
-
|
|
48
|
+
np.array([48, 20, 3, 15, 13, 32, 7, 27, 85, 48]),
|
|
49
|
+
np.array([1,1,2,3])]:
|
|
50
|
+
|
|
51
|
+
lst = lst.tolist()
|
|
52
|
+
print('-----')
|
|
38
53
|
print(lst)
|
|
39
|
-
ret = calc(lst)
|
|
54
|
+
ret1 = calc(lst)
|
|
40
|
-
print(ret)
|
|
55
|
+
print(ret1)
|
|
41
56
|
|
|
57
|
+
"""
|
|
58
|
+
-----
|
|
42
|
-
|
|
59
|
+
[48, 20, 3, 15, 13, 32, 7, 27, 85, 48]
|
|
43
|
-
|
|
60
|
+
[0, 0, 0, 1, 0, 4, 0, 1, 8, 0]
|
|
61
|
+
-----
|
|
44
|
-
|
|
62
|
+
[1, 1, 2, 3]
|
|
45
|
-
|
|
63
|
+
[0, 0, 2, 3]
|
|
64
|
+
"""
|
|
46
65
|
```
|
3
コメント修正。やっぱり最初のコメントが正しかった…
test
CHANGED
|
@@ -23,12 +23,12 @@
|
|
|
23
23
|
# searchsortedはバイナリサーチなので速いはず
|
|
24
24
|
p = np.searchsorted(vals, val, side='right')
|
|
25
25
|
|
|
26
|
-
# [p:]以降はまだ手前の行より
|
|
26
|
+
# [p:]以降はまだ手前の行より大きいので＋１
|
|
27
27
|
remain = idxs[p:]
|
|
28
28
|
if remain.shape[0] > 0:
|
|
29
29
|
ret[remain] += 1
|
|
30
30
|
|
|
31
|
-
# [0:p]は現在行以
|
|
31
|
+
# [0:p]は現在行以下の値なので捨てて、先頭にこの値を追加
|
|
32
32
|
idxs = np.insert( idxs[p:], 0, idx)
|
|
33
33
|
vals = np.insert( vals[p:], 0, val)
|
|
34
34
|
|
2
修正
test
CHANGED
|
@@ -3,34 +3,44 @@
|
|
|
3
3
|
```Python
|
|
4
4
|
import numpy as np
|
|
5
5
|
|
|
6
|
-
lst
|
|
6
|
+
def calc(lst):
|
|
7
|
-
lst = np.array(lst)
|
|
7
|
+
lst = np.array(lst)
|
|
8
|
-
L = len(lst)
|
|
8
|
+
L = len(lst)
|
|
9
9
|
|
|
10
|
-
# 手前の行より大きい要素の「要素位置」と「値」のリスト
|
|
10
|
+
# 手前の行より大きい要素の「要素位置」と「値」のリスト
|
|
11
|
-
idxs, vals = np.array([],dtype=int), np.array([],dtype=int)
|
|
11
|
+
idxs, vals = np.array([],dtype=int), np.array([],dtype=int)
|
|
12
12
|
|
|
13
|
-
ret = np.zeros(L,dtype=int) # 連続回数
|
|
13
|
+
ret = np.zeros(L,dtype=int) # 連続回数
|
|
14
14
|
|
|
15
|
-
# 逆順に走査
|
|
15
|
+
# 逆順に走査
|
|
16
|
-
for i in range(L):
|
|
16
|
+
for i in range(L):
|
|
17
17
|
|
|
18
|
-
# 現在の要素位置と値
|
|
18
|
+
# 現在の要素位置と値
|
|
19
|
-
idx = L-i-1
|
|
19
|
+
idx = L-i-1
|
|
20
|
-
val = lst[idx]
|
|
20
|
+
val = lst[idx]
|
|
21
21
|
|
|
22
|
-
# 値の挿入位置（この値より大きいもの）の位置
|
|
22
|
+
# 値の挿入位置（この値より大きいもの）の位置
|
|
23
|
-
# searchsortedはバイナリサーチなので速いはず
|
|
23
|
+
# searchsortedはバイナリサーチなので速いはず
|
|
24
|
-
p = np.searchsorted(vals, val)
|
|
24
|
+
p = np.searchsorted(vals, val, side='right')
|
|
25
25
|
|
|
26
|
-
# [p:]以降はまだ手前の行より
|
|
26
|
+
# [p:]以降はまだ手前の行より小さいので＋１
|
|
27
|
-
remain = idxs[p:]
|
|
27
|
+
remain = idxs[p:]
|
|
28
|
-
if remain.shape[0] > 0:
|
|
28
|
+
if remain.shape[0] > 0:
|
|
29
|
-
ret[remain] += 1
|
|
29
|
+
ret[remain] += 1
|
|
30
30
|
|
|
31
|
-
# [0:p]は現在行以
|
|
31
|
+
# [0:p]は現在行以上の値なので捨てて、先頭にこの値を追加
|
|
32
|
-
idxs = np.insert( idxs[p:], 0, idx)
|
|
32
|
+
idxs = np.insert( idxs[p:], 0, idx)
|
|
33
|
-
vals = np.insert( vals[p:], 0, val)
|
|
33
|
+
vals = np.insert( vals[p:], 0, val)
|
|
34
34
|
|
|
35
|
+
return ret
|
|
36
|
+
|
|
37
|
+
for lst in [[48,20,3,15,13,32,7,27,85,48],[1,1,2,3]]:
|
|
38
|
+
print(lst)
|
|
39
|
+
ret = calc(lst)
|
|
40
|
+
print(ret)
|
|
41
|
+
|
|
42
|
+
#[48, 20, 3, 15, 13, 32, 7, 27, 85, 48]
|
|
35
|
-
|
|
43
|
+
#[0 0 0 1 0 4 0 1 8 0]
|
|
44
|
+
#[1, 1, 2, 3]
|
|
45
|
+
#[0 0 2 3]
|
|
36
46
|
```
|
1
修正
test
CHANGED
|
@@ -23,12 +23,12 @@
|
|
|
23
23
|
# searchsortedはバイナリサーチなので速いはず
|
|
24
24
|
p = np.searchsorted(vals, val)
|
|
25
25
|
|
|
26
|
-
# [p:]以降はまだ手前の行より
|
|
26
|
+
# [p:]以降はまだ手前の行より大きいので＋１
|
|
27
27
|
remain = idxs[p:]
|
|
28
28
|
if remain.shape[0] > 0:
|
|
29
29
|
ret[remain] += 1
|
|
30
30
|
|
|
31
|
-
# [0:p]は現在行以
|
|
31
|
+
# [0:p]は現在行以下の値なので捨てて、先頭にこの値を追加
|
|
32
32
|
idxs = np.insert( idxs[p:], 0, idx)
|
|
33
33
|
vals = np.insert( vals[p:], 0, val)
|
|
34
34
|
|