Codeforces Round #355 Div.2 A. Vanya and Fence / B. Vanya and Food Processor

Dashboard - Codeforces Round #355 (Div. 2) - Codeforces

4問解くか、3問早解きか、みたいな回だった

A. Vanya and Fence

• 問題

数列Aの各値を、H以下なら1、Hより大きいなら2と変換する。変換後の和を求めよ。
こんな問題文だからreadforcesとか揶揄されるんだ

• 解法

implement

• コード

B. Vanya and Food Processor

• 問題

ジャガイモを高さhまで入れられて分速kセンチ潰せるミキサーで、ジャガイモを潰すことを考える。
高さA_1, ..., A_nのジャガイモが与えられる。このとき、1分で行える操作は以下。

1. ジャガイモをA_1から順番に入れられるだけ入れる(ただし、高さがHを超える場合は入れられない)
2. ジャガイモをKセンチ潰す

これを繰り返して、全てのジャガイモを潰したとき、何分かかるか？

• 制約

1 <= n <= 10^5
1 <= k <= h <= 10^9

• 解法

単純にシミュレーションすると最悪O(h)かかってTLEする(ex. K=1, h=10^9, A={10^9, 10^9, 10^9, ...})ので、次のものを入れるためにはどこまで潰す必要があるかを式を立てて求める。
潰すのにかかる秒数と今の高さをそれぞれt, nowと置くと、以下の図の式が成り立つ

これをtについて解くと、t = ceil((A_i + now - h) / k) となるので、O(n)で答えを求めることができる。

• コード

• 感想

潰すタイミングをどこで書けばいいか迷って、かなり時間をとってしまった。