問題（外部リンク） 2441 -- Arrange the Bulls 実装の概要 空いているところに牛を配置する問題。深さ優先探索では間に合いません。 ただ、nおよびmの最大値は大きくないのでビットDPであればで求めることができます。 具体的には、例えば1101(2進数)を1、3…

問題（外部リンク） Fastest Route | Aizu Online Judge 実装の概要 ステージを経由する順序によってそれぞれのステージをクリアするための時間が変わるためグラフのアルゴリズムをそのまま使うことはできません。 また、要素数は少ないですが流石にですべて…

問題（外部リンク） 1631 -- Bridging signals 実装の概要 信号が交差しないための条件は行き先の数字が単調増加することです。問題の1つ目の入力例では行き先が{4,2,6,3,1,5}となっており、できるだけ要素数が大きくなるように増加数列を作ると{2,3,5}とな…

問題（外部リンク） 1631 -- Bridging signals 実装の概要 動的計画法を用いて解きます。 配線が交わらないための条件は目的地のポート番号が{1,2,4,8,,,,}のように単調増加することです。そのためこの問題は最長増加部分列（LIS）の長さを求めるのと同じ方…

問題（外部リンク） 1065 -- Wooden Sticks 実装の概要 動的計画法を用いて解きます。 それぞれの棒には長さと重さが与えられていますが、分かりやすくするためにまず長さについて昇順にソートします。これによって「前の棒よりも重さが大きいか等しいならセ…

問題（外部リンク） 3181 -- Dollar Dayz 実装の概要 動的計画法で解きます。 決まった合計金額における品物の買い方のパターン数を問う問題ですが、例えば合計が$5なら「$1 $1 $1 $2」のように必ず安い順に購入すると決めると考えやすくなります。そこでdp[…

問題（外部リンク） 3046 -- Ant Counting 実装の概要 動的計画法を用います。 問題にあるように{1,2}と{2,1}などを重複して数えないように気をつける必要がありますが、そのためには「数字は必ず小さい順に並べる」と考えると分かりやすくなります。そしてd…

問題（外部リンク） 3616 -- Milking Time 実装の概要 「ある時点までに採れるミルクの量」を保存しつつ動的計画法で解きます。事前にインターバルを搾乳開始時を基準にソートし、その時間になったら直前までのミルクの量と新たに採れるミルクの量を足して「…