ABC153 F - Silver Fox vs Monster

問題
提出コード

解法

について、で割り、切り上げをしておきます。これで、が

• 番目のモンスターを倒すまでにかかる攻撃回数

となります。加えて、全てのモンスターを、の昇順で並び替えます。

1番目のモンスターについて考えると、回どこかで攻撃しなければなりません。このモンスターへの攻撃を最適化することを考えると、の地点を攻撃することが最適です。なぜなら、これより右側の地点を攻撃してもを攻撃することはできず、これより左側の攻撃を攻撃をしても、1番目のモンスターよりも左側にモンスターは存在しないので、得をしません(右側にはモンスターがまだいる可能性があるので、できるだけ右側も攻撃できるようにするべきです)。
すると、の区間内に存在するモンスターは、回攻撃されることになります。
すると、1番目のモンスターを除去し、先ほどの区間内に存在するモンスターについて回攻撃を与えた後の状況について考えればよいことになります。 これを繰り返すと、前から順番に、番目のモンスターに攻撃すべき残り回数分だけ、で攻撃を行う、という操作を前から順番に繰り返せばよいです。
攻撃を行った回数のリストを作成します。範囲攻撃なので、ある区間について同じ値を足したいのですが、についての区間加算を、BIT上でいもす法のように、に値を加算、から値を引くことで表現します。
すると、今までで番目のモンスターに攻撃した回数が、BITにおける1からまでの値の総和を計算することで計算できるようになります。
また、を攻撃した際にダメージを与えられないモンスターのインデックスの最小値を計算するための変数を用意しておきます。初期値は左端のインデックスとしておきます。
今番目のモンスターについて処理を行う際、

• 攻撃した回数がを超えている場合
  スルーします。

• 超えていない場合
  残り攻撃すべき回数をとします。
  を計算します。しゃくとり法のようにをインクリメントしていき、を超える最小のを新たなとします。
  すると、今回の処理でに回攻撃することになります。
  答えにを加算します。
  BITの処理は、の部分にを加算し、の部分からを減らします。

これを繰り返すことで、答えを求めることができます。