問題

整数 $E, \mathrm{EM}, M, \mathrm{MH}, H$ が与えられる。 を求めよ。

あるいは、次の整数計画問題を解け:

  • max: $x _ {E,M,H} + x _ {E,M,MH} + \dots$
  • sub.to:
    • $x _ {E,M,H} + x _ {E,M,MH} + \dots \le E$
    • $x _ {EM,M,H} + x _ {EM,M,MH} + \dots \le \mathrm{EM}$
    • $\dots$

考察

  1. やるだけぽい見ため
  2. あっ 微妙にめんどう
  3. 整数計画問題に帰着できたし解けたことにしていい? だめです。ひゃあ
  4. 整数計画問題のいい感じ実装を自動で出力してくれるすごいツールがほしいよう
  5. まあこういうのはたいてい $1$ 点固定すると残りが自明に解けるんですよね
  6. 単調性の証明が自明でないし二分探索やだなあ

解法

$\mathrm{EM}$ を $E + M$ にどう分けるかを二分探索する。 これが固定されたとき $\mathrm{MH}$ を $M + H$ にどう分けるかは明らか。 全体で $O(\log \mathrm{EM})$ で解ける。

反省

  • ぐだぐだやったとはいえ 54 分かかったので青パフォです。だめ

メモ

  • $x$ を動かしたときの $E’, M’, H’$ の動きはそれぞれ区分的に $1$ 次間数である。特にその向きと、式が $\min { E’, M’, H’ }$ の形であることから、単調性が従う
  • 難易度 Easy, Medium, Hard に加えて難易度 Ultimate を足したとしたら解けるか?
    • $\mathrm{MH}$ に関して二分探索すればできそう? $\to$ たぶんできる
    • なお整数計画問題だしつよいソルバで殴ればいけるのでは?

リンク