I - Which must be deleted? Editorial by maspy
\(O(N\log N)\) 時間での解法を説明します.
(
, )
を \(+1\), \(-1\) に対応させて,入力は \((+1, -1)\) の列として扱います.次のような問題になります.
各 \(i\) に対して \(L_i, R_i\) のどちらかを \(0\) に変更して,任意の prefix sum が非負かつ総和が \(0\) にせよ
まず,\(S_{L_i} = S_{R_i}\) であるような \((L_i, R_i)\) については貪欲な選択肢が決まります.
\(S_{L_i} = -1, S_{R_i}=1\) であるような \((L_i, R_i)\) については次のように考えます:
- \(S_{L_i} = -1\), \(S_{R_i} = 0\) で初期化しておく.このあと,次の操作を \(0\) 回または \(1\) 回行える:\(S_{L_i}, S_{R_i}\) の両方に \(+1\) する.
\(S_{L_i} = 1, S_{R_i}=-1\) であるような \((L_i, R_i)\) についても同様にします.次の問題に帰着できました:
数列 \(A\) と,いくつかの組 \((L_i, R_i)\) が与えられる.「\(A_{L_i}, A_{R_i}\) に \(+1\) する」という選択をいくつかの \(i\) に行って,\(A\) の prefix sum が非負かつ総和が \(0\) になるようにせよ.
これは,次のような貪欲アルゴリズムで判定可能です.
\(i=0, 1, 2, \ldots\) 順に prefix sum を計算していく.prefix sum が負になったら,\(L\leq i\) であるような未使用の組 \((L,R)\) であって \(R\) が最小のものを選んで操作を行う.操作が行えないならば
No
を出力する.
posted:
last update: