ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC153 F - Silver Fox vs Monster

問題
提出コード

解法

H_{i}について、Aで割り、切り上げをしておきます。これで、H_{i}

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

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

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

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

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

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