ダンジョン攻略

現在のレベルが $X$ のとき、$A_i < X$ であるダンジョンだけを考えればよい。この条件を満たさないダンジョンに挑戦してもレベルは増加しないため、後で挑戦する場合より有利になることはない。

$A_i < X$ であるダンジョンの中から、$B_i$ が最も小さいダンジョンを選ぶ。現在のレベルが $X$ で、選んだダンジョンの二つ目の難易度が $B$ ならば、攻略後のレベルは

$$X+\min(X,B)$$

となる。現在攻略できる二つのダンジョンの二つ目の難易度が $b \leq c$ であるとき、二つのダンジョンを $b,c$ の順に攻略した後のレベルは、$c,b$ の順に攻略した後のレベル以上である。この交換論法を繰り返すと、現在攻略できるダンジョンの中で $B_i$ が最も小さいダンジョンを最初に選んでも、最適解を失わないことが分かる。

ダンジョンを $A_i$ の昇順にソートする。$A_i$ が現在のレベルより小さいダンジョンの $B_i$ を最小ヒープに追加し、ヒープから最小値を取り出してレベルを更新する。ヒープが空なら、残っているすべてのダンジョンではレベルを上げられないため終了する。

時間計算量は $O(N\log N)$、空間計算量は $O(N)$ である。最終的なレベルは $L+\sum B_i$ 以下であるため、 以下であり、符号付き 64 ビット整数の範囲に収まる。

Solution written by GPT5