回答編集履歴
5
誤字の修正
answer
CHANGED
|
@@ -65,7 +65,7 @@
|
|
|
65
65
|
|
|
66
66
|
このように動的計画法では部分問題の解についての漸化式を用いて、より少ない計算量で元の問題の解を求めることができます。今回の問題においては、部分問題の解について以下の漸化式が成立していると解釈することができます。
|
|
67
67
|
|
|
68
|
-
Problem(A_0, p_0) = max_(p=1, ..., p_0) Problem(
|
|
68
|
+
Problem(A_0, p_0) = max_(p=1, ..., p_0) Problem(A_0, p_0 - p)の最大価値 * (100 + p) / 100(小数点以下切り捨て)
|
|
69
69
|
|
|
70
70
|
```python
|
|
71
71
|
A_0 = 100
|
4
解法の解釈を追記
answer
CHANGED
|
@@ -63,6 +63,10 @@
|
|
|
63
63
|
|
|
64
64
|
なので、トータル(1 + 10) * (10 / 2) = 55回の計算で元の問題の解を求めることが可能です。
|
|
65
65
|
|
|
66
|
+
このように動的計画法では部分問題の解についての漸化式を用いて、より少ない計算量で元の問題の解を求めることができます。今回の問題においては、部分問題の解について以下の漸化式が成立していると解釈することができます。
|
|
67
|
+
|
|
68
|
+
Problem(A_0, p_0) = max_(p=1, ..., p_0) Problem(100, p_0 - p)の最大価値 * (100 + p) / 100(小数点以下切り捨て)
|
|
69
|
+
|
|
66
70
|
```python
|
|
67
71
|
A_0 = 100
|
|
68
72
|
p_0 = 10
|
3
動的計画法に基づくアルゴリズムの説明を追記
answer
CHANGED
|
@@ -1,3 +1,98 @@
|
|
|
1
|
+
動的計画法に基づくアルゴリズムだと、初期ポイントを`p_0`として`(p_0 + 1) * (p_0 / 2)`回の計算で解を求めることができます。以下で、動的計画法に基づくアルゴリズムの考え方を説明します。
|
|
2
|
+
|
|
3
|
+
例えば、初期価値を`A_0 = 100`、初期ポイントを`p_0 = 10`の場合の問題を考えましょう。この問題をProblem(100, 10)と書くことにします。
|
|
4
|
+
|
|
5
|
+
最後に何ポイント使うかによって場合分けすると、以下の10通り考えることができます。
|
|
6
|
+
|
|
7
|
+
ケース1. 最後に1ポイントだけ使う場合、直前には9ポイント残っている
|
|
8
|
+
ケース2. 最後に2ポイント使う場合、直前には8ポイント残っている
|
|
9
|
+
...
|
|
10
|
+
ケース10. 最後に10ポイント全部使う場合、直前には0ポイント残っている
|
|
11
|
+
|
|
12
|
+
実はこれらの問題は、元の問題の部分問題の解を用いて上手く解くことができます。どういうことか見ていきましょう。
|
|
13
|
+
|
|
14
|
+
例えば、ケース2の場合の最適解は、直前の8ポイントの最適な使い方がわかっていれば実は簡単に求められます。つまり、初期価値を`A_0 = 100`、初期ポイントを`p_0 = 8`とした問題Problem(100, 8)の解がわかっていれば、ケース2の場合の最適解は、
|
|
15
|
+
|
|
16
|
+
ケース2の最適解 = Problem(100, 8)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
|
|
17
|
+
|
|
18
|
+
として求められます。
|
|
19
|
+
|
|
20
|
+
同様に、ケース1からケース10までの解はそれぞれ、
|
|
21
|
+
|
|
22
|
+
ケース1の最適解 = Problem(100, 9)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
|
|
23
|
+
ケース2の最適解 = Problem(100, 8)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
|
|
24
|
+
...
|
|
25
|
+
ケース10の最適解 = Problem(100, 0)の最大価値 * (100 + 10) / 100(小数点以下切り捨て)
|
|
26
|
+
|
|
27
|
+
となります。
|
|
28
|
+
ここで、ケース10の最適解で現れるProblem(100, 0)の最大価値は、明らかに100であることに注意してください。なぜなら、Problem(100, 0)は初期価値100で与えられたポイントが0だからです。
|
|
29
|
+
|
|
30
|
+
元の問題Problem(100, 10)の解は、ケース1からケース10の最適解のうち最も大きい価値を取るものになります。
|
|
31
|
+
|
|
32
|
+
このように、元の問題はより少ないポイントしか使えない状況下での最適解（部分問題の最適解）を用いて容易に計算できます。これを素朴に再帰を用いて実装したコードが一番下に書いてあるコードになります。
|
|
33
|
+
|
|
34
|
+
一方で、再帰を用いずにループだけで実装することも可能です。ループだけで実装する場合は、次のように考えるとよいです。
|
|
35
|
+
|
|
36
|
+
まず、Problem(100, 0)の解は上でも述べたように100であることは自明ですね。
|
|
37
|
+
次に、Problem(100, 1)の解はProblem(100, 0)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)で計算できます。
|
|
38
|
+
次に、Problem(100, 2)の解は
|
|
39
|
+
|
|
40
|
+
最後に1ポイント使う場合： Problem(100, 1)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
|
|
41
|
+
最後に2ポイント使う場合： Problem(100, 0)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
|
|
42
|
+
|
|
43
|
+
のうち価値がより大きくなる方です。ただし、Problem(100, 1)の最大価値とProblem(100, 0)の最大価値はすでに求まっていることに注意してください。
|
|
44
|
+
|
|
45
|
+
次に、Problem(100, 3)の解は
|
|
46
|
+
|
|
47
|
+
最後に1ポイント使う場合： Problem(100, 2)の最大価値 * (100 + 1) / 100(小数点以下切り捨て)
|
|
48
|
+
最後に2ポイント使う場合： Problem(100, 1)の最大価値 * (100 + 2) / 100(小数点以下切り捨て)
|
|
49
|
+
最後に3ポイント使う場合： Problem(100, 0)の最大価値 * (100 + 3) / 100(小数点以下切り捨て)
|
|
50
|
+
|
|
51
|
+
のうち価値が最も大きくなるものです。ただし、Problem(100, 2)の最大価値とProblem(100, 1)の最大価値とProblem(100, 0)の最大価値はすでに求まっていることに注意してください。
|
|
52
|
+
|
|
53
|
+
このように与えられたポイントが小さい部分問題から順に解を求めていくことで単純なループで元の問題の解を求めることが可能です。
|
|
54
|
+
ループのみ再帰なしの実装を下に挙げます。
|
|
55
|
+
|
|
56
|
+
必要な計算回数はそれぞれ次のようになります。
|
|
57
|
+
|
|
58
|
+
Problem(100, 1)： 1回
|
|
59
|
+
Problem(100, 2)： 2回
|
|
60
|
+
Problem(100, 3)： 3回
|
|
61
|
+
...
|
|
62
|
+
Problem(100, 10): 10回
|
|
63
|
+
|
|
64
|
+
なので、トータル(1 + 10) * (10 / 2) = 55回の計算で元の問題の解を求めることが可能です。
|
|
65
|
+
|
|
66
|
+
```python
|
|
67
|
+
A_0 = 100
|
|
68
|
+
p_0 = 10
|
|
69
|
+
|
|
70
|
+
|
|
71
|
+
def solve(A_0, p_0):
|
|
72
|
+
# Subproblem of this problem is defined by A_0 and p_0, each corresponds to
|
|
73
|
+
# the initial value of some object and the points given initially.
|
|
74
|
+
# Variable `solutions` holds the optimal values of subproblems as a dictionary.
|
|
75
|
+
# The solution of the subproblem with (A_0, 0) is apparent, that is A_0.
|
|
76
|
+
solutions = {(A_0, 0): A_0}
|
|
77
|
+
for p_0 in range(1, p_0 + 1):
|
|
78
|
+
# Solve the subproblem with (A_0, p_0), p_0 begins with 1
|
|
79
|
+
# and ends with p_0 given to the function `solve`.
|
|
80
|
+
max_A = A_0
|
|
81
|
+
for point_to_be_used in range(1, p_0 + 1):
|
|
82
|
+
# case division with the points to be used in the last time.
|
|
83
|
+
A = solutions[(A_0, p_0 - point_to_be_used)] * (100 + point_to_be_used) // 100
|
|
84
|
+
if A > max_A:
|
|
85
|
+
max_A = A
|
|
86
|
+
# add solution of the subproblem with (A_0, p_0)
|
|
87
|
+
solutions.update({(A_0, p_0): max_A})
|
|
88
|
+
return solutions[(A_0, p_0)]
|
|
89
|
+
|
|
90
|
+
print(solve(A_0, p_0))
|
|
91
|
+
```
|
|
92
|
+
|
|
93
|
+
---
|
|
94
|
+
以下、更新前の再帰に基づく実装です。
|
|
95
|
+
|
|
1
96
|
kichirb3さんの「小数点以下切り捨て」についての指摘を受けて改めて考え直した結果、解析的に閉じた形で解を求めることが難しいと思いました。
|
|
2
97
|
|
|
3
98
|
しかし、2^Nより効率の良いアルゴリズムを実装することは可能です。
|
2
計算量を追記
answer
CHANGED
|
@@ -7,7 +7,7 @@
|
|
|
7
7
|
A_0やp_0を大きくして実行しても非常に高速に実行可能で、スケールします。
|
|
8
8
|
ただし、p_0をかなり大きくした場合には、Maximum Recursion Error（最大再帰呼び出し数の上限を超える）が発生しますが、pythonの再帰の上限を変更すればエラーは起こりません。
|
|
9
9
|
説明や計算量や補足については後ほど時間があるときに追記します。
|
|
10
|
-
計算量はちゃんと確認していませんが、多分O(p_0)です。計算時間がp_0にだいたい比例
|
|
10
|
+
計算量はちゃんと確認していませんが、多分O(p_0^2)です。計算時間がp_0^2にだいたい比例するということです。
|
|
11
11
|
|
|
12
12
|
```python
|
|
13
13
|
from math import floor
|
1
計算量を追記
answer
CHANGED
|
@@ -7,6 +7,7 @@
|
|
|
7
7
|
A_0やp_0を大きくして実行しても非常に高速に実行可能で、スケールします。
|
|
8
8
|
ただし、p_0をかなり大きくした場合には、Maximum Recursion Error（最大再帰呼び出し数の上限を超える）が発生しますが、pythonの再帰の上限を変更すればエラーは起こりません。
|
|
9
9
|
説明や計算量や補足については後ほど時間があるときに追記します。
|
|
10
|
+
計算量はちゃんと確認していませんが、多分O(p_0)です。計算時間がp_0にだいたい比例します。
|
|
10
11
|
|
|
11
12
|
```python
|
|
12
13
|
from math import floor
|