ABC472 C - On a Diet
ダイエット
考え方
まず、愚直に考える。
毎日、直前 $M-1$ 日の摂取カロリー合計を求め、それに今日の分を足して $K$ を超えるか判定する。
超えるなら食べない、超えないなら食べる、という処理をすればよい。
これで、$O(NM)$ でなら解けるが、大きい入力だと TLE してしまう。
そこで、sliding window法で高速化する。
最初のうちは、毎日の判定後に今日の摂取カロリーを加えれば、次の日の判定基準となる。
$M+1$ 日目から先は、それに加えて判定前にちょうど $M$ 日前の摂取カロリーを引く。
こうすると判定基準の「直前 $M-1$ 日の摂取カロリー合計」が足し算と引き算 $1$ 回ずつで求まり、高速。
全体で計算量は $O(N)$ となる。
食べなかったという情報の持ち方は様々ある。
食べなかった時には A を $0$ に書き換えて $0$ カロリー食べたことにしてしまうのが、分岐が減って楽。
入力例1での動作
入力を受け取る。
n: 5
m: 3
k: 83
a: {48, 73, 59, 90, 21}判定前には、直前 $M-1$ 日で実際に食べたおやつのカロリー合計を持っておく。
| 日 | 判定前の合計 | 今日を食べると | 判定 | 判定後の合計 |
|---|---|---|---|---|
| $1$ | $0$ | $0+48=48$ | $83$ 以下なので食べる | $48$ |
| $2$ | $48$ | $48+73=121$ | $83$ を超えるので食べず、$A_2=0$ にする | $48$ |
| $3$ | $48$ | $48+59=107$ | $83$ を超えるので食べず、$A_3=0$ にする | $48$ |
| $4$ | $48-48=0$ | $0+90=90$ | $83$ を超えるので食べず、$A_4=0$ にする | $0$ |
| $5$ | $0-0=0$ | $0+21=21$ | $83$ 以下なので食べる | $21$ |
処理後の $A$ は $(48,0,0,0,21)$ となる。
正の値なら Yes、$0$ なら No なので、各日の答えは順に Yes, No, No, No, Yes となる。
注意点
$K$ と、直前の日々で食べたおやつのカロリー合計は、int 型からはみ出る場合がある。
long long 型を用いること。
別解
特になし。