足跡-sokuseki-

りかの日進月歩の記録

ABC013 C 節制

先日 AtCoder Virtual Contest でやっていたABCのC埋めに出てきて、コンテスト中には解けなかったのでゆっくり解いていたが、満点解法がわからなかった&&時間がかかったので書く。

C: 節制 - AtCoder Beginner Contest 013 | AtCoder


問題概要


N日間の食事を次の3つから選ぶ。

・普通の食事 ( 出費A円、満腹度 +B )
・質素な食事 ( 出費C円、満腹度 +D )
・食事抜き  ( 出費なし、満腹度 -E )

最初の満腹度がHで、一度も満腹度が0以下にならないとき、最低何円でN日間乗り切れるか。


制約
 1 \le N \le 5 \times 10^5
 1 \le H \le 10^9
 1 \le C < A \le 10^6
 1 \le D < B \le 10^6
 1 \le E \le 10^6

部分点

10点……  N \le 10 を満たすテストケース
40点……  N \le 50, H \le 50, B \le 50, D \le 50 を満たすテストケース
100点……  N \le 10^3 を満たすテストケース
101点…… すべてのテストケース


部分点解法その1


 N \le 50 ,   H \le 50 ,  B \le 50 ,   D \le 50 の解法。問題を見た時にまずこれが浮かんだ。

日にちと満足度が決まればそのときの最小の食費は一意に定まるので、
dp[i][j]:=i日目に満足度がjであるときにかかる最小の食費
という配列をもつDPで解ける。
満足度の上限はH+NBより
計算量は  O(N(H+NB)) つまり O(BN^2)


部分点解法その2


 N \le 10^3 の解法。DPが思いついたあと、100点解法では満足度の上限がないため、満足度を使わずに食費が一意に定まるものは他にないかと考えて、「それぞれの食事をした回数が決まれば、満足度も食費も求めることができる!」と気づいた。
普通の食事の日数と質素な食事の日数が決まれば、食事抜きの日は「 n - (普通の食事の日数) - (質素な食事の日数) 」に決まるから、計算量は  O(N^2)



Submission #1111965 - AtCoder Beginner Contest 013 | AtCoder

普通の食事の日数をi日、質素な食事の日数をj日とすると、食事を抜く日数はn-i-j日である。
このとき、n日目の満足度は「  H + Bi + Dj - E(n-i-j) 」であるから、これが0より大きければ満足度が一度も0以下になることがないような食事の順番が存在する*1。よって、このときの合計の食費「  Ai+Cj 」が今までの暫定の最小の食費よりも小さければ暫定値を更新する。

満点解法


  N \le 5 \times 10^5 の解法。思いつかなかったので解説を見たら頭が良かった(それはそう)。

制約より、満腹度が大きくなるほど合計の食費も大きくなるので、合計の食費をできるだけ小さくするには満腹度が(一度も0以下にならないという制約を満たしつつ)できるだけ小さくなるようにすればいい。

つまり、普通の食事の日数をi日、質素な食事の日数をj日、食事を抜く日数はn-i-j日としたとき、  H + Bi + Dj - E(n-i-j) > 0 を満たすようなiとjのうち、iとjが最小になるものを考える。

2変数であるから、計算しやすいように片方の変数iを固定して考える*2
iを固定したとき

 H + Bi + Dj - E(n-i-j) > 0

 H + Bi + (D+E)j - E(n-i) > 0

 j > \frac{E(n-i)-H-Bi}{D+E}

となる最小の整数jは  O(1) で求まる。
これを  0 \le i \le n についてそれぞれ調べるので、全体の計算量は  O(N)



Submission #1112041 - AtCoder Beginner Contest 013 | AtCoder


普通の食事の日数がi日のとき、質素な食事の日数が0日かそうでないかで場合分けをする*3
 H + (B+E)i - En > 0 のときは質素な食事の日数が0日で良いため、合計の食費は Ai となる。
 H + (B+E)i - En \ge 0 のときは、最小となるjを求めて、 i+j \le n のとき(普通の食事の日数と質素な食事の日数の合計がn日以下のとき)は、合計の食費は Ai+Cj となる。 合計がn日より大きい場合は、なかったことにする。


感想


ABCのCなのに難しい問題が多くてつらい(人権がない)

*1:たとえば、はじめの1日目からi日目までは普通の食事をとり、i+1日目からi+j日目は質素な食事をとり、i+j+1日目からn日目は食事を抜くとき、満足度は一度も0以下にならない

*2:「予選決勝法」を思い出して懐かしい気持ちになった

*3:この場合分けをせずに、 0 \le j かつ i+j \le n にしていたらWAで、このWAが取れずにずっと悩んでいた