ヒント

解法

順列全体の最長増加部分列の長さを \(L\) と書きます。各位置 \(i\) に対し、そこが末尾であるような最も長い増加部分列の長さ \(f(i)\) を予め計算しておきましょう。

\(L\) が偶数なら、題意を満たす分割は常に可能です。これは、\(f(i)\le \frac{L}{2}\) であるような \(i\) を一方の部分列に全て含め、残り全てをもう一方に含めることにより行えます。これらの部分列の最長増加部分列の長さがともに \(\frac{L}{2}\) であることは明らかです。

\(L = 2K+1\) のとき、どのように分割を行っても、少なくとも一方の部分列は長さ \(K+1\) 以上の増加部分列を含むため、どちらの部分列も最長増加部分列の長さが \(K+1\) 以上でなければなりません。順列全体の最長増加部分列（長さ \(2K+1\)）のうち任意の一つについて考えます。このとき、この列に含まれない要素であって、長さ \(K+1\) 以上の増加部分列に含まれるものが存在しなければ題意を満たせません。

逆に、それが存在すれば十分であることが分かります。実際に、位置 \(x\) の要素が、順列全体の最長増加列に含まれないものの、長さ \(K+1\) の増加部分列に含まれるとします。この部分列の要素の位置を \(i_1, \dots, i_{K+1}\) として、順列を以下のように分割します。

• $f(i)$ が $f(i_1), f(i_2), \dots, f(i_{K+1})$ のいずれとも異なるなら、位置 $i$ の要素は第一の部分列に含める。
• $f(i) = f(x)$ かつ $i\neq x$ であるなら、位置 $i$ の要素は第一の部分列に含める。
• その他の要素は全て第二の部分列に含める。

第二の部分列は、位置 \(x\) の要素を含む長さ \(K+1\) の件の増加部分列を含みますが、より長い増加列を含むことはありません。第一の部分列は順列全体の最長増加部分列から \(K+1\) 個の要素を受け継ぎますが、こちらもより長い増加列を含むことはありません。

順列全体の最長増加列に含まれないものの、長さ \(K+1\) の増加部分列に含まれる要素が存在するかを判定するには、各要素についてその要素を末尾とする最も長い増加部分列やその要素を先頭とする最も長い増加部分列の長さを計算します。そして、これら \(2\) つの値の和が \(K+2\) 以上であるような要素が \(2K+2\) 個以上存在すれば、答えは YES です。