モラトリアムライフ

自由を求めて

ツイッターで見た問題について

ツイッターを眺めていると ABCのwriterをなさっている競プロフレンズさんが問題を出しておりましたので, その問題について個人的に考えたことを記します. (問題はツイッターを参照)

考察1

まず, 言えることは「モンスターを1度攻撃したなら, そのモンスターのHPが0以下になるまで攻撃をするべきである」ということである. 明らかもしれないが, 簡単にそのことを示す.
モンスター i を攻撃した後まだモンスターがHP1以上であり, その後にモンスター j (\neq i) を攻撃したとしよう. このとき, 倒れるまでの回数はモンスター固有であることを考えると, モンスター i, j に関する攻撃の順序をどのように入れ替えようとも両方が倒れる時点は変わらない. ここで, モンスター i が j よりも先に倒される場合, 攻撃対象をモンスター i, i, ..., i , j, ..., j の順に攻撃順序を入れ替えるとモンスター i は 元の攻撃よりも早く倒れ, 結果モンスター i から食らうダメージが減り, j からのダメージは変わらないので結果として被ダメージは減少する. 同様に, j が先に倒される場合は j, j, ...., j, i, i, ..., i の順序に入れ替えることで被ダメージを減らすことができる. これを全てのモンスターに関して倒される前に別の攻撃対象に変わっているなら前述のように並び替えることをすると, 上記で述べた戦略がある種「局所最適解」として得られる.

考察2

したがって, 上記の戦略からどのモンスターを順に倒すかを探索すれば良いということになる. これをもし全探索するとすると, 計算量 O(n!) かかってしまい間に合わない. そこで, 順序を全探索する際の典型 bitDPを使うことで計算量を O(n \cdot 2^{n}) に抑えることができ, 間に合うようなコードが作ることができる.

考察3

TLを見ると, もっと大きい制約で解くことができるという旨のツイートがあったのでそれについて考える.
各モンスター i に対して 体力 H_{i}とその攻撃力 D_{i} があるが, 倒すために必要な回数を S_{i} := \lceil \frac{H_{i}}{A} \rceil とすると, このとき受ける総被ダメージは

\displaystyle{ \sum_{i = 1}^{n} \left( \sum_{j \leq i} S_{j} - 1\right) D_{i} = \sum_{i = 1}^{n} \left( \sum_{j \leq i} S_{j} \right) D_{i} - \sum_{i}^{n} D_{i} }

と書けることに注意する. もし最適解を与えるような倒す順序が得られているとし, その順番に添字を並び替えて以降は考える. そのとき, i, i + 1 番目を交換したとすると, その被ダメージは - S_{i} D_{i+1} + S_{i+1} D_{i} 増加する. したがって, 全ての 1 \leq i \lt n に関して - S_{i} D_{i+1} + S_{i+1} D_{i} \leq 0, すなわち \frac{D_{i}}{S_{i}} \leq \frac{ D_{i+1} }{ S_{i+1} } である必要がある. つまり, c_{i} = \frac{D_{i}}{S_{i}} と表す時 c_{1} \leq c_{2} \leq ... \leq c_{n} が成り立っている. すると, 順序が"ほとんど一意"になるような条件が必要条件から得られた.
次に, この等号の中でどのような順序を選択するべきかを考えなければいけない、と言いたいところが, 上記の式を考えると、等号が成り立つどの隣り合う2要素の順序を交換しても被ダメージは変わらない. したがって, 等号内がどのような順序であろうと, 等号内で隣接swap操作を行うことで値を変えることなく想定した最適解を与える順序に並び替えることができる, すなわちソートされているならば最適解と同じ値が得られるのである. ゆえに, ソートして累積和を用いて計算すればよく, 答えが O(n \log n) で求めることができた.