回答編集履歴
9
動的計画法の簡単な解説追加
test
CHANGED
|
@@ -54,3 +54,24 @@
|
|
|
54
54
|
23 298
|
|
55
55
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
56
56
|
```
|
|
57
|
+
|
|
58
|
+
---
|
|
59
|
+
|
|
60
|
+
私のコードはいろいろ削ぎ落して分かりづらくなっているので、「部分和問題」で検索して見つかるコード・解説で学ぶことをお勧めします。
|
|
61
|
+
動的計画法の解説は、表を使わないと厳しいので、ここの回答欄だと限界があります。
|
|
62
|
+
|
|
63
|
+
無理を承知で簡単に解説すると、以下のようになります。
|
|
64
|
+
|
|
65
|
+
まず、`dp`の意味ですが、`for n in c:`のループを何回回ったかにより変わってきます。
|
|
66
|
+
ループを`j`回回った時点で`dp[i]`が`True`ならば「`c`の先頭`j`枚のカードからいくつか選んで、合計が`i`となるようにする方法がある」という意味となります。
|
|
67
|
+
|
|
68
|
+
初期状態(ループを0回回った時点)では、カードを1枚も使えないので、作ることが可能な合計は0しかありません。そのため、`dp[0]`のみ`True`で、それ以外は`False`になるように`dp`を初期化しています。
|
|
69
|
+
|
|
70
|
+
終了状態(ループを`a`回回った時点)では、すべてのカードを使える場合の結果が求まっています。そのため、`dp[b]`が`True`なら、合計が`b`になるようにする方法がある、ということになります。(`dp`の長さが`b+1`なので、`dp[b]`と`dp[-1]`は同じ)
|
|
71
|
+
|
|
72
|
+
さて、肝心なループの中身についてですが、外側のループを`j-1`回回った時点で`dp[i]`が`True`、つまり先頭`j-1`枚のカードで合計`i`にできるなら、`j`回目のループ、つまり先頭`j`枚のカードが使える場合に以下のことが言えます。
|
|
73
|
+
1. 合計を`i`にする方法がある(`j`枚目のカードを使わなければよい)
|
|
74
|
+
2. 合計を`i + n`にする方法がある(`j-1`枚のカードで合計`i`にしたうえで、`j`枚目のカード`n`を使う)
|
|
75
|
+
この2.の場合を反映するのが、一番内側のif文になります。なお、1.については、`dp`を上書きしているので何もしなくても反映されます。
|
|
76
|
+
|
|
77
|
+
あとは内側のループが逆順となっている理由ですが、小さい順に処理してしまうと、`dp[i+n]=True`にて`True`にした(=合計を`i+n`にするのに`j`枚目のカードを使用済み)値を、同じループ内で再度拾ってしまうので、`j`枚目のカードが複数回使われてしまうためです。
|
8
文言変更
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
|
|
5
5
|
> どちらのコードでも1100ms強の実行時間がかかってしまいました．
|
|
6
6
|
|
|
7
|
-
AtCoderでは、時間がかかるコードは途中で強制終了されます。1100msで実行が終わったわけではなく、1100msで強制終了されただけですので、
|
|
7
|
+
AtCoderでは、時間がかかるコードは途中で強制終了されます。1100msで実行が終わったわけではなく、1100msで強制終了されただけですので、実行時間の数字自体には意味はありません。
|
|
8
8
|
|
|
9
9
|
> 全探索ではなく二分探索を行う
|
|
10
10
|
|
|
@@ -24,7 +24,7 @@
|
|
|
24
24
|
print("Yes" if dp[-1] else "No")
|
|
25
25
|
```
|
|
26
26
|
|
|
27
|
-
2.4節までの知識で解く場合でも、
|
|
27
|
+
2.4節までの知識で解く場合でも、和をすべてsetなどに集めてから検索するのではなく、その場で和が目的の値か判定したほうが速くなりそうです。
|
|
28
28
|
```python
|
|
29
29
|
import itertools
|
|
30
30
|
import sys
|
|
@@ -35,8 +35,8 @@
|
|
|
35
35
|
for n in range(a,0,-1):
|
|
36
36
|
for combi in itertools.combinations(c, n):
|
|
37
37
|
if sum(combi) == b:
|
|
38
|
-
|
|
38
|
+
print("Yes")
|
|
39
|
-
|
|
39
|
+
exit()
|
|
40
40
|
print("No")
|
|
41
41
|
```
|
|
42
42
|
|
|
@@ -49,7 +49,7 @@
|
|
|
49
49
|
23 277
|
|
50
50
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
|
51
51
|
```
|
|
52
|
-
対策されてしまったので、もう少し
|
|
52
|
+
対策されてしまったので、もう少し意地悪な例を挙げておきます。
|
|
53
53
|
```text
|
|
54
54
|
23 298
|
|
55
55
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
7
時間がかかる条件追加
test
CHANGED
|
@@ -44,7 +44,7 @@
|
|
|
44
44
|
|
|
45
45
|
---
|
|
46
46
|
|
|
47
|
-
他の方の回答にあるように、メモ化せずに再帰を使った場合、
|
|
47
|
+
他の方の回答にあるように、メモ化せずに再帰を使った場合、特定の条件で時間がかかるという問題があります(カードの枚数が多め、目標とする合計が大きめ(全カードの合計付近)、答えがNo)。手元の環境だと、カード枚数23枚で1秒を超えました。
|
|
48
48
|
```text
|
|
49
49
|
23 277
|
|
50
50
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
6
対策の対策
test
CHANGED
|
@@ -49,3 +49,8 @@
|
|
|
49
49
|
23 277
|
|
50
50
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
|
51
51
|
```
|
|
52
|
+
対策されてしまったので、もう少しひねくれた例を挙げておきます。
|
|
53
|
+
```text
|
|
54
|
+
23 298
|
|
55
|
+
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
56
|
+
```
|
5
返信を上にまとめる
test
CHANGED
|
@@ -1,11 +1,14 @@
|
|
|
1
1
|
> 満点の条件である実行時間で1000msが切れませんでした．
|
|
2
2
|
|
|
3
|
-
問題の「注意」にも書いてありますが、この問題は2.4節までの知識(全探索)で解いても1000msを切れません。
|
|
3
|
+
問題の「注意」にも書いてありますが、この問題は2.4節までの知識(全探索)で解いても1000msを切れません。3.7節の知識(動的計画法)で解いて、初めて1000msを切れるようになっています。
|
|
4
|
-
3.7節の知識(動的計画法)で解いて、初めて1000msを切れるようになっています。
|
|
5
4
|
|
|
6
5
|
> どちらのコードでも1100ms強の実行時間がかかってしまいました．
|
|
7
6
|
|
|
8
7
|
AtCoderでは、時間がかかるコードは途中で強制終了されます。1100msで実行が終わったわけではなく、1100msで強制終了されただけですので、多少高速化したぐらいでは1000msを切ることはできません。
|
|
8
|
+
|
|
9
|
+
> 全探索ではなく二分探索を行う
|
|
10
|
+
|
|
11
|
+
ソートしてから1回だけしか二分探索しない場合、普通に検索するよりかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|
|
9
12
|
|
|
10
13
|
---
|
|
11
14
|
|
|
@@ -41,10 +44,6 @@
|
|
|
41
44
|
|
|
42
45
|
---
|
|
43
46
|
|
|
44
|
-
ちなみに、ソートしてから1回だけしか二分探索しない場合、普通に検索するよりかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|
|
45
|
-
|
|
46
|
-
---
|
|
47
|
-
|
|
48
47
|
他の方の回答にあるように、メモ化せずに再帰を使った場合、カードの枚数が多めで答えがNoだと時間がかかるという問題があります。手元の環境だと、カード枚数23枚で1秒を超えました。
|
|
49
48
|
```text
|
|
50
49
|
23 277
|
4
再帰だとTLEの可能性があるので追記、整形
test
CHANGED
|
@@ -1,5 +1,13 @@
|
|
|
1
|
+
> 満点の条件である実行時間で1000msが切れませんでした．
|
|
2
|
+
|
|
1
|
-
問題の「注意」にも書いてありますが、この問題は2.4節までの知識(全探索)で解いても
|
|
3
|
+
問題の「注意」にも書いてありますが、この問題は2.4節までの知識(全探索)で解いても1000msを切れません。
|
|
2
|
-
3.
|
|
4
|
+
3.7節の知識(動的計画法)で解いて、初めて1000msを切れるようになっています。
|
|
5
|
+
|
|
6
|
+
> どちらのコードでも1100ms強の実行時間がかかってしまいました．
|
|
7
|
+
|
|
8
|
+
AtCoderでは、時間がかかるコードは途中で強制終了されます。1100msで実行が終わったわけではなく、1100msで強制終了されただけですので、多少高速化したぐらいでは1000msを切ることはできません。
|
|
9
|
+
|
|
10
|
+
---
|
|
3
11
|
|
|
4
12
|
3.7節の知識(動的計画法)で解く場合、以下のようになります。
|
|
5
13
|
```python
|
|
@@ -29,7 +37,16 @@
|
|
|
29
37
|
print("No")
|
|
30
38
|
```
|
|
31
39
|
|
|
32
|
-
なお、書籍の3.7.9節に書いてある通り、この問題には「部分和問題」という名前がついています。
|
|
40
|
+
なお、書籍の3.7.9節に書いてある通り、この問題には「部分和問題」という名前がついています。こちらの名前で検索すれば、さまざまな解説や実装例が見つかると思います。
|
|
41
|
+
|
|
33
|
-
|
|
42
|
+
---
|
|
34
43
|
|
|
35
44
|
ちなみに、ソートしてから1回だけしか二分探索しない場合、普通に検索するよりかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|
|
45
|
+
|
|
46
|
+
---
|
|
47
|
+
|
|
48
|
+
他の方の回答にあるように、メモ化せずに再帰を使った場合、カードの枚数が多めで答えがNoだと時間がかかるという問題があります。手元の環境だと、カード枚数23枚で1秒を超えました。
|
|
49
|
+
```text
|
|
50
|
+
23 277
|
|
51
|
+
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
|
52
|
+
```
|
3
全体の構成変更
test
CHANGED
|
@@ -1,4 +1,7 @@
|
|
|
1
|
-
|
|
1
|
+
問題の「注意」にも書いてありますが、この問題は2.4節までの知識(全探索)で解いても満点になりません。
|
|
2
|
+
3.6節の知識(再帰、他の方の回答を参照)や3.7節の知識(動的計画法)で解いて、初めて満点がとれるようになっています。
|
|
3
|
+
|
|
4
|
+
3.7節の知識(動的計画法)で解く場合、以下のようになります。
|
|
2
5
|
```python
|
|
3
6
|
a, b = map(int, input().split())
|
|
4
7
|
c = map(int, input().split())
|
|
@@ -10,7 +13,7 @@
|
|
|
10
13
|
print("Yes" if dp[-1] else "No")
|
|
11
14
|
```
|
|
12
15
|
|
|
13
|
-
2.4
|
|
16
|
+
2.4節までの知識で解く場合でも、わざわざ和をすべてsetなどに集めてから検索するのではなく、その場で和が目的の値か判定したほうが速くなりそうです。
|
|
14
17
|
```python
|
|
15
18
|
import itertools
|
|
16
19
|
import sys
|
|
@@ -26,4 +29,7 @@
|
|
|
26
29
|
print("No")
|
|
27
30
|
```
|
|
28
31
|
|
|
32
|
+
なお、書籍の3.7.9節に書いてある通り、この問題には「部分和問題」という名前がついています。
|
|
33
|
+
こちらの名前で検索すれば、さまざまな解説や実装例が見つかると思います。
|
|
34
|
+
|
|
29
35
|
ちなみに、ソートしてから1回だけしか二分探索しない場合、普通に検索するよりかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|
2
文言変更
test
CHANGED
|
@@ -26,4 +26,4 @@
|
|
|
26
26
|
print("No")
|
|
27
27
|
```
|
|
28
28
|
|
|
29
|
-
ちなみに、ソートしてから1回だけしか二分探索しない場合、
|
|
29
|
+
ちなみに、ソートしてから1回だけしか二分探索しない場合、普通に検索するよりかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|
1
全探索のコードと二分探索の注意点を追記
test
CHANGED
|
@@ -9,3 +9,21 @@
|
|
|
9
9
|
dp[i + n] = True
|
|
10
10
|
print("Yes" if dp[-1] else "No")
|
|
11
11
|
```
|
|
12
|
+
|
|
13
|
+
2.4.6節までの知識で解く場合でも、わざわざ和をすべてsetなどに集めてから検索するのではなく、その場で和が目的の値か判定したほうが速くなりそうです。
|
|
14
|
+
```python
|
|
15
|
+
import itertools
|
|
16
|
+
import sys
|
|
17
|
+
input = sys.stdin.readline
|
|
18
|
+
a, b = map(int, input().split())
|
|
19
|
+
c = input().split()
|
|
20
|
+
c = [int(t) for t in c]
|
|
21
|
+
for n in range(a,0,-1):
|
|
22
|
+
for combi in itertools.combinations(c, n):
|
|
23
|
+
if sum(combi) == b:
|
|
24
|
+
print("Yes")
|
|
25
|
+
exit()
|
|
26
|
+
print("No")
|
|
27
|
+
```
|
|
28
|
+
|
|
29
|
+
ちなみに、ソートしてから1回だけしか二分探索しない場合、ソートの分だけかえって遅くなるので注意しましょう。(ソートがO(N log N)なので、普通に検索するO(N)より遅くなる)
|