ARC 201-300/ARC206D - LIS ∩ LDS - 競技プログラミング用 知識集積所

---

問題

ARC206D

必要知識

簡単な内容は省略

• 特になし

考え方

ほぼ考察が全て。

まず、減少列の長さが1の場合、つまり全部小さい順に並べた場合が混ざるとややこしいので、これを分離する。
つまり、全部小さい順に並べると、K=Nの場合の解答になる。

以下は、数列は減少列の長さが2以上の場合のみ、条件はK<Nの場合のみ考える。

N番目をNにすると、これは必ず増加列の方に含まれ、減少列の方には含まれない（減少列の長さが1の場合だけ例外）。
よって、N-1番目までの良い要素の数がそのままN番目までの良い要素の数となる。
つまり、以下の3パターンを考えればよい。

まず、K≧2の場合。
1からKまでを完全に逆順で並べる。
これにより、1からKまでで良い要素数がK個、減少列の長さが2以上になるので、K+1以上を続きに小さい順で並べればよい。

K=1の場合。
最初の5個を、{2,5,3,1,4}または{4,1,3,5,2}の順で並べる。
その後、6以上を小さい順に並べる。
ただしこれはN≧5でなければいけない点に注意。

K=0の場合。
最初の8個を、{3,4,8,7,2,1,5,6}などの順で並べる。
その後、9以上を小さい順に並べる。
ただしこれはN≧8でなければいけない点に注意。

残った「K=1かつN≦4」または「K=0かつN≦7」の場合は不可能である。
これは、手元で提出とは関係なくプログラムを書いて全探索※で確認するか、数学的に証明するか、ないと信じて一か八かの提出をするか。

解答例

解答例

注意点

K=1かつN=1の場合のコーナーケース※に注意

最初にK=Nである話を分離したが、実はK≧2のパターンにほぼ全て合流できる。
しかし、だからといって完全に消すと、K=1かつN=1の場合だけどこにも合流できずに-1と解答してしまう。
何らかの形でケアすること。

別解