D - Divide Interval Editorial by evima
別解トップダウンに再帰する方針を述べます。(セグメントツリーの再帰的な実装とほぼ同じです。)以下、数列 \(l, l+1, \dots, r-2, r-1\) を \([l, r)\) と書きます。
良い数列 \([l, r)\) に対し、それと入力で与えられた数列 \([L, R)\) の共通部分の最適な分割を \(f(l, r, L, R)\) とします。(共通部分がない場合は考えません。)答えは \(f(0, 2^{60}, L, R)\) です。
\(f(l, r, L, R)\) を再帰的に求めましょう。
- \([l, r)\) の全体が \([L, R)\) に含まれる場合、共通部分は \([l, r)\) で、これ自体が最適な「分割」です。
- そうでない場合、\(m = (l + r) / 2\) とします。ここで、\([l, r)\) の左半分 \([l, m)\) と右半分 \([m, r)\) はともに良い数列です。
- \([L, R)\) の全体が \([l, r)\) の左半分 \([l, m)\) に含まれるなら、つまり \(R \leq m\) なら、右半分は無視でき、最適な分割は \(f(l, m, L, R)\) です。
- \([L, R)\) の全体が \([l, r)\) の右半分 \([m, r)\) に含まれるなら、つまり \(m \leq L\) なら、左半分は無視でき、最適な分割は \(f(m, r, L, R)\) です。
- 上記のどちらでもないなら、\([L, R)\) は \([l, r)\) の左半分と右半分の双方と共通部分を持ち、 最適な分割は \(f(l, m, L, R)\) と \(f(m, r, L, R)\) を連結したものです。
これを再帰関数として実装して \(f(0, 2^{60}, L, R)\) を呼んだ際の再帰呼び出しの回数は、各層(公式解説の図を参照)で \(4\) 回以下、合計で \(60 \times 4\) 回以下です。
実装例(Python)
def f(l, r, L, R):
if L <= l and r <= R:
return [(l, r)]
m = (l + r) // 2
if R <= m:
return f(l, m, L, R)
if m <= L:
return f(m, r, L, R)
return f(l, m, L, R) + f(m, r, L, R)
L, R = map(int, input().split())
ans = f(0, 1 << 60, L, R)
print(len(ans))
for l, r in ans:
print(l, r)
posted:
last update: