L - 最長のジグザグ / Longest ZigZag Editorial
by 
Tomii9273
時間計算量 \(O(N)\) の解法です。
ある \(i\) \((1 \leq i \leq N-1)\) について \(B_i = B_{i+1}\) のとき、\(B\) の部分列であるジグザグ列に \(B_i\) と \(B_{i+1}\) の両方が使われることはないため、数列から \(B_i\) を除外しても答えは変わりません。
このような \(B_i\) を事前にすべて除外しておきます。
この時点で数列 \(B\) の長さが \(1\) のとき答えは明らかに \(1\) であるため、以降では長さが \(2\) 以上の場合のみを考えます。
以降では、整数列 \(P=(P_1, \ldots,P_n)\) において、
- \(P_{i-1} < P_{i} > P_{i+1}\) \((2 \leq i \leq n-1)\) を満たす \(P_i\) を \(P\) の極大値
- \(P_{i-1} > P_{i} < P_{i+1}\) \((2 \leq i \leq n-1)\) を満たす \(P_i\) を \(P\) の極小値
- \(P_1\) と \(P_{n-1}\) と極大値または極小値である \(P_i\) を \(P\) の良い成分
と呼ぶことにします。
実は、\(B\) の良い成分の個数が答えです。
\(B\) の良い成分をすべて使用した数列がジグザグ列になることは定義より明らかなので、それを超える長さのジグザグ列が得られないことを示します。
ここで、以下が成り立ちます。
\(B\) の部分列であるジグザグ列は、その長さを保ったまま、\(B\) の部分列でありかつ良い成分のみからなるジグザグ列に変換できる。
証明
\(B\) の部分列であるジグザグ列の長さが \(1\) のときは自明なので、長さが \(2\) 以上の場合について示す。
ジグザグ列を \(A=(A_1, \ldots,A_m)\) \((m \geq 2)\) とする。
ここで、任意の成分 \(A_i\) について、以下のいずれかが成り立つ。
- (A1) \((i \geq 2 かつ A_{i-1} < A_{i}) または (i \leq N-1 かつ A_{i} > A_{i+1})\)
- (A2) \((i \geq 2 かつ A_{i-1} > A_{i}) または (i \leq N-1 かつ A_{i} < A_{i+1})\)
\(A_i = B_j\) とすると、\(B_j\) が良い成分でない場合、以下のいずれかが成り立つ。
- (B1) \(B_{j-1} < B_{j} < B_{j+1}\)
- (B2) \(B_{j-1} > B_{j} > B_{j+1}\)
良い成分でない \(B_j\) について、以下の操作をすることで、良い成分にすることができる。
- (A1) かつ (B1) が成り立つ場合、 \(B_{j}\) の代わりに \(B_{j+1}\) を使用しても (A1) は成り立つ。これを (B1) が成り立たなくなるまで繰り返す。
- (A1) かつ (B2) が成り立つ場合、 \(B_{j}\) の代わりに \(B_{j-1}\) を使用しても (A1) は成り立つ。これを (B2) が成り立たなくなるまで繰り返す。
- (A2) かつ (B1) が成り立つ場合、 \(B_{j}\) の代わりに \(B_{j-1}\) を使用しても (A2) は成り立つ。これを (B1) が成り立たなくなるまで繰り返す。
- (A2) かつ (B2) が成り立つ場合、 \(B_{j}\) の代わりに \(B_{j+1}\) を使用しても (A2) は成り立つ。これを (B2) が成り立たなくなるまで繰り返す。
\(B\) の部分列であり、\(B\) の良い成分の個数を超える長さのジグザグ列が存在すると仮定すると、上記の変換をする際に矛盾が生じます。
したがって、\(B\) の良い成分の個数を超える長さのジグザグ列は得られません。
\(B\) の各成分が良い成分かどうかは時間計算量 \(O(N)\) で判定できます。
posted:
last update: