AGC057 に Unrated 参加してきました。AB 2完(1 WA)で順位は195位とのこと。
B 問題を解いているうちに「あれ、計算量どうやって減らすんだ...?」と十数分悩んだのち、解けたときすごい感動しちゃったので記事残しておきます。
解説ではしれっと2行くらいで流されている内容なんですけどね。
B 問題のリンクと
atcoder.jp
B 問題の解説へのリンクです。
atcoder.jp
解説にもある以下の部分問題に関する記事です。
以下の整数列
および、
以上の整数列
が与えられる。
各
に対し、
または
が成り立つように整数列
を構成する。
このとき
がとりうる値の最小値を求めよ。
なにも考えないと
か
どちらを採用するかで、計算量
でこの部分問題が解けることがわかります。
なので、まあ間に合わないです。
これがなんと計算量
まで落とせるという。
※ 厳密には、前処理に
かかるので、そちらが律速になります。
これを導出するために、以下の考察を行います。
は、以下のどちらかを満たす。
を満たす
が存在する場合、以下が成り立つ。
について、
であるならば、
である。
を満たす
が存在する場合、さらに以下が成り立つ。
※ 当記事ではここを後で深堀りします
- 等号成立条件は、
について、
のとき。
を満たす
が存在しない場合、さらに以下が成り立つ。
が成り立つ場合、以下が成り立つ。
この考察から、
の値は以下の3パターンのいずれかになります。
事前に
が昇順になるように、
と
をソートしておけば、
となり、累積 max を取ることで高速に取得することができます。
前処理のソートの計算量が
、累積 max を取っていくところの計算量は
となります。
Python で書くとこんな感じ。
l = [l1, l2, ..., ln]
r = [r1, r2, ..., rn]
l, r = list(zip(*sorted(list((li, ri) for li, ri in zip(l, r)))))
ans = float("inf")
upper = max(l)
lower = min(l)
ans = min(ans, upper - lower)
for i in range(n-1):
upper = max(upper, ri)
lower = l[i+1]
ans = min(ans, upper - lower)
upper = max(r)
lower = min(r)
ans = min(ans, upper - lower)
print(ans)
さて、考察にあった
の深堀りの時間です。
この不等式にたどり着くために、まず以下の事実を挙げておきます。
関数
について、以下が成り立つ。
となる
について、
また、同様に
関数
について、以下が成り立つ。
となる
について、
このことから、考察の
が
より
であることから導出できます。
※ しれっと
を集合にしているのにはご容赦。
この性質によって、max や min の上界・下界を求めることができました。
他の関数や、集合でも似た議論ができます。先ほどの max や min の性質を少し抽象化して、以下のような性質を考えてみます。
集合
と 順序構造
が存在し、ある関数
について、以下が成り立つ。
となる
について、
順序構造にもいろいろ強さがありますが、
であるときに
と
の順序関係が保証されるような
であれば、どんな
でもよいかと思います。
具体例としては、こんな感じですかね。
- 例1
- 集合
は何でも OK
- 順序構造は

- 関数
は、集合の要素数を返す関数
- 例2
- 集合
は有向木上のノード
- 順序構造は
で、ノード間に親子関係が成り立つとき、子ノード
親ノード。
- 2ノード間に親子関係がないこともあるので、これは半順序構造です。
- 関数
は、最近共通祖先を返す関数
他にも、意外な例があるかもしれないです。誰か閃いた方教えてください。
この性質を使うことで、
の値域の上界・下界を賢くもとめることができました。
既に名前がついている性質だったり? ご存じの方はコメントか、Twitter の方にでも投げていただけると嬉しいです。
(2022年6月28日追記)
単調性でよさそうでした。