ABC #013 C – 節制

問題の概要


abc013.contest.atcoder.jp

  N \ (1 \leq H \leq 5 \times 10^{5})日の間、初期値  H \ (1 \leq H \leq 10^{9})満腹度を 0以下にさせないために、以下のような食事のいずれかを選ぶ。

内容 食費 満腹度の変動
普通の食事  A \ (1 \leq A \leq 10^{6})  +B \ (1 \leq B \leq 10^{6})
質素な食事  C \ (1 \leq C < A)  +D \ (1 \leq D < B)
食事抜き  0  -E \ (1 \leq E \leq 10^{6})

 以上の条件を満たす必要最低限の食費はいくらかを求める。 また、満腹度には上限がない上、 Nの値の範囲で以下のように部分点が設定されている。

範囲  N \leq 10  N, H, B, D \leq 50  N \leq 1000  N \leq 5 \times 10^{6}
点数 10 40 100 101

問題の考察


 普通の食事の日数を X日、質素な食事の日数を Y日とする。

 この時、満腹度には上限がないため、最初の X + Y日に全ての食事を済ますと考える。 この方法では、満腹度が途中で 0になる状態を考えずに、食費の最小値を求めることができる。

f:id:farma_11:20180109090500p:plain
食事の計画

解答例


[100点解法]  (X, Y) に対する全探索

 各  (X, Y) に対して、以下の不等式が成り立つかどうかを確認する。

 H + BX + DY - (N - X - Y)E > 0 \ \cdots \ (1)

 しかし、この解放では O(n^{2})であるため、 N \leq 5 \times 10^{6}のテストケースでは時間が足りない。

[満点解法]  Xのみの全探索

 式 (1) を以下のように式変形すると Xのみの探索で済むため、 O(n) で求めれる。

 Y > \frac{(N - X)E - H - BX}{D + E} \ \cdots \ (2)

 また、 Xの値が大きいとき、 Yの値が負の値をとることがあるため、注意が必要となる。

[満点解法] 尺取り法を用いた解法

 この解法では、式 (1) をそのまま用いる。  (X, Y)の探索を、以下のように尺取り法を用いることで、 O(n)で探索することを可能とした。

  1. 最初に、普通の食事だけで乗り切る場合の最低回数を求める。これを Xとする。
  2. 式(1)を満たさなくなるまで、 Xを減少させる。
  3. 式(1)を満たすまで、質素な食事の回数 Yを増加させる。
  4. 操作2, 3ができなくなるまで繰り返す。

 以上のソースコードは以下のGithub上にて参照可能です。 github.com

その他の解説サイト

広告を非表示にする