276.1

250

ある品物がK個セットのとき価格Nとする。最低A個入手するのにかかる最小コストを求めよ、という問題。

ある個数入手するのに必要な最小価格についてDPする。最低A個なので、単価の安い大きなセットを購入することも考慮に入れて、少し余分にDPしつつ、A個以上になるもので最小コストのものを答えれば良い。

500

ある時間期間に出して良い上限速度が指定されている。加速度の最大値が与えられるので、その制限において、開始からある時刻までに可能な最高速度を求めよ、という問題。

すべての制約のグラフを求めて、その重なりのうち最大のものを求めれば良い。初速が0なので、傾きが加速度に等しい直線が最初の制約。後はある区間において速度制約を満たす線分と、その両端点から傾きが加速度に等しい(2次元グラフに描くと上向きの)半直線。すべての線分(開始から終了までで切るので線分になる)間で、交差する時刻を求め、それが開始時刻から終了時刻までの間にあれば、すべての線分のうちその点を含むものの最小値がその時刻での可能な最高速度。変極点以外で最大速度は実現されないはずなので、これらのうち最大のものを答えれば良い。

1000

N個のものを使って、耐久力を測定する。そのうち高々1個だけ欠陥品があり、それは耐久力が他のよりも小さい。圧力をかけるという操作を何回行えば、最大耐久力を計測できるかこたえよ、という問題。

ある点で壊れたときに、それが欠陥品である可能性を考慮する必要がある。欠陥品があるかどうかでそれぞれについてDPすれば良さそう。DPでは、後いくつ使えるか、測定しないといけない範囲はどこか、これまでに壊れた最小値はどれか、の三つから計算する必要がありそう。うまく式にならない...。