AtCoder Grand Contest 057 の B 問題の考察

AGC057 に Unrated 参加してきました。AB 2完（1 WA）で順位は195位とのこと。

B 問題を解いているうちに「あれ、計算量どうやって減らすんだ...？」と十数分悩んだのち、解けたときすごい感動しちゃったので記事残しておきます。
~~解説ではしれっと２行くらいで流されている内容なんですけどね。~~

B 問題のリンクと atcoder.jp

B 問題の解説へのリンクです。 atcoder.jp

解説にもある以下の部分問題に関する記事です。

$a$ 以下の整数列 $(L_{1}, L_{2}, \dots , L_{N})$ および、 $a$ 以上の整数列 $(R_{1}, R_{2}, \dots , R_{N})$ が与えられる。各 $i = 1, 2, \dots, n$ に対し、 $A_{i} = L_{i}$ または $A_{i} = R_{i}$ が成り立つように整数列 $A = (A_{1}, A_{2}, \dots , A_{N})$ を構成する。
このとき $max(A) - min(A)$ がとりうる値の最小値を求めよ。

なにも考えないと $L_{i}$ か $R_{i}$ どちらを採用するかで、計算量 $O(2^{N})$ でこの部分問題が解けることがわかります。 $N \leq 10^{5}$ なので、まあ間に合わないです。

これがなんと計算量 $O(N)$ まで落とせるという。
※ 厳密には、前処理に $O(N log(N))$ かかるので、そちらが律速になります。

これを導出するために、以下の考察を行います。

は、以下のどちらかを満たす。
- $min(A) = L_{i}$ を満たす $i$ が存在する。
- $min(A) = min(R_{1}, R_{2}, \dots, R_{N})$
を満たすが存在する場合、以下が成り立つ。
- について、であるならば、である。
  - を満たすが存在する場合、さらに以下が成り立つ。
    - $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ 　※ 当記事ではここを後で深堀りします
    - 等号成立条件は、 $j = 1, 2, \dots, n$ について、 $L_{j} \lt L_{i} \Leftrightarrow A_{j} = R_{j}$ のとき。
  - を満たすが存在しない場合、さらに以下が成り立つ。
    - $max(A) = max(L_{1}, L_{2}, \dots, L_{N})$ 　
    - また、 $min$ の定義より、 $L_{i} = min(L_{1}, L_{2}, \dots, L_{N})$
が成り立つ場合、以下が成り立つ。
- $max(A) = max(R_{1}, R_{2}, \dots, R_{N})$

この考察から、 $max(A) - min(A)$ の値は以下の３パターンのいずれかになります。

$max(L_{1}, L_{2}, \dots, L_{N}) - min(L_{1}, L_{2}, \dots, L_{N})$
$max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace) - L_{i}$
$max(R_{1}, R_{2}, \dots, R_{N}) - min(R_{1}, R_{2}, \dots, R_{N})$

事前に $(L_{1}, L_{2}, \dots, L_{N})$ が昇順になるように、 $(L_{1}, L_{2}, \dots, L_{N})$ と $(R_{1}, R_{2}, \dots, R_{N})$ をソートしておけば、 $max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace) = max(R_{1}, R_{2}, \dots, R_{i-1})$ となり、累積 max を取ることで高速に取得することができます。

前処理のソートの計算量が $O(N log(N))$ 、累積 max を取っていくところの計算量は $O(N)$ となります。

Python で書くとこんな感じ。

l = [l1, l2, ..., ln]
r = [r1, r2, ..., rn]
# l を昇順にソートする。r は l のソートにあわせて並び替える。
l, r = list(zip(*sorted(list((li, ri) for li, ri in zip(l, r)))))

ans = float("inf")

# 全部 l[i] を採用する場合
upper = max(l)
lower = min(l)
ans = min(ans, upper - lower)

# r[1], r[2], ..., r[i], l[i+1], l[i+2], ...., l[n] を採用する場合
for i in range(n-1):
  upper = max(upper, ri)
  lower = l[i+1]
  ans = min(ans, upper - lower)

# 全部 r[i] を採用する場合
upper = max(r)
lower = min(r)
ans = min(ans, upper - lower)

print(ans)

さて、考察にあった $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ の深堀りの時間です。
この不等式にたどり着くために、まず以下の事実を挙げておきます。

関数 $max \colon 2^{\mathbb{R}} \rightarrow \mathbb{R}$ について、以下が成り立つ。
$P \subseteq Q \in 2^{\mathbb{R}}$ となる $P, Q$ について、 $max(P) \leq max(Q)$

また、同様に
関数 $min \colon 2^{\mathbb{R}} \rightarrow \mathbb{R}$ について、以下が成り立つ。
$P \subseteq Q \in 2^{\mathbb{R}}$ となる $P, Q$ について、 $min (P) \geq min (Q)$

このことから、考察の $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ が
$L_{j} \lt L_{i} \Rightarrow A_{j} = R_{j}$ より $A \supseteq \lbrace R_{j} | L_{j} \lt L_{i} \rbrace$ であることから導出できます。
※ しれっと $A$ を集合にしているのにはご容赦。

この性質によって、max や min の上界・下界を求めることができました。

他の関数や、集合でも似た議論ができます。先ほどの max や min の性質を少し抽象化して、以下のような性質を考えてみます。

集合 $S$ と順序構造 $(P, \preceq )$ が存在し、ある関数 $f \colon 2^{S} \rightarrow P$ について、以下が成り立つ。
$A \subseteq B \in 2^{S}$ となる $A, B$ について、 $f(A) \preceq f(B)$

順序構造にもいろいろ強さがありますが、 $A \subseteq B \in 2^{S}$ であるときに $f(A)$ と $f(B)$ の順序関係が保証されるような $\prec$ であれば、どんな $\prec$ でもよいかと思います。

具体例としては、こんな感じですかね。

例１
- 集合 $S$ は何でも OK
- 順序構造は $(\mathbb{N}, \leq)$
- 関数 $f$ は、集合の要素数を返す関数
例２
- 集合 $S$ は有向木上のノード
- 順序構造はで、ノード間に親子関係が成り立つとき、子ノード親ノード。
  - ２ノード間に親子関係がないこともあるので、これは半順序構造です。
- 関数 $f$ は、最近共通祖先を返す関数