典型テク: 大小関係のみを考える
概要
たくさんのものの順序について考えるときには、ひとつのものを選んで固定し、それ以外については固定したものとの大小関係のみを考えるとよいことがあります。
$n$ 個のものの順序は $n!$ 通りありますが、$n$ 個のもののそれぞれについてそれ以外の $n - 1$ 個との間の $2^{n-1}$ 通りの大小関係を考えれば全体では $n \cdot 2^{n-1}$ 通りです。 つまり $n!$ の複雑さのものが $n \cdot 2^{n-1}$ の複雑さに落ちます。 具体的な構成が不要で判定のみすればよいとき、ちょうど判定のみをすることができます。 中央値や二分探索と相性がよいです。
例題1: AtCoder Regular Contest 101: D - Median of Medians
以下のような問題です。
長さ $N$ の数列 $a$ があります。 各 $(l, r)$ ($1 \le l \le r \le N$) について、$a$ の連続部分列 $(a_l, a _ {l + 1}, \dots, a_r)$ の中央値を $m _ {l, r}$ とします。すべての $(l, r)$ に対する $m _ {l, r}$ を並べ、新たに数列 $m$ を作ります。$m$ の中央値を求めてください。
解法 (概要)
この問題は答えについての二分探索で解けます。 与えられた $x$ に対して答え $\mathrm{ans}$ が $x$ 以下であるかを判定する必要がありますが、数列 $a$ の要素そのものではなくそれらが $x$ より小さいか大きいかだけを考えるとうまくいきます。 計算量は $O(N \log N \log \max_i a_i)$ です。
解法 (詳細)
与えられた $x$ に対して答え $\mathrm{ans}$ が $x$ 以下であるかを高速に判定できれば十分です。 この判定を考えます。
$\mathrm{ans} \le x$ かどうか判定したい $x$ を固定します。 長さ $N$ の数列 $b$ を $b_i = \begin{cases} 0 & (a_i \le x) \cr 1 & (a_i \gt x) \end{cases}$ で定義します。 各 $(l, r)$ (ただし $1 \le l \le r \le N$) に対し $b$ の連続部分列 $(b_l, b _ {l+1}, \dots, b_r)$ の中央値を $m’ _ {l,r}$ とします。 すべての $(l, r)$ に対する $m’ _ {l,r}$ を並べ、新たに数列 $m’$ を作ります。 このとき $m’$ の中央値が $0$ であることと $\mathrm{ans} \le x$ であることが同値です。
このような $m’$ の値を計算するには、累積和 $c$ (つまり $c_i = \sum _ {j \lt i} b_j$) を用いて適当にします。 組 $(l, r)$ (ただし $1 \le l \le r \le N$) であって $c_r - c_l \ge \lfloor \frac{r - l}{2} \rfloor$ なものの個数が求まればよく、これはセグメント木などで転倒数のようにして $O(N \log N)$ で処理できます。
例題2: AtCoder Grand Contest 006: D - Median Pyramid Hard
以下のような問題です。
$N$ 段のピラミッドがあります。 (中略) すぬけ君は $N$ 段目のブロックに $(1, 2, \dots, 2 N - 1)$ を並べ替えたもの (順列) を書き込みました。 さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。
- あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。
(中略) すぬけ君は、$N$ 段目のブロックに書き込まれた順列が $(a_1, a_2, \dots, a _ {2 N - 1})$ であったことだけを覚えています。 $1$ 段目のブロックに書き込まれた整数を求めてください。
解法 (概要)
この問題も答えについての二分探索で解けます。 与えられた $x$ に対して答え $\mathrm{ans}$ が $x$ 以下であるかを判定する必要がありますが、やはり数列 $a$ の要素そのものではなくそれらが $x$ より小さいか大きいかだけを考えるとうまくいきます。 計算量は $O(N \log N)$ です。
解法 (詳細)
与えられた $x$ に対して答え $\mathrm{ans}$ が $x$ 以下であるかを高速に判定できれば十分です。 この判定を考えます。
$\mathrm{ans} \le x$ かどうか判定したい $x$ を固定します。 長さ $2 N - 1$ の数列 $b$ を $b_i = \begin{cases} 0 & (a_i \le x) \cr 1 & (a_i \gt x) \end{cases}$ で定義します。 この数列 $b$ の値を $N$ 段目のブロックに書き込み、問題文中のルールに従って残りすべてのブロックに $0$ か $1$ を書き込んだとき、$1$ 段目のブロックに書き込まれた整数が $0$ であることと $\mathrm{ans} \le x$ が同値です。
後は数列 $b$ に対してこの問題を解けばよいです。 これは図を書いて観察することによって $O(N)$ で解けます。 詳細は省略します。
例題3: ICPC 2020 国内予選: D - Icpca 文字
以下のような問題です。
先日の Icpca の廃墟の発掘では石壁に刻まれたふたつの式を発見した．
(中略)
古王国とその文明についての多様な知見を総合した分析から，以下の評価規則が判明した．
- (省略)
- 式が文字ひとつからなるとき，その値はその文字そのものである．
- ふたつの式 $P$ と $Q$ の値がそれぞれ $a_i$ と $a_j$ であるとき，式 $(P \lt Q)$ の値は，$a_i$ と $a_j$ のうち全順序で先に来る方の文字である．両者が同じ文字なら値はその文字である．
- 同様に，ふたつの式 $P$ と $Q$ の値がそれぞれ $a_i$ と $a_j$ であるとき，式 $(P \gt Q)$ の値は，$a_i$ と $a_j$ のうち全順序で後に来る方の文字である．両者が同じ文字なら値はその文字である．
発見されたふたつの式の値は等しいはずであることもわかった． 考えられる $n!$ 種の全順序のうち，両式の値が等しくなるような全順序は何種類存在するだろうか．
https://icpc.iisf.or.jp/past-icpc/domestic2020/contest/D_ja.html
つまりは「文字 $a_1, a_2, \dots, a_n$」「二項最小値関数 $\min(P, Q)$」「二項最大値関数 $\max(P, Q)$」から構成されるふたつの式 $S, T$ が与えられたとき、$n$ 個の文字 $a_1, a_2, \dots, a_n$ への順序の入れ方の $n!$ 通りのうち $S$ と $T$ を等しくするものの数を数えよという問題です。
解法
それぞれの文字 $a_i$ ごとに、$S$ と $T$ の両方の値が $a_i$ になるような順序の入れ方を数えます。 $a_i$ を固定したとき残りの $n - 1$ 個の文字のそれぞれが $a_i$ より大きいか小さいかは $2^{n - 1}$ 通りあり、これを全探索します。 $S$ と $T$ の両方の値が $a_i$ で一致したとき、残りの $n - 1$ 個の文字への順序の入れ方は、$a_i$ より小さいとした文字が $k$ 個あるとき $k! \cdot (n - 1 - k)!$ 通りです。 $n \le 16$ であるので $O(n \cdot 2^{n-1} \cdot (\lvert S \rvert + \lvert T \rvert))$ は間に合います。