いもす法の勉強

AtCoder　ABC183のD問題の公式解説に「いもす法」が紹介されていました。

今回はABC183のD問題を解く前にまず「いもす法」について勉強したいと思います。

参考させていただいた記事はこちら
いもす法 - いもす研 (imos laboratory)

ABC183のD問題を例題とします。
atcoder.jp
3人お湯を使う人がいて順にA・B・Cさんとします。
Aさんは時間2～4まで5リットル、
Bさんは時間1～2まで2リットル、
Cさんは時間3～4まで4リットルのお湯を使います。
以上の条件でいもす法を用いて考え方を整理していきます。

①すべての時刻でお湯の量が0の配列を用意する

②Aさんは時間2～4まで5リットル→使い始めの時刻2で＋5、使い終わりの時刻4で－5

③Bさんは時間1～2まで2リットル→使い始めの時刻1で＋2、使い終わりの時刻2で－2

④Cさんは時間3～4まで5リットル→使い始めの時刻3で＋4、使い終わりの時刻4で－4

⑤配列の累積和を計算する（要素N=要素N-1 + 要素N）

上記の手順で各時刻におけるお湯の使用量がわかります。
時刻3の9リットルが最大使用量となります。

以上のようにすべて要素が0の配列に使い初めのタイミングに使う量をプラスし、使い終わり時刻でマイナスしていきます。
最後に累積和を計算することで最大の使用量がわかります。

いもす法を初めて学び考え方はわかりましたが、実際に使うときはなかなかうまくいかないと思います。
例題に使用したABC183のD問題で実際にプログラミングを行って、より深く学習したいと思います。