質問編集履歴
1
ベストアンサーと解決済みのコードの掲載
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -61,3 +61,20 @@
|
|
|
61
61
|
else:
|
|
62
62
|
print("No")
|
|
63
63
|
```
|
|
64
|
+
### ベストアンサーと解決済みコード
|
|
65
|
+
本業が忙しく，また動的計画法というものを知らなかったので，解答の理解に時間がかかってしまいました．
|
|
66
|
+
kazuma-sさん，lehshellさん，actorbugさん，ご回答いただきありがとうございました．
|
|
67
|
+
今回は解決だけでなく，学習につながる解説をしていただいたactorbugさんをベストアンサーとさせていただきます．
|
|
68
|
+
actorbugさんが投稿していただいたコードを解釈してみましたので，掲載しておきます．実行時間(63msほど)でした．
|
|
69
|
+
私としては，納得できましたが何か間違い等にお気づきの方はコメントいただけると幸いです．
|
|
70
|
+
##### 解決済みコードとその解釈
|
|
71
|
+
```Python
|
|
72
|
+
a, b = map(int, input().split()) # aがカードの枚数， bが判定値（判定基準）
|
|
73
|
+
c = map(int, input().split()) # cがカードの数値リスト
|
|
74
|
+
dp = [True] + [False] * b # dpのノードを作る．最初がtrueなのは， 判定する初期位置の設定？
|
|
75
|
+
for n in c: # カードの数値を取り出す．
|
|
76
|
+
for i in range(b - n, -1, -1): # 判定値から，リストの数字を引く．そこから， 値を大きい方から-1ずつ取り出す．indexの0まで
|
|
77
|
+
if dp[i]: # dpのリスト内の値は，真偽値なので帰ってくるのは"True" or "False"だから， Trueの場合は
|
|
78
|
+
dp[i + n] = True # Trueは値としては1だから，dpリスト内の1+（取り出した数値n）をTrueにする． 判定する位置の移動？
|
|
79
|
+
print("Yes" if dp[-1] else "No") # リストのindexがTrueならその数値をカードの合計で作れる．最後が判定値なので，"Yes"，Falseなら"No"
|
|
80
|
+
```
|