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

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

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

最小値の削除

問題に戻る

解説

削除できる要素 xxx が長さ二以上の区間の最小値なら、その区間内に直接隣接する要素が一つ以上あり、それは xxx より大きい。逆に大きい隣接要素があれば、その二要素を区間として xxx を削除できる。従って、現在の左右どちらかの隣が大きいことが削除可能条件である。

残す位置の順序 操作は削除だけなので AAA は PPP の部分列でなければならない。値 vvv の元の位置を pos[v]\mathrm{pos}[v]pos[v] として

pos[A1]<pos[A2]<⋯<pos[AM]\mathrm{pos}[A_1]<\mathrm{pos}[A_2]<\cdots<\mathrm{pos}[A_M]pos[A1​]<pos[A2​]

を確認する。AAA の重複値もこの検査で除外される。

隙間の条件 残す要素は削除されないため、削除対象は最初の残す要素の左、残す要素同士の間、最後の右の区間に分かれる。別の区間の要素は残す要素を越えて隣接できない。

空でない区間の最大値を ggg、隣接する残す境界要素の大きい方を bbb とする。両端の区間には境界が一つだけある。その区間をすべて消せる必要十分条件は g<bg<bg<b である。

必要性:ggg を消すにはより大きな隣接要素が必要である。区間内には存在しないため残す境界要素でなければならず、b>gb>gb>g が必要。

十分性:区間の要素を小さい順に削除する。二つ以上残っていれば最小の要素は同じ区間の大きい要素と隣接し、削除できる。最後に ggg だけになると b>gb>gb>g の境界と隣接するため削除できる。空区間は常に条件を満たす。

実装 残す要素を順に訪れ、それぞれの前の隙間を一度走査して最大値を求める。存在しない左境界と空区間の最大値は 000 とする。実際の値は正なので同じ比較式で処理できる。最後の接尾部分も確認する。

位置の順序と全区間の条件が成り立つときだけ YES、それ以外は NO。全体最大値 NNN は消せないので AAA に含まれなければ不可能である。ただし最大値を含む部分列であるだけでは不十分。例えば P=[6,1,5,2,3,4]P=[6,1,5,2,3,4]P=[6,1,5,2,3,4], は、 の両境界が なので不可能である。

時間・空間は O(N+M)O(N+M)O(N+M)。位置、値、区間最大値は 200 000200\,000200000 以下で、大きな整数演算は不要である。

サブタスク 1 は残る位置をビットマスクで表し、すべての連続区間操作を BFS で探索する。状態数は 2N2^N2N 以下。区間最小値を逐次更新すれば一状態の操作列挙は O(N2)O(N^2)O(N2) であり、全体は O(2NN2)O(2^N N^2)O(2 時間、 空間。 なら十分である。サブタスク 2 は線形判定を使う。

Solution written by GPT6

<
⋯<
pos[AM​]
A=[6,1,2,3,4]A=[6,1,2,3,4]
A=[6,1,2,3,4]
555
1,21,21,2
N
N2
)
O(2N+N)O(2^N+N)O(2N+N)
N≤10N\leq10N≤10