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

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

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

BCDは難易度順に逆転がないと進行できないのか

問題に戻る

解説

PjP_jPj​ を問題 jjj より前にある問題の難易度の最大値、QjQ_jQj​ をそれより後にある問題の難易度の最小値とする。前に問題がない場合は Pj=0P_j=0Pj​=0、後に問題がない場合は Qj=M+1Q_j=M+1Qj​=M+1 とする。最初に解けなくなる問題が jjj 番である被害者の人数は

max⁡(0,Aj−max⁡(Pj,Qj))\max\bigl(0,A_j-\max(P_j,Q_j)\bigr)max(0,Aj​−max(Pj​,Q

である。

この値をすべての jjj について足し合わせる。右から走査して QjQ_jQj​ を求めた後、左から PjP_jPj​ を更新しながら合計を計算する。時間計算量と空間計算量はいずれも O(N である。

証明

難易度順に並べ替えられている場合、実力が sss の参加者は難易度が sss 以下の問題をすべて解く。したがって、被害者となるための必要十分条件は、最初に解けずに止まる問題より後に、その参加者が解ける問題が残っていることである。

最初に解けなくなる問題が jjj 番であるための条件は Pj≤s<AjP_j\leq s<A_jPj​ であり、後に解ける問題が存在するための条件は である。両方の条件を満たす実力の個数は である。各被害者について最初に解けなくなる問題は一意なので、合計に重複も漏れもない。

j​
)
)
)O(N)
O(N)
≤
s<
Aj​
Qj≤sQ_j\leq sQj​≤s
max⁡(0,Aj−max⁡(Pj,Qj))\max(0,A_j-\max(P_j,Q_j))max(0,Aj​−max(Pj​,Qj​))