ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

2019-01-31から1日間の記事一覧

Educational DP Contest / DP まとめコンテスト F - LCS

問題 提出コード 明らかにMLEを起こしそうなコードを提出するのはやめましょう。 解法 求める文字列の長さだけなら、よくある問題です。 ですが、今回は文字列自体も求めなければいけないので、DPの遷移の際に、たどってきた1つ手前の値を一緒に記録してあげ…

Educational DP Contest / DP まとめコンテスト E - Knapsack 2

問題 提出コード 解法 番目までの品物を利用して合計が価値がとなるような組み合わせの中での合計重量の最小値 とします。 となります。あとは、をで、を0で初期化し、このDPを解くことで、となるの最大値を求めれば、これが答えになります。

Educational DP Contest / DP まとめコンテスト D - Knapsack 1

問題 提出コード 解法 こちらと全く同じです。 動的計画法(ナップサック問題について) - ツバサの備忘録 番目までの品物を使って、重さの合計がとなるような組み合わせの中での価値の最大値 とすると、 となります。 答えはの最大値です。

Educational DP Contest / DP まとめコンテスト C - Vacation

問題 提出コード 解法 日目に行動を選択(0:A,1:B,2:C)したときの~日までの幸福度の合計の最大値 とします。 すると、 のとき のとき のとき となります。 あとは、これをもとに計算をし、の最大値を選べば答えになります。

Educational DP Contest / DP まとめコンテスト A - Frog 1,B - Frog 2

問題(A) 問題(B) 提出コード(B) Bの問題においてK=2とすればAの問題と同じになります。 解法 個目の足場に行くための最小コスト、とします。すると、 が答えになります。 あとは、 となります。ここで、は1以上以下かつ、が0以上となるような数字です。 今回…