回答編集履歴
3
追記
test
CHANGED
|
@@ -1,3 +1,93 @@
|
|
|
1
|
+
追記2: Takahito_Ogawaさんにコメントいただき考えてみるとなるほど再帰的に最適解を求める考え方でよく、一度求めたa, pに関する最適解を複数回計算しなくてよいような論理が容易に組めることに気づけました。コメントありがとうございました。>Takahito_Ogawaさん
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
既にコードは複数上がっていて本質的には同じことだと思いますが、自分なりの「分かり易い」コードを書いてみました。例えばkichirb3さんのコードは再帰を必要としないコードですが、悲しいかなパっと見てすぐに腑に落ちなかった(^^;)ため自分なりに書いてみたわけです。
|
|
6
|
+
|
|
7
|
+
|
|
8
|
+
|
|
9
|
+
```Python
|
|
10
|
+
|
|
11
|
+
import math
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
debug_count = 0 # fを何回評価したかの計算量評価用カウンター
|
|
16
|
+
|
|
17
|
+
|
|
18
|
+
|
|
19
|
+
def f(a, p):
|
|
20
|
+
|
|
21
|
+
global debug_count
|
|
22
|
+
|
|
23
|
+
debug_count += 1
|
|
24
|
+
|
|
25
|
+
return int(math.floor(a * (100 + p) / 100))
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
def solve(a, p):
|
|
30
|
+
|
|
31
|
+
assert p > 0
|
|
32
|
+
|
|
33
|
+
best = {}
|
|
34
|
+
|
|
35
|
+
_count = debug_count
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
def inner(p):
|
|
40
|
+
|
|
41
|
+
# 既に(a, p)の最大値が計算済みなら単にそれを返す
|
|
42
|
+
|
|
43
|
+
if p in best:
|
|
44
|
+
|
|
45
|
+
return best[p]
|
|
46
|
+
|
|
47
|
+
# 最初に全てのポイントを一度につぎ込んだ場合を計算
|
|
48
|
+
|
|
49
|
+
max_a, max_ps = f(a, p), [p]
|
|
50
|
+
|
|
51
|
+
for i in range(1, p):
|
|
52
|
+
|
|
53
|
+
# p - iポイントをつぎ込んでからiポイントをつぎ込んだ場合を計算
|
|
54
|
+
|
|
55
|
+
# まずp - iポイントをつぎ込んだ場合の最大値・組み合わせを再帰で求め>る
|
|
56
|
+
|
|
57
|
+
pre_a, pre_ps = inner(p - i)
|
|
58
|
+
|
|
59
|
+
# その後iポイントをつぎ込んだ最終結果を求める
|
|
60
|
+
|
|
61
|
+
can_a = f(pre_a, i)
|
|
62
|
+
|
|
63
|
+
# 最大値の更新
|
|
64
|
+
|
|
65
|
+
if can_a > max_a:
|
|
66
|
+
|
|
67
|
+
max_a, max_ps = can_a, pre_ps + [i]
|
|
68
|
+
|
|
69
|
+
best[p] = max_a, max_ps
|
|
70
|
+
|
|
71
|
+
return best[p]
|
|
72
|
+
|
|
73
|
+
|
|
74
|
+
|
|
75
|
+
res = inner(p)
|
|
76
|
+
|
|
77
|
+
return res + (debug_count - _count,)
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
print(solve(70, 10)) # (77, [10], 55)
|
|
82
|
+
|
|
83
|
+
print(solve(10000, 10)) # (11045, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 55)
|
|
84
|
+
|
|
85
|
+
```
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
|
|
89
|
+
---
|
|
90
|
+
|
|
1
91
|
追記：Takahito_Ogawaさんの動的計画法をちゃんと理解できてませんが、同じポイントを消費する組み合わせのうち最大のもの以外を候補から手際よく削除しながらベストなものの探索空間を絞り込むというアプローチではないかと思いました。それに対して本回答は劣っていて単にgen_psを示すためだけのものでしかないです。
|
|
2
92
|
|
|
3
93
|
|
2
追記
test
CHANGED
|
@@ -1,3 +1,15 @@
|
|
|
1
|
+
追記：Takahito_Ogawaさんの動的計画法をちゃんと理解できてませんが、同じポイントを消費する組み合わせのうち最大のもの以外を候補から手際よく削除しながらベストなものの探索空間を絞り込むというアプローチではないかと思いました。それに対して本回答は劣っていて単にgen_psを示すためだけのものでしかないです。
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
なおポイント数11の最大値は10のときと同じなので1ポイントは無駄ということになり、無暗に組み合わせが増えているだけでありしらみつぶし探索のよくない特徴が浮き彫りになってますね。動的計画法であればこういう影響を受けず本質的に有効な組み合わせを早く求められるのではないかと思います。
|
|
6
|
+
|
|
7
|
+
|
|
8
|
+
|
|
9
|
+
---
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
1
13
|
> 足して10になる組み合わせを全て列挙してリスト化すると言うものですが、まず、それを列挙するアルゴリズムが思いつかない
|
|
2
14
|
|
|
3
15
|
|
1
追記
test
CHANGED
|
@@ -176,4 +176,4 @@
|
|
|
176
176
|
|
|
177
177
|
|
|
178
178
|
|
|
179
|
-
やってみるとポイントが10の場合はベストな組み合わせは2通り、11になると27通りになりました。
|
|
179
|
+
Aの初期値70についてやってみるとポイントが10の場合はベストな組み合わせは2通り、11になると27通りになりました。
|