LIS、LDSの性質より、

• \(A,B\) は広義単調増加

• \(A_1, B_1 = 1, (A_{i + 1} - A_i) + (B_{i + 1} - B_i) \leq 1\)

が満たされる必要があります。 また、

\(X_i = (C_i で終わるCの単調増加部分列の長さの最大値) \) ,

\(Y_i = (C_i で終わるCの単調減少部分列の長さの最大値) \)

と定義します。そして \((X_i,Y_i) = (X_j,Y_j) (i < j)\)を満たす\(i,j\) が存在すると仮定すると、\(C_i < C_j\)ならば\(X\)が、\(C_i > C_j\)ならば\(Y\)が矛盾するので存在しません。 ここで順列の要素をグリッド上のマス\((X_i, Y_i)\) に埋め込むことを考えます、そうすると、グリッドのあるマス\((i, j)\)に要素が埋め込まれているならば\((max(0, i - 1), j)\)と\((i, max(0, j- 1))\)にも埋まっている必要があり、そこから

• \( i \leq X_i \times Y_i\)

が導け、これらが必要条件となります、そしてこれを満たすものはすべて構築できます 先ほどのマス目に要素を埋め込みながら\(C\)を構成することを考えると、\(A,B\)が増加する際はグリッドの端をそれぞれ伸ばしながら構成すればよく、復元する際は、マス \((i,j)\)に対して、\(i = 1\)なら下側、そうじゃないかつ \(j = 1\) なら上側、それ以外はグリッドを伸ばす時に伸ばした範囲のものをそれぞれ上、下に追加した列を持っておいて、小さい方から貪欲に埋めていくと\(O(N)\)で動き、条件をすべて満たすことが示せます。

• おまけ

コンテスト直前に気づいたのですが、えびまさんがIMO2025-p6の解説をしている動画でこの補題を示し似たような考察をしていたので半分くらい既出の考察になってしまったかもしれません。すみません。IMO2025-p6もとてもいい問題なので解いてみてください