K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-high概要
長さ \(K\) の連続区間を 1 つ選ぶとき、駐車スペース付き区画数が条件を満たすものの中で、賃料合計の最小値を求めます。
賃料 \(A_i\) は更新されますが、駐車スペースの有無 \(C_i\) は変化しない点を利用します。
考察
長さ \(K\) の区間の開始位置を \(i\) とします。
- \(S_i\)：開始位置 \(i\) の長さ \(K\) 区間の賃料合計
- \(P_i\)：開始位置 \(i\) の長さ \(K\) 区間に含まれる駐車スペース付き区画数
とします。
すると、質問 \(X\) に対する答えは
\[ P_i \geq X \]
を満たす区間の中での
\[ S_i \]
の最小値です。
ここで重要なのは、\(C_i\) は更新されないため、各区間の \(P_i\) は最初から最後まで変わらないことです。
一方、賃料 \(A_i\) が更新されると、それを含む長さ \(K\) の区間すべての \(S_i\) が同じ差分だけ変化します。
例えば、\(A_x\) が \(d\) だけ変化したとします。
このとき影響を受ける区間の開始位置 \(i\) は
\[ i \leq x \leq i+K-1 \]
を満たすものです。
つまり、開始位置 \(i\) はある連続範囲になります。
したがって更新は、配列 \(S\) に対する「区間加算」として扱えます。
問題は次の形に言い換えられます。
- 配列 \(S_i\) に対して区間加算を行う
- 固定された値 \(P_i\) について、\(P_i \geq X\) を満たす \(i\) の中での \(S_i\) の最小値を求める
素朴に各質問で全区間を調べると \(O(N)\) かかり、最大で \(5 \times 10^9\) 程度の処理になってしまうため間に合いません。
そこで、開始位置を平方分割して管理します。
アルゴリズム
長さ \(K\) の区間は全部で
\[ M = N-K+1 \]
個あります。
まず、各開始位置 \(i\) について
- 賃料合計 \(S_i\)
- 駐車スペース数 \(P_i\)
を尺取りのようにスライドしながら \(O(N)\) で求めます。
その後、開始位置 \(0,1,\dots,M-1\) をブロックに分けます。
各ブロックについて、以下を持ちます。
- そのブロック内の開始位置を \(P_i\) の昇順に並べた配列
- 並べた順に見たときの \(P_i\)
- 後ろからの最小値配列
例えば、あるブロックの \(P_i\) が昇順に
\[ [0, 1, 3, 3] \]
で、それに対応する \(S_i\) が
\[ [8, 5, 10, 7] \]
だったとします。
このとき後ろからの最小値は
\[ [5, 5, 7, 7] \]
です。
質問で「\(P_i \geq 2\)」が来た場合、二分探索で最初に \(P_i \geq 2\) となる位置を探します。
この例では \(P_i=3\) の位置から見ればよいので、答え候補は \(7\) です。
更新処理
賃料 \(A_x\) を \(Y\) に変更するとします。
差分を
\[ d = Y - A_x \]
とします。
この \(d\) は、\(x\) を含む長さ \(K\) の区間すべてに加算されます。
つまり、\(S_i\) に対してある連続範囲への区間加算を行います。
平方分割では、更新範囲を次のように扱います。
- 範囲に完全に含まれるブロック
→ ブロック全体に同じ値を足すだけなので、遅延加算として記録する - 範囲の端にある一部だけ含まれるブロック
→ 実際に各 \(S_i\) を更新し、そのブロックの後ろからの最小値配列を作り直す
これにより、1 回の更新で作り直す必要があるのは高々 2 ブロックだけです。
質問処理
質問 \(X\) に対して、各ブロックを見ます。
あるブロックについて、
- ブロック内の最大 \(P_i\) が \(X\) 未満なら、そのブロックには条件を満たす区間がない
- そうでなければ、\(P_i\) の昇順配列に対して二分探索し、最初に \(P_i \geq X\) となる位置を探す
- そこから後ろの \(S_i\) の最小値を、後ろからの最小値配列で取得する
- ブロック全体への遅延加算分を足す
これを全ブロックについて行い、最小値を答えます。
また、全体での最大駐車スペース数を max_parking として持っておけば、\(X > \text{max\_parking}\) の質問は即座に IMPOSSIBLE と判定できます。
計算量
\(M=N-K+1\)、ブロックサイズを \(B\)、更新回数を \(U\)、有効な質問回数を \(R\) とします。
- 初期計算: \(O(N)\)
- 各ブロックのソート: \(O(M \log B)\)
- 1 回の更新: \(O(B)\)
- 1 回の質問: \(O\left(\frac{M}{B}\log B\right)\)
したがって全体では
\[ O\left(N + M\log B + UB + R\frac{M}{B}\log B\right) \]
です。
ブロックサイズをおよそ \(\sqrt{M}\) にすれば、典型的には
\[ O\left((N+Q)\sqrt{N}\log N\right) \]
程度で動作します。
- 時間計算量: \(O\left(N + M\log B + UB + R\frac{M}{B}\log B\right)\)
- 空間計算量: \(O(M)\)
実装のポイント
- 長さ \(K\) の区間和 \(S_i\) と駐車スペース数 \(P_i\) は、スライドしながら \(O(N)\) で求めます。
- 更新で影響を受ける開始位置の範囲は、0-indexed で考えると
$\( [x-K+1, x] \)$
を配列範囲内に収めたものです。
各ブロックでは \(P_i\) の順番は変わりません。
変わるのは \(S_i\) だけなので、更新後もソートし直す必要はありません。ブロック全体に同じ値を足した場合、最小値を取る位置は変わらないため、遅延加算として管理できます。
部分的に更新されたブロックだけ、後ろからの最小値配列を再計算します。
\(X > \text{max\_parking}\) の場合は、条件を満たす区間が存在しないので即座に
IMPOSSIBLEを出力できます。ソースコード
import sys
from bisect import bisect_left
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
p = 0
N = data[p]
K = data[p + 1]
Q = data[p + 2]
p += 3
A = data[p:p + N]
p += N
C = data[p:p + N]
p += N
op_start = p
op_end = op_start + 3 * Q
M = N - K + 1
vals = [0] * M
s = sum(A[:K])
vals[0] = s
for i in range(1, M):
s += A[i + K - 1] - A[i - 1]
vals[i] = s
cnt = [0] * M
c = sum(C[:K])
cnt[0] = c
for i in range(1, M):
c += C[i + K - 1] - C[i - 1]
cnt[i] = c
max_parking = max(cnt)
upd_count = 0
possible_query_count = 0
for i in range(op_start, op_end, 3):
if data[i] == 1:
upd_count += 1
else:
if data[i + 1] <= max_parking:
possible_query_count += 1
if possible_query_count == 0:
out = []
for i in range(op_start, op_end, 3):
if data[i] == 2:
out.append("IMPOSSIBLE")
sys.stdout.write("\n".join(out))
return
if upd_count == 0:
B = M
else:
B = int((2.0 * possible_query_count * M / upd_count) ** 0.5) + 1
if B < 16:
B = 16
if B > M:
B = M
nb = (M + B - 1) // B
INF = 10 ** 30
starts = [0] * nb
ends = [0] * nb
orders = []
cnt_blocks = []
sufs = []
min_counts = [0] * nb
max_counts = [0] * nb
getcnt = cnt.__getitem__
for b in range(nb):
st = b * B
en = st + B
if en > M:
en = M
starts[b] = st
ends[b] = en
idxs = list(range(st, en))
idxs.sort(key=getcnt)
cs = [cnt[i] for i in idxs]
sf = [0] * (en - st)
cur = INF
for j in range(len(idxs) - 1, -1, -1):
v = vals[idxs[j]]
if v < cur:
cur = v
sf[j] = cur
orders.append(idxs)
cnt_blocks.append(cs)
sufs.append(sf)
min_counts[b] = cs[0]
max_counts[b] = cs[-1]
block_diff = [0] * (nb + 1)
def add_part(b, lo, hi, d):
vv = vals
for ii in range(lo, hi):
vv[ii] += d
idxs = orders[b]
sf = sufs[b]
cur_min = INF
for jj in range(len(idxs) - 1, -1, -1):
v = vv[idxs[jj]]
if v < cur_min:
cur_min = v
sf[jj] = cur_min
out = []
append = out.append
bl = bisect_left
for ptr in range(op_start, op_end, 3):
t = data[ptr]
x = data[ptr + 1]
if t == 1:
y = data[ptr + 2]
xi = x - 1
old = A[xi]
if old == y:
continue
d = y - old
A[xi] = y
l = x - K
if l < 0:
l = 0
r = x - 1
if r >= M:
r = M - 1
b1 = l // B
b2 = r // B
rp1 = r + 1
if b1 == b2:
if l == starts[b1] and rp1 == ends[b1]:
block_diff[b1] += d
block_diff[b1 + 1] -= d
else:
add_part(b1, l, rp1, d)
else:
lf = b1
if l != starts[b1]:
add_part(b1, l, ends[b1], d)
lf = b1 + 1
rg = b2
if rp1 != ends[b2]:
add_part(b2, starts[b2], rp1, d)
rg = b2 - 1
if lf <= rg:
block_diff[lf] += d
block_diff[rg + 1] -= d
else:
need = x
if need > max_parking:
append("IMPOSSIBLE")
continue
ans = INF
lazy = 0
for b in range(nb):
lazy += block_diff[b]
if need <= min_counts[b]:
v = sufs[b][0] + lazy
if v < ans:
ans = v
elif need <= max_counts[b]:
pos = bl(cnt_blocks[b], need)
v = sufs[b][pos] + lazy
if v < ans:
ans = v
if ans == INF:
append("IMPOSSIBLE")
else:
append(str(ans))
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
posted:
last update: