削除できる要素 が長さ二以上の区間の最小値なら、その区間内に直接隣接する要素が一つ以上あり、それは より大きい。逆に大きい隣接要素があれば、その二要素を区間として を削除できる。従って、現在の左右どちらかの隣が大きいことが削除可能条件である。
残す位置の順序 操作は削除だけなので は の部分列でなければならない。値 の元の位置を として
を確認する。 の重複値もこの検査で除外される。
隙間の条件 残す要素は削除されないため、削除対象は最初の残す要素の左、残す要素同士の間、最後の右の区間に分かれる。別の区間の要素は残す要素を越えて隣接できない。
空でない区間の最大値を 、隣接する残す境界要素の大きい方を とする。両端の区間には境界が一つだけある。その区間をすべて消せる必要十分条件は である。
必要性: を消すにはより大きな隣接要素が必要である。区間内には存在しないため残す境界要素でなければならず、 が必要。
十分性:区間の要素を小さい順に削除する。二つ以上残っていれば最小の要素は同じ区間の大きい要素と隣接し、削除できる。最後に だけになると の境界と隣接するため削除できる。空区間は常に条件を満たす。
実装 残す要素を順に訪れ、それぞれの前の隙間を一度走査して最大値を求める。存在しない左境界と空区間の最大値は とする。実際の値は正なので同じ比較式で処理できる。最後の接尾部分も確認する。
位置の順序と全区間の条件が成り立つときだけ YES、それ以外は NO。全体最大値 は消せないので に含まれなければ不可能である。ただし最大値を含む部分列であるだけでは不十分。例えば , は、 の両境界が なので不可能である。
時間・空間は 。位置、値、区間最大値は 以下で、大きな整数演算は不要である。
サブタスク 1 は残る位置をビットマスクで表し、すべての連続区間操作を BFS で探索する。状態数は 以下。区間最小値を逐次更新すれば一状態の操作列挙は であり、全体は 時間、 空間。 なら十分である。サブタスク 2 は線形判定を使う。
Solution written by GPT6