https://www.acmicpc.net/problem/12825
以下の条件を満たす $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ を 312-avoid と呼びます。
- $1 \le i < j < k \le N$ を満たす全ての整数組 $(i,j,k)$ について、 $P_j < P_k < P_i$ となることがない。
312-avoid な順列 $P$ が与えられるので、辞書順で $P$ より大きい 312-avoid な順列のうち辞書順で最小のものを求めよ。
$1 \le N \le 10000$
$P \neq (N,N-1,\dots,1)$
問題文に謎の指定があるが、以下の問題が解ければよい。 (初手で $P$ に next_permutation をかけると帰着できる)
順列 $P$ が与えられるので、辞書順で $P$ 以上の 312-avoid な順列のうち辞書順で最小のものを求めよ。
312-avoid な順列というのがかなり雲を掴んでいるので、実験してみる。
3 :
0 1 2
0 2 1
1 0 2
1 2 0
2 1 04 :
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 2 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 05 :
0 1 2 3 4
0 1 2 4 3
0 1 3 2 4
0 1 3 4 2
0 1 4 3 2
0 2 1 3 4
0 2 1 4 3
0 2 3 1 4
0 2 3 4 1
0 2 4 3 1
0 3 2 1 4
0 3 2 4 1
0 3 4 2 1
0 4 3 2 1
1 0 2 3 4
1 0 2 4 3
1 0 3 2 4
1 0 3 4 2
1 0 4 3 2
1 2 0 3 4
1 2 0 4 3
1 2 3 0 4
1 2 3 4 0
1 2 4 3 0
1 3 2 0 4
1 3 2 4 0
1 3 4 2 0
1 4 3 2 0
2 1 0 3 4
2 1 0 4 3
2 1 3 0 4
2 1 3 4 0
2 1 4 3 0
2 3 1 0 4
2 3 1 4 0
2 3 4 1 0
2 4 3 1 0
3 2 1 0 4
3 2 1 4 0
3 2 4 1 0
3 4 2 1 0
4 3 2 1 0
観察した結果、以下が言える。
- 312-avoid な順列全体の集合と、以下の手順で生成できる順列全体の集合とは一致する。
- まず、 $1$ 以上 $N$ 以下の整数 $x$ を好きに選んで $P=(x)$ から始める。
- その後、以下の手順を $i=1,2,\dots,N-1$ について繰り返す。
- $P$ の末尾に、以下の条件を満たす要素を付け加える。
- 集合 $S$ を、現在の $P$ に含まれていない $1$ 以上 $N$ 以下の整数の集合とする。
- $l$ を、 $S$ 中の $P_i$ 未満の要素のうち最大のものとする。そのようなものがなければ $l=-1$ とする。
- このとき、 $x$ が $x \in S$ かつ $x \ge l$ を満たす、またその時に限って付け加えることができる。
ざっくり言うと、値が増える時は好き勝手にして良く、値が減る時はそのような要素のうち最大のものしか付け加えられない。
証明は次の通り。
必要性:
もし $l$ 未満の要素 $m $ を付加したとすると、それ以降に $l$ を付加することになる。このとき、 $(P_i,m,l)$ という部分列が存在してこれが 312 型になってしまうので不適。
十分性:
ある 312 型の部分列 $(x,y,z)$ が存在すると仮定する。
$x$ を付加した後に $y,z$ ( $y<z$ ) をこの順に付加することになるが、 $y,z < x$ である。
「下る時は下れる最大の要素しか付加できない」という縛りがあるので、必ず $y$ の前に $z$ が付加されることになるので、矛盾。よって、そのような部分列は存在しない。
よって、生成方法を暴き出すことができた。
あとは、(帰着した問題での)順列 $P$ を先頭から舐めていき、
- $P$ の接頭辞が上記の生成法で生成できる限り、それを採用する。
- 接頭辞が生成できるなら、そのような接頭辞から常に 312-avoid な順列が一つ以上生成できることに注意
- $P$ の接頭辞が上記の生成法で生成できなくなれば(下がりすぎている状態)、そこからは貪欲に付加できる最小の要素を付加することを繰り返せばよい。
必要十分条件を「生成法」のように表現してそこから解いていくという流れは典型だが、その流れが綺麗に適用できたのでメモ。
