Top

(ΦωΦ)<これのつづきですよー。目次はここ

---
練習問題だよ。
(1) 再帰関数のインターフェース(シグニチャ)を考えて、
(2) メモ化再帰で書いてみよう。
インターフェースは「知りたいことと、それを一意に決める情報は何か」というのを考えること。
知りたいことが戻り値、一意に決める情報が引数になる。

問1-1
天秤に $N$ 個のおもりを置くことを考えます。
おもりは必ず左右のどちらかに置くとしたとき、天秤が釣り合うようにできるかを判定してください。yukicoder No.4
$N$ は $100$ 以下。それぞれのおもりの重さも $100$ 以下。
答えへのリンク

問1-2
$N$ 問の問題について、それぞれの配点が与えられます。
総得点として取り得るのは何通りか求めてください。AtCoder Typical DP A
$N$ は $100$ 以下。各問の配点も $100$ 以下。
答えへのリンク

問1-3
こんな2人対戦のゲームをします。
猫コインが積まれた山が2つあり、先手と後手が交互にどちらかの山の一番上の猫コインを取ります。
猫コインにはそれぞれ価値がパラメータとして存在し、両者とも取ったコインの合計価値をなるべく多くしたいとします。
どっちかの山からコインが無くなったら、残ってる方の山から取ります。
どっちの山からもコインが無くなったらゲーム終了です。先手が得る価値の合計はいくらですか。AtCoder Typical DP B
ひとつの山に積まれた猫コインの数は $1{,}000$ 以下。猫コインの価値も $1{,}000$ 以下。
答えへのリンク

問1-4
敵が最大で3体いて、それぞれのHPが与えられます。
全体攻撃をすることができ、1体めは $9$ ポイント、2体めは $3$ ポイント、3体めは $1$ ポイントのダメージを与えることができます。
全体攻撃をするとき、敵をどの順番で攻撃してもいいとすると、最低何ターンで全ての敵を倒すことができますか。SRM 658 Div2 Med
それぞれのHPは $60$ 以下。
答えへのリンク

(ΦωΦ)<つづく