yukicoder1071を解いた

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.1071 ベホマラー - yukicoder

星2の問題です。
よく見る系統の問題ですね。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。

---

問題概要

HPを持ったN人の仲間がいる。
HPの現在値は1で、最大値はAi。

• YのMPを消費して全体回復を行うか
• XのMPを消費して単体回復を行うか

を全員がHP満タンになるまで行う。
回復量はどちらの操作も同じ(K)。

使用MPの最小化をせよ。

考察

全体回復をする数を固定すると考えやすそうかな？

制約を見る限り、固定値を全部試すには10⁹かかるから厳しそうだね。

単体回復、全体回復の回復量(K)が両方とも同じだから全体回復の消費MP(Y) < 単体回復の消費MP(X)ならずっと全体回復すればいいね。

単体回復をする必要がある場合はHPが満タンじゃない人 * X < Yかどうかを見ればいいかな？

例えば2人傷ついてる人を考えた時、全体回復ならY、単体回復なら2X必要だよね。
2Xの方が小さければ単体回復をした方がいいね。

上記の式の不等号が入れ替わるタイミングまで、何回全体回復するかを求めれば答えが出そうだね。

方針通りでAC！

あとがき + 解法(ネタバレ全開)

考察中に出てきた式を使って、負傷者が何人いる時まで全体回復した方がいいかは簡単に求められます。

式変形するなり、全探索するなり。
私は頭に優しい全探索しました。

負傷者の数(w)を0 ~ nまで変えて実際に不等号が入れ替わるタイミングを探す形ですね。

次に求めるのは、何回全体回復したらいいかです。

Aをソートしておくとわかりやすいですね。

HPの最大値が大きい人順にw人残すように回復すれば良いです。

後は残ったHPを単体回復で同じように回復させていけば答えです。

ソースコード

int main() {
  ll input(n, k, x, y);

  vector<ll> a(n);
  REP(i, n) cin >> a[i];
  REP(i, n) a[i]--;

  sort(a.begin(), a.end());

  ll woundeds = n;
  while (woundeds * x >= y) woundeds -= 1;

  ll all;
  if (woundeds == n) all = 0;
  else all = (a[n - woundeds - 1] + k - 1) / k; // 全体回復

  ll ans = all * y;
  REP(i, woundeds) { // 単体回復
    ans += (((a[n - woundeds + i] - all * k) + k - 1) / k) * x;
  }
  print(ans);
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間となっています。

https://yukicoder.me/submissions/494437

woundedsが上記の解法で言ってるwですね。

全体回復回数を求めて、単体回復回数をそれぞれ求めて・・・という順番です。

それでは、またっ！

おまけ

a / b : 切り上げをする時に、(a + b - 1) / b : 切り下げをよく使います。

ちょっと式が複雑になると思いますが、小数が出てこなくていい感じです。

よく使ってる人がいるので、頭の片隅に置いておくといいかと思います。