codeforces #502 C ~The Phone Number~

背景が面白い問題だったのでつい投稿。嘘を書いていたら教えてください。
問題要約
長さ $n$ のpermutationのうち，最長増加部分列(LIS)の長さと最長減少部分列(LDS)の長さの和が最小になるものを1つ出力せよ。
https://codeforces.com/contest/1017/problem/C

本番はエスパーして解いたので，解説を見たところこう書いてあった。

You can use [Dilworth's theorem]https://en.wikipedia.org/wiki/Dilworth So assume we've already known that $LIS=L$ ,then we can achieve $LDS=\lceil \frac{n}{L} \rceil$ .

なんでや。

ということで詳しく調べてみた。
まず，いくつか準備。
定義(最小被覆パス)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の最小被覆パスとは，パスの集合の組 $P_1,\dots P_k$ であって，これらが $V$ の分割になっているようなもの(すべての頂点 $v\in V$ に対して，ある $P_i$ がただ1つあって， $v\in P_i$ )のうち， $k$ が最小のものである。

定義(反鎖)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の反鎖(antichain)とは， $V$ の部分集合 $P$ であって， $P$ の任意の2要素の間にパスがないもののことである。
本来この語は半順序集合に定義されるもののようだが，閉路をもたない有向グラフは半順序集合とみなせる(と思う)ので，ここではグラフで定義をしても差し支えない。

Dilworthの定理とは以下のようなものらしい。
定理(Dilworth)
閉路をもたない有向グラフ $G(V,E)$ における最小被覆パスの大きさ(上の定義でいうところの $k$ )と， $G$ の最大の反鎖の大きさは等しい。
証明は(https://en.wikipedia.org/wiki/Dilworth%27s_theorem)を参照。こちらは半順序集合の言葉で話を進めているので注意。

LISとLDSに話を戻そう。長さ $n$ のpermutationを $p_1,p_2,\dots,p_n$ とする。このとき，頂点集合を $\{p_1,p_2,\dots,p_n\}$ として，グラフを作る。 $p_i,p_j (1\leq i.j\leq n)$ について， $p_i\lt p_j$ かつ $i\lt j$ のときに $p_i$ から $p_j$ に辺を張る。このグラフを $G(V,E)$ とすると，LISの長さ $L$ は $G$ の最長のパスの長さであり，LDSの長さ $K$ は最大の反鎖の大きさになる。これが肝である。
こんな感じ。
f:id:sigma1113:20180809202306j:plain

LISの長さが $L$ のとき， $K=\lceil \frac{n}{L} \rceil$ が最小であることを示そう。Dilworthの定理より， $K$ は $G(V,E)$ の最小被覆パスの大きさに等しい。ここで，LISの長さが $L$ であることから，最小被覆パスを構成するパスたち $P_1,P_2,\dots,P_K$ のそれぞれの大きさは高々 $L$ である。すると， $KL\geq n$ ，つまり $K\geq \lceil \frac{n}{L} \rceil$ が成り立つ。この下界は達成できる。実際， $L(K-1)+1,L(K-1)+2,\dots,n,L(K-2)+1,L(K-2)+2,\dots,L(K-1),\dots\dots,L+1,L+2,\dots,2L,1,2,\dots,L$ がそうなっている。