325.1

昔全然ダメだったセット...。今やるとなんとでもなりそうなのがせめてもの救い。

300

長さNのフェンスの故障個所が与えられる。フェンスの修理は位置IからJまでまとめてやると、SQRT(J-I+1)だけコストがかかる。このとき、故障していないところを修理しても良いので、故障個所すべてを修理するのにかかる最小コストを答えよ、という問題。

典型的なDPをやるだけ。現在位置を開始点として、位置Kまでの修理を終えるには、Kから現在位置よりの点で一番近い故障個所までを一括で修理すれば良い。

500

整数配列が与えられるので、すべての要素との差分の合計値がK以下になる整数の個数を求めよ、という問題。

取り敢えず配列はソートする。各要素について、すべての要素との差分の合計値を求めてやると、それは下に凸な関数になる。合計値がK以下のもので、最大のものの座標を求めてやり(なければ該当するものはない)、そこから1だけ外にずれるといくつ合計値が変動するかを計算すると、どれだけ外にずれられるかが分かる。これで両端点が求まるので、その区間にある整数の数を答えるだけ。

1000

1ドル紙幣から開始して、最高額の紙幣の2から5倍のいずれかの紙幣を発行するという行為を、紙幣の種類がK枚になるまで繰り返す。Nドルを支払うのに必要な紙幣の枚数を最小化するように構築し、その時の必要な枚数を答えよ、という問題。

Nドルを2から5のいずれかで割り、余りの分を1ドルで支払う。こうすると作った紙幣を1ドルとみなして再帰的に計算できる。発行できる紙幣の残り枚数と、支払う残高について、今までに支払った枚数をメモしておき、これが増えないように気を付けながら計算していくだけ。現在の最小枚数と比較して枝を狩るくらいしても良いかも。