AtCoder Grand Contest 057 の B 問題の考察

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

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

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) は、以下のどちらかを満たす。
    •  min(A) = L_{i} を満たす  i が存在する。
    •  min(A) = min(R_{1}, R_{2}, \dots, R_{N})
  •  min(A) = L_{i} を満たす  i が存在する場合、以下が成り立つ。
    •  j = 1, 2, \dots, n について、 L_{j} \lt L_{i} であるならば、 A_{j} = R_{j} である。
      •  L_{j} \lt L_{i} を満たす  j が存在する場合、さらに以下が成り立つ。
        •  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} のとき。
      •  L_{j} \lt L_{i} を満たす  j が存在しない場合、さらに以下が成り立つ。
        •  max(A) = max(L_{1}, L_{2}, \dots, L_{N}) 
        • また、 min の定義より、 L_{i} = min(L_{1}, L_{2}, \dots, L_{N})
  •  min(A) = min(R_{1}, R_{2}, \dots, R_{N}) が成り立つ場合、以下が成り立つ。
    •  max(A) = max(R_{1}, R_{2}, \dots, R_{N})

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

  •  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 でもよいかと思います。

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

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

他にも、意外な例があるかもしれないです。誰か閃いた方教えてください。

この性質を使うことで、 f の値域の上界・下界を賢くもとめることができました。
既に名前がついている性質だったり? ご存じの方はコメントか、Twitter の方にでも投げていただけると嬉しいです。

(2022年6月28日追記)
単調性でよさそうでした。