https://csacademy.com/contest/ioi-2016-training-round-4/summary/
整数$N, K$が与えられる。以下のような性質を持つ長さ$N$の順列の数を$10^9+7$で割ったあまりを出力せよ。
はじめに、$K=1$の場合を考える。$K=1$の場合には、隣り合うペア$N-1$個のなかで($x, x+1$)のように連続した整数になっているものが1つもあってはならない。このような場合の数は、以下のようなDPを考えることで求められる。
$DP[i][j]=[1, i]$の順列のうち、隣接する2数のペアが昇順に連続している箇所が$j$個ある場合の数
遷移は$DP[i][j]$の表す各順列に対して整数$i+1$を挿入する形で行い、これは以下の3種類がある。
$K\gt1$の場合には、順列を分割することによって$K=1$の場合に帰着できる。列 $$1, 2, 3, ..., N-1, N$$ を、各partitionの要素数が$K$を超えないように分割し、このpartitionを並べ替えることで順列を表現することを考える。ここで、各partitionは$K$個以下の要素からなっているので、元々連続していたpartitionを連続させない限りは連続した公差1の部分列の長さが$K$個を超えることがない。これは各partitionを[1, partitionの数]の整数と読み替えた場合の$K=1$の場合に相当する。すべてのpartitionの分け方とその並べ替えを調べれば、連続する公差1の部分列が長さ$K$以下であるようなすべての順列を表現できる。また、分割の仕方が違えば隣り合う連続する整数の組み合わせが異なるので、並び替えによって同じ順列が生成されることもない(ダブルカウントはない)。以上のことから
$part[i][j]=[1, i]$を、各partitionの要素数が$K$を超えないように$j$個に分割する場合の数
を計算する必要があり、これは $$part[i][j]=\sum_{k=i-K}^{i-1} part[k][j-1]$$ のように計算できる。最終的な答えは
$$\sum_{x=1}^{N} \left( part[N][x]\times DP[x][0] \right)$$
となる。
解説AC。発想力が必要で難しいが、面白い問題だと思った。隣り合う要素のペアのうち条件を満たすものを数えるDPは以前も見た。$part$の計算はO($N^2$)の方法があるらしいが、BITを使ってO($N^2\log N$)としてもギリギリで間に合った。
2次元平面上の点($x, y$)が$N$個与えられる。これらの点が以下の性質を満たすかどうかを出力せよ
ある2点($x, y$), ($u, v$)からなる長方形を考える。今、$x\leq u, y\leq v$が満たされているとする。ここで、この長方形の内部および周上に別の点があり、かつその点と($x, y$)からなる長方形の面積が0でないとき(つまり、長方形の内部もしくは上、右の辺上に別の点があるとき)、この点から1つ選んで新たに($u, v$)とする。この操作を可能な限り繰り返すと、($x, y$), ($u, v$)からなる長方形の内部および上、右の辺には別の点がないことになる。
ここで、この長方形が求められる性質を満たすためには、長方形の下もしくは左の辺に別の点が存在する必要があることがわかる。また、どのような($u, v$)に対してもこの性質が満たされるために必要な条件を考える。
($x, y$)より右かつ($x, y$)と同じ$y$座標を持つ点のうちで、もっとも左にある点の座標を($x_{right}, y$)とする。また、($x, y$)より上かつ($x, y$)と同じ$x$座標を持つ点のうちで、もっとも下にある点の座標を($x, y_{up}$)とする。2点($x_{right}, y$), ($x, y_{up}$)からなる長方形の内部に別の点がないならば、点($x, y$)が自身よりも右上の点となす長方形の内部もしくは周上には常に別の点が存在することがいえる。
すべての点について、長方形($x_{right}, y$), ($x, y_{up}$)の内部に点が存在しないことを調べる方法を考える。点を($y, x$)で降順ソートして順に見ていくと、現在調べている点より右上にある点はすべて調べ終わっているという状態になる。ここで、区間($x, x_{right}$)のなかで一番小さい(今まで調べた点の)$y$座標の値が$y_{up}$以上ならば長方形($x_{right}, y$), ($x, y_{up}$)の内部に点が存在しないことがいえる。これは、各$x$座標をノードとして、これまでに見た点のなかで最小の$y$座標を保持するセグメント木(RMQ)を使うことで全体でO($N\log N$)で調べられる。$x_{right}$や$y_{up}$が存在しない場合もあるが、その場合は$\infty$として考えればよい。
以上の方法で、各点について右上にある点となすすべての長方形に別の点が含まれるかどうかを調べることができる。これを同様の手順で左上の点についても行えば、すべての長方形に対して求められる性質を満たすかどうかを調べることができる。
解説AC。なんとなく解けそうという段階で答えを見てしまった。コンテスト中以外に問題に全力で取り組むのは結構難しい……。
$N$要素の数列が与えられる。この数列に対して以下の操作を繰り返してソートするとき、合計コストが$4\times 10^6$を超えないような手順を一つ出力せよ。
隣り合う要素のswapは部分列のreverseの一種であるから、与えられた数列に対してバブルソートを行えば数列をソートすること自体は簡単に可能である。しかし、今回は$N\leq 32000$であるから、O($N^2$)のバブルソートでは目標のコストを達成することができない。よって、より小さいコストで数列をソートする方法を考える必要がある。
はじめに、連続な部分列のreverseのみを使うという条件のもとで、ある値$a$に対して数列を$a$未満の要素と$a$以上の要素に分ける方法を考える。これは以下のようにして再帰的に行うことができる(この操作を、ここでは便宜上sub_routine($a$)と呼ぶことにする)。
数列に対して上記のsub_routineを適用すれば、$a$に対して数列を00...0011...11のような形に並べ替えることができる。この操作は、全体でO($N\log N$)である。
次に、このsub_routineを使って数列をソートすることを考える。これは、以下のように行うことができる(この操作を、main_routineと呼ぶことにする)。
以上のようにすれば、reverseのみを用いて数列のソートができて、時間計算量は全体としてO($N\log^2 N$)となる。数列の各要素がdistinctでない場合には中央値の計算がうまく行かない場合があるが、各要素を($val, idx$)のpairに置き換えれば擬似的にdistinctであるとして考えることができる。
解説AC。なるほどなぁと思った。