yukicoder contest 240 F (No.1008 Bench Craftsman)

問題

No.1008 Bench Craftsman - yukicoder

解法

基本は解説の通りであるが、自分なりの説明を行う。

まず、ベンチの耐久度を固定すると、人が番目の区画に与える負荷は、である。
この負荷は正の場合、人毎に等差数列になるため、imos法を用いることで、番目の区画に与える負荷の合計を、で求めることができる。

imos法の考え方としては、初項の場合は累積和を1回、公差の場合は累積和を2回行うことで、等差数列を作ることができる。
ただし、今回の場合はで傾きが反転するため、公差の場合においては左右それぞれの場合を考える必要がある。

右側の場合は比較的単純であるが、左側の場合は少し工夫が必要であり、1回目の累積和を行う際に、区間を1つ右にずらしておく必要がある。
そうすることで、実装の手間を減らすことができる。

あとは、固定していたベンチの耐久度を二分探索すれば良い。
ただし、が0の場合は、負荷が正である個数をにするか、処理を分ける必要がある。

全体の計算量は、となる。

コード

#440982 No.1008 Bench Craftsman - yukicoder

感想

わかってみるとそれほど難しくはないが、わかるまでが大変だった。
ただ、苦戦しただけあって、imos法の考え方を少しは理解できたように思う。
（自分なりの説明ができているかどうか微妙なので、問題があれば消します）