ABC063D

見当がつかなかったので、解説を見ました。

分かるまで考えると記憶に残るというのはあるのですが、精神が擦り減るので最近は気が向いたときにしかやっていません。

（前回のブログで、解説を見ないと考察が中途半端でコードが汚くなると書いたのですが、今回は解説を見たので比較的綺麗です）

ABC063Dは、1体だけA、それ以外にBを与える爆発を使い、体力のN体の魔物全てを消し去るには、最小で何回の爆発が必要かという問題です。

  int n, a, b; cin >> n >> a >> b;
  int h[n];
  for (int i = 0; i < n; i++) cin >> h[i];

まず、爆発の回数で二分探索をするので、二分探索の右端を調べるために、の最大値を求めます。

爆発の回数は、の最大値をBで割った値（を切り上げたもの）よりは大きくなることがないので、その値を右端とするためです。

  int maxh = 0;
  for (int i = 0; i < n; i++) maxh = max(maxh, h[i]);

後は二部探索をするだけです。

具体的には、各における、B×爆発の回数だけで倒せない分の体力をA-Bで倒しきる回数を合計し、回数の合計が爆発の回数を超えていた場合、左端を爆発の回数+1に、超えていなかった場合、右端を爆発の回数にします。

境界のアウトが左側、境界のセーフが右側の場合、アウトの時を中心値+1、セーフの時中心値にすれば、左端・右端共にセーフ側の境界値に収束する感じですね。

（掛け算による整数オーバーフローに注意）

  int l = 1, r = (maxh + b - 1) / b;
  while (l < r) {
    int c = (l + r) / 2;
    ll count = 0;
    for (int i = 0; i < n; i++) {
      int rest = max(0LL, h[i] - b * (ll)c);
      count += (rest + (a - b) - 1) / (a - b);
    }
    if (count > c)
      l = c + 1;
    else
      r = c;
  }
  cout << l << endl;

今回は比較的綺麗に文章を書くことが出来た気がします。

次回もこの調子で書いていきたいですね。

では。