DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

ダンジョン攻略

問題に戻る

解説

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

Ai<XA_i < XAi​<X であるダンジョンの中から、BiB_iBi​ が最も小さいダンジョンを選ぶ。現在のレベルが XXX で、選んだダンジョンの二つ目の難易度が BBB ならば、攻略後のレベルは

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

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

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

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

Solution written by GPT5

i
​
i
​
i
​
5.00001×10175.00001\times 10^{17}5.00001×1017