回答編集履歴
4
コード追記
answer
CHANGED
|
@@ -22,4 +22,108 @@
|
|
|
22
22
|
|
|
23
23
|
が，本件について言えば，そもそもが「ＤＰの学習」なので，上記の「謎の前提」に従う以外に道は無いハズです．
|
|
24
24
|
行動の目的自体が「ＤＰ」なのですから，あなたが直感的に思いつく方法が「ＤＰではない」場合，それは無視するしかないです．
|
|
25
|
-
「納得」を後回しにするということは，「ＤＰの学習」自体を後回しにするということと同義かと思えます．
|
|
25
|
+
「納得」を後回しにするということは，「ＤＰの学習」自体を後回しにするということと同義かと思えます．
|
|
26
|
+
|
|
27
|
+
---
|
|
28
|
+
|
|
29
|
+
[追記]
|
|
30
|
+
|
|
31
|
+
> 問題1~3にあなたならどう回答するか、どういう方針で取り組むのかを答えてくださった方が、有意義だと考えてしまいます。
|
|
32
|
+
|
|
33
|
+
こんな…かなぁ…？
|
|
34
|
+
簡単な入力例でしか確認してないのでコレで合ってるかどうかは保証しかねますが，「方針」はコメントとして記しておきました．
|
|
35
|
+
|
|
36
|
+
```C++
|
|
37
|
+
//MEMO :
|
|
38
|
+
//* 扱う値が正の整数ならば unsigned とかにすべきかもしれませんが，
|
|
39
|
+
// ここではとりあえず方針を示すのが目的なので，全部 int で書いてます．
|
|
40
|
+
//* 途中経過の情報を記録する配列は全て Memo という変数名にしています．
|
|
41
|
+
|
|
42
|
+
//(1)
|
|
43
|
+
//N個の正の整数 a_1, a_2, ..., a_N が与えられます。
|
|
44
|
+
//これらのうちいくつかを選んで、ちょうど合計 S にできるか判定してください。
|
|
45
|
+
template< int S, int N >
|
|
46
|
+
bool Q1(
|
|
47
|
+
const int (&A)[N] //N個の正の整数
|
|
48
|
+
)
|
|
49
|
+
{
|
|
50
|
+
//Memo[x] は，処理中に合計値xになったか否か
|
|
51
|
+
bool Memo[S + 1];
|
|
52
|
+
for( bool &b : Memo )b = false;
|
|
53
|
+
Memo[0] = true;
|
|
54
|
+
|
|
55
|
+
//{ a_1 } だけで達成できる合計値とはどれどれか？
|
|
56
|
+
//{ a_1, a_2 } だけで達成できる合計値とはどれどれか？
|
|
57
|
+
//…
|
|
58
|
+
//と見ていく感じで Memo を更新していく．
|
|
59
|
+
//（質問文で示されている疑似コードと全く同じかと）
|
|
60
|
+
for( int a : A )
|
|
61
|
+
{
|
|
62
|
+
for( int x=S-a; x>=0; --x )
|
|
63
|
+
{
|
|
64
|
+
if( Memo[x] )
|
|
65
|
+
{ Memo[x+a] = true; }
|
|
66
|
+
}
|
|
67
|
+
}
|
|
68
|
+
|
|
69
|
+
return Memo[S];
|
|
70
|
+
}
|
|
71
|
+
|
|
72
|
+
//(2)
|
|
73
|
+
//N段の階段があります。
|
|
74
|
+
//一度に1段か2段ずつ上ることができます。
|
|
75
|
+
//N段目に到達する方法は何通りあるか求めてください。
|
|
76
|
+
template< int N >
|
|
77
|
+
int Q2()
|
|
78
|
+
{
|
|
79
|
+
//Memo[x] は，x段目に到達できる方法の数
|
|
80
|
+
int Memo[ N+1 ] = { 0 };
|
|
81
|
+
Memo[0] = 1;
|
|
82
|
+
|
|
83
|
+
//単に，下の段から順にパターン数を積み上げていくだけでいけるんじゃないかな
|
|
84
|
+
for( int x=0; x<=N-2; ++x )
|
|
85
|
+
{
|
|
86
|
+
Memo[x+1] += Memo[x];
|
|
87
|
+
Memo[x+2] += Memo[x];
|
|
88
|
+
}
|
|
89
|
+
Memo[N] += Memo[N-1];
|
|
90
|
+
|
|
91
|
+
return Memo[N];
|
|
92
|
+
}
|
|
93
|
+
|
|
94
|
+
//(3)
|
|
95
|
+
//N種類のコインがあります。
|
|
96
|
+
//それぞれのコインの価値は coins = [c1, c2, ..., cN] です。
|
|
97
|
+
//合計金額 M を作るときに必要なコインの枚数の最小値を求めてください。
|
|
98
|
+
//作れない場合は -1 を返してください。
|
|
99
|
+
template< int M, int N >
|
|
100
|
+
int Q3( const int (&C)[N] )
|
|
101
|
+
{
|
|
102
|
+
//Memo[x] は，x円を作るのに必要なコインの最小枚数．
|
|
103
|
+
//ただし「x円を作れない」ことを示す特殊値として -1 を用いる．
|
|
104
|
+
int Memo[M+1];
|
|
105
|
+
for( auto &m : Memo )m=-1;
|
|
106
|
+
Memo[0] = 0;
|
|
107
|
+
|
|
108
|
+
//金額が低い側から順に作れるかどうか見ていく
|
|
109
|
+
for( int iFrom=0; iFrom<M; ++iFrom )
|
|
110
|
+
{
|
|
111
|
+
if( Memo[iFrom]<0 )continue;
|
|
112
|
+
|
|
113
|
+
//iFrom円を作れるなら，それに１枚コインを足した金額は全て作れる
|
|
114
|
+
for( int c : C )
|
|
115
|
+
{
|
|
116
|
+
int iTo = iFrom + c;
|
|
117
|
+
if( iTo > M )continue;
|
|
118
|
+
//iTo円を作るのに要する最小枚数を更新
|
|
119
|
+
if(
|
|
120
|
+
( Memo[iTo]<0 ) ||
|
|
121
|
+
( Memo[iTo] > Memo[iFrom]+1 )
|
|
122
|
+
)
|
|
123
|
+
{ Memo[iTo] = Memo[iFrom]+1; }
|
|
124
|
+
}
|
|
125
|
+
}
|
|
126
|
+
|
|
127
|
+
return Memo[M];
|
|
128
|
+
}
|
|
129
|
+
```
|
3
追記
answer
CHANGED
|
@@ -18,4 +18,8 @@
|
|
|
18
18
|
実際に何かしらの初見の問題に対面した際に複数個の方法論が思いつくというのはよくあることなわけで，
|
|
19
19
|
それらの方法の間に「ギャップ/違い」があるのは，何をどう考えても **当たり前のこと** です．
|
|
20
20
|
（差が無いなら，異なる方法ではないのだし，その差を「埋める」ことに何の 意味/意義 があるというのか？）
|
|
21
|
-
その場の制約等々に応じて，複数の候補の中から必要十分な方法を選べば良いだけのことです．
|
|
21
|
+
その場の制約等々に応じて，複数の候補の中から必要十分な方法を選べば良いだけのことです．
|
|
22
|
+
|
|
23
|
+
が，本件について言えば，そもそもが「ＤＰの学習」なので，上記の「謎の前提」に従う以外に道は無いハズです．
|
|
24
|
+
行動の目的自体が「ＤＰ」なのですから，あなたが直感的に思いつく方法が「ＤＰではない」場合，それは無視するしかないです．
|
|
25
|
+
「納得」を後回しにするということは，「ＤＰの学習」自体を後回しにするということと同義かと思えます．
|
2
誤記修正と末尾一文追加
answer
CHANGED
|
@@ -11,10 +11,11 @@
|
|
|
11
11
|
> (3)どういった形式の問題なら直感とdp表のギャップを埋められるか？また何故このような思考の違いがでるのか？
|
|
12
12
|
|
|
13
13
|
そもそも今回の状況について言えば， **実際の問題に直面するよりも前の段階で** あなたの中に
|
|
14
|
-
【「DPというのはこういうものである」という何らかのイメージができていて，且つ，これから出題される問題はと
|
|
14
|
+
【「DPというのはこういうものである」という何らかのイメージができていて，且つ，これから出題される問題はとにかく何が何でもそれを用いて解かねばならない】
|
|
15
15
|
とかいう謎の前提が存在していることが「違い」の原因です．
|
|
16
16
|
普通，解決すべき課題が何なのかがわからない時点で「次に直面する問題はこのアルゴリズムで～」とか考えるわけないですよね．
|
|
17
17
|
|
|
18
18
|
実際に何かしらの初見の問題に対面した際に複数個の方法論が思いつくというのはよくあることなわけで，
|
|
19
19
|
それらの方法の間に「ギャップ/違い」があるのは，何をどう考えても **当たり前のこと** です．
|
|
20
20
|
（差が無いなら，異なる方法ではないのだし，その差を「埋める」ことに何の 意味/意義 があるというのか？）
|
|
21
|
+
その場の制約等々に応じて，複数の候補の中から必要十分な方法を選べば良いだけのことです．
|
1
誤字修正
answer
CHANGED
|
@@ -11,7 +11,7 @@
|
|
|
11
11
|
> (3)どういった形式の問題なら直感とdp表のギャップを埋められるか？また何故このような思考の違いがでるのか？
|
|
12
12
|
|
|
13
13
|
そもそも今回の状況について言えば， **実際の問題に直面するよりも前の段階で** あなたの中に
|
|
14
|
-
【「DPというのはこういうものである
|
|
14
|
+
【「DPというのはこういうものである」という何らかのイメージができていて，且つ，これから出題される問題はとくかく何が何でもそれを用いて解かねばならない】
|
|
15
15
|
とかいう謎の前提が存在していることが「違い」の原因です．
|
|
16
16
|
普通，解決すべき課題が何なのかがわからない時点で「次に直面する問題はこのアルゴリズムで～」とか考えるわけないですよね．
|
|
17
17
|
|